3 ms·
That doesn't even describe a hash table, it describes an associative array, or map. A hash table as one way to implement that, the other main one being self-bal
by cup-of-tea 8y ago
That doesn't even describe a hash table, it describes an associative array, or map. A hash table as one way to implement that, the other main one being self-balancing binary trees.
- ummonk 8y agoOr more broadly, self-balancing trees (the best performing balanced tree, the B-tree, is not generally a binary tree). And then there is the skip list.
- cup-of-tea 8y agoYes, quite right. Is a B-tree worth it when the structure is fully in memory, though? I would say that when talking about maps people are thinking of in memory structures.
- ummonk 8y agoIt absolutely is! You get significantly better cache utilization with a B-tree.