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

Question

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.

Answer 1

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.

Answer 2

Common cryptographic hash functions like SHA-1 outputs 20 bytes (160 bit). How long are your stock symbols? If we're talking about ticker symbols like "WMT" (Walmart), "KO" (Coca-Cola), etc, then they seem to be only a couple of bytes long -- thus it should be faster to compare them directly instead of dealing with a 20 byte hash. You mention hash collisions -- I wouldn't worry about them, especially not when the inputs are much smaller than the hash output.

You might be able to cast the bytes into an int or long depending on the programming language and platform and then do the comparison between these "numbers" in one CPU instruction. (I don't know if modern compilers can compare a bunch of bytes equally fast with a call to memcmp?)