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 direc

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).