I am curious about how you deal with matches that are not exact?
> if a value exists at that key you fill the order (or partial fill)
If there is an existing sell for 100 and a buy comes in for 101 your hash will miss the 100 entry, do you need to do a scan down the array looking for potential matches?
You're not going to be able to get away from traversing the order book for every match. Another subtle differentiating factor is the time at which the potential matches entered the order book. Obviously priority is always given to price (better price always taken first) but assuming 2 potential orders came into the book for the same price, the one that got there first will be matched.
Another thing to think about is that some firms also don't always want price improvement for an asset. Typically these firms are custodians of other peoples assets and need to trade with equal and offsetting amounts between multiple accounts. If they get price improvement then they end up buying or selling a different quantity which then leaves them responsible for explaining the difference. A lot of times it's just more trouble than its worth.
You can definitely get away with traversals - and they are often required. The simplest method would be to use a sorted list. The head of the list is always the best price, so comparing the best bid against the best offer is linear and can be performed every time the orders are modified. Order insertion is naively O(log n) as the list is sorted, but this can be optimized by keeping a journal of orders and only immediately inserting orders close to the best price. You can then insert from the journal into the order book as time allows or if the best price moves a large enough amount.
There are a lot of other techniques too, but you definitely can't just let people buy or sell a different quantity. At least on any formal market I know of?
I'm thinking about FX where I work. If the price you get executed at is better than what you wanted your term currency amount changes. Often times what ends up happening is that some someone upstream (e.g. broker) ends up keeping the improvement.
