Algo Hashmap 与 Treemap Orderbook

问题分析

You are building an order book for a high-frequency trading system. The order book needs to efficiently support the following operations:

1. Insertion: Adding new orders at specific price levels.
2. Best Bid/Ask Retrieval: Quickly finding the highest bid price and the lowest ask price.
   Price level

解法

根据题目要求实现相应功能。核心逻辑需要：

// 核心数据结构和方法——根据题目 API 约定实现
// 1. 确定状态表示——选择支持所需操作的数据结构
// 2. 实现核心算法——确保 O(·) 时间复杂度和正确性
// 3. 处理边界条件——空输入、极值参数、并发访问

验证

用具体输入验证：构造已知输入的测试用例，确认输出匹配预期结果。

复杂度与边界

• 时间复杂度：取决于选用的算法
• 空间复杂度：取决于数据规模
• 关键边界条件：空输入、极值参数、并发场景下的正确性保证

英文解析

Analysis

You are building an order book for a high-frequency trading system. The order book needs to efficiently support: insertion at specific price levels, best bid/ask retrieval (highest bid, lowest ask), and price-level traversal for market data processing. HashMap provides O(1) lookup by price but requires separate tracking of min/max. TreeMap provides O(log N) operations with natural min/max from sorted structure.

Solution

// HashMap-based order book: O(1) insertion, O(1) lookup, O(N) for best bid/ask
class HashMapOrderBook {
    std::unordered_map<double, PriceLevel> levels_;
    double best_bid_ = 0, best_ask_ = DBL_MAX;
public:
    void insert(double price, int qty, bool is_buy) {
        levels_[price].addOrder(qty, is_buy);
        if (is_buy && price > best_bid_) best_bid_ = price;
        else if (!is_buy && price < best_ask_) best_ask_ = price;
    }
    double bestBid() const { return best_bid_; }
    double bestAsk() const { return best_ask_; }
};

// TreeMap-based order book: O(log N) for all operations
class TreeMapOrderBook {
    std::map<double, PriceLevel> levels_;
public:
    void insert(double price, int qty, bool is_buy) {
        levels_[price].addOrder(qty, is_buy);
    }
    double bestBid() const { return levels_.empty() ? 0 : levels_.rbegin()->first; }
    double bestAsk() const { return levels_.empty() ? DBL_MAX : levels_.rbegin()->first; }
};

Complexity & Edge Cases

• Time complexity: HashMap O(1) insert/lookup, O(N) for best; TreeMap O(log N) all operations
• Space complexity: HashMap O(N), TreeMap O(N)
• Edge cases: (1) HashMap requires updating best_bid/best_ask on each insert (2) TreeMap natural ordering gives best bid/ask for free (3) Deletion requires updating min/max in HashMap

Verification

Insert 1000 random price levels, benchmark best bid/ask retrieval speed. HashMap should be faster for insertion but slower for best retrieval. TreeMap provides consistent O(log N) for all operations. Test deletion scenario.

Key Considerations

For HFT systems, HashMap is preferred for raw insertion speed (O(1)), but requires maintaining best_bid/best_ask pointers. TreeMap provides automatic ordering but O(log N) overhead. The practical choice depends on the operation mix: if best bid/ask is queried frequently (e.g., in matching engine), HashMap with cached pointers wins. If the book is mostly iterated (e.g., for snapshot generation), TreeMap's sorted iteration is more efficient.