3 ms·
isn't this making a lot of assumptions with regard to memory locality and the organization of the hash table? for instance: what if the initial capacity isn't
by bborud 16y ago
isn't this making a lot of assumptions with regard to memory locality and the organization of the hash table?
for instance: what if the initial capacity isn't set properly for the hash table? what if the hash function isn't perfect and you end up with 16 buckets and 4 elements in one bucket and none in the other 15? (at which point you end up with what is essentially a list with lots of overhead). what if you start off by allocating a hash table that is too small and midway through populating it have to expand it?
the more comments I read, the more Erik becomes right.
- tptacek 16y agoSaying "what if your hash table becomes linearized" is not a fair argument when comparing linear search to hash lookup.
- jerf 16y ago"isn't this making a lot of assumptions with regard to memory locality and the organization of the hash table?" Well, yeah. Always. But if you want to talk about how Erik is right, you probably want to go looking for an algorithm specifically designed for storing alists in a cache aware manner. Not sure what such a beast would look like, but something could probably be constructed and probably has been.