Re:Problems with Hash Tables
by nimrody on Friday January 08, 2010 @03:54PM
(#1040406)
Potential benefit of hash tables: cache locality.
Assuming you already have the key in the CPU cache, computing the hash is relatively cheap and gets you directly to the desired value.
A binary tree structure always makes you traverse several levels until you get to the desired value. Of course, this can be minimized with high-fanout trees -- see clojure for example).
Assuming you already have the key in the CPU cache, computing the hash is relatively cheap and gets you directly to the desired value.
A binary tree structure always makes you traverse several levels until you get to the desired value. Of course, this can be minimized with high-fanout trees -- see clojure for example).