A tree access is ~log n memory lookups and every one of them can miss cache. A hash map access is ~1 memory lookup, which can miss cache. Even when you have cac

A tree access is ~log n memory lookups and every one of them can miss cache. A hash map access is ~1 memory lookup, which can miss cache. Even when you have cache collisions and need to do a linear search in a bucket it's not going to cause additional cache misses if the bucket is allocated as an array.