> What's wrong with red-black trees for an ordered map?
I was wondering that too, except without the "n ordered" part. The claim that trees are competitive with hash tables in the average case rests on the claim that comparison is much faster than hashing, because you only have to hash once in the average case, whereas you have to compare something like 1.5 lg N times in the average case, which might be between 4 and 22 in common cases. I just ran this microbenchmark to compare hashing integers with comparing them, and hashing seems to be actually slightly faster than comparing on my CPU; this implies that hash tables should be dramatically faster than red-black trees.
In theory, this forces an unpleasant dilemma on code that aspires to be real-time but wants to do a lookup in a finite map: use hash tables with their awful worst-case performance (typically O(N), although you can improve this by hanging trees off your hash buckets, but that would be stupid), or use trees with their awful average-case performance?
In practice, I've never written real-time code, so I don't know if this dilemma is real.
I was wondering that too, except without the "n ordered" part. The claim that trees are competitive with hash tables in the average case rests on the claim that comparison is much faster than hashing, because you only have to hash once in the average case, whereas you have to compare something like 1.5 lg N times in the average case, which might be between 4 and 22 in common cases. I just ran this microbenchmark to compare hashing integers with comparing them, and hashing seems to be actually slightly faster than comparing on my CPU; this implies that hash tables should be dramatically faster than red-black trees.
https://gist.github.com/814746
In theory, this forces an unpleasant dilemma on code that aspires to be real-time but wants to do a lookup in a finite map: use hash tables with their awful worst-case performance (typically O(N), although you can improve this by hanging trees off your hash buckets, but that would be stupid), or use trees with their awful average-case performance?
In practice, I've never written real-time code, so I don't know if this dilemma is real.