|
|
|
|
|
|
by misja111
3280 days ago
|
|
|
Even if the typical bucket has 100 members, as long as this number is constant and does not go up with the size of the hash table, the performance is still O(1). And the same applies for cache misses. All these things don't really matter except if you are using hash tables with not very many elements in them. |
|
|
If you mean in a chained hash table, where you chase up to 100 pointers to get the value, the performance is atrocious.
Friendly reminder: traversal of a linked list and a contiguous array are both O(n). In the real world one is two orders of magnitude faster than the other.
> All these things don't really matter except if you are using hash tables with not very many elements in them.
The lookup of a value given a key is probably the least affected operation. If all you care about is a "weak dictionary" (you only really need to store values and lookup from keys), all of this is mostly jabber. If you store the keys to iterate through, or access for some reason, all those things start to matter a whole lot.