News for hackers. Stuff that matters.
Re:Naggum Nugget by bborud on Tuesday November 02, 2010 @03:33PM (#1861946)
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.

Re:Naggum Nugget by jerf on Tuesday November 02, 2010 @04:21PM (#1862171)
"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.

Re:Naggum Nugget by tptacek on Tuesday November 02, 2010 @03:43PM (#1861990)
Saying "what if your hash table becomes linearized" is not a fair argument when comparing linear search to hash lookup.