Unique integer/long hash key generation over strings for faster compairson

algorithmcomparisonhashstring

I'm curious how others have solved this problem, and what problems might lurk behind the naive solution:

I have a system which processes stock market data. There are tens of thousands of symbols, with associated prices/sizes, flowing into the system at the rate of several thousand every millisecond.

One of the basic operations that needs to happen on every tick is string comparison to see if the incoming matches the symbol we are interested in. At such high frequency, optimization of these string comparisons can make a measurable difference in the performance of the whole system.

I am thinking of generating a hash of the symbol string, and storing it with the record. For subsequent comparison, the system should use this hash (being an int or a long, the comparison should be a single operation, rather than iterating through each character of the string until a mismatch is found).

Let's ignore the cost of generating the hash itself (which, in reality, may actually be prohibitive). The only problem I can see is that with a large number of unique symbols, a hash collision (two separate symbols generate the same hash) would be devastating. Is there a hashing algorithm which guarantees that strings which match certain constraints (such as limit on the number of characters) are unique?

EDIT: I'll write this code in Java. Not sure of the (collision) quality of hashCode or the speed with which it is calculated.

Best Solution

Maybe hash functions aren't the best approach here. If you're receiving a ticker symbol (and not the hash of the ticker symbol) you're going to have to compute the hash for it every single time it comes through. If its a hashing algorithm with no collisions, you'll need to look at every character of the symbol anyway. So you might as well directly compare the characters.

I suggest building a Trie data structure of all the tickers you're interested in. (see http://en.wikipedia.org/wiki/Trie). Traverse the tree for each symbol and if you reach the end of the ticker without finding a match, then its not an interesting ticker.

With hashing, you'll have to do this traversal anyway in the set of all hash values of the interesting tickers.

Related Question