Talk:Coalesced hashing

O(1) addition

If you maintain a freelist of unused buckets, the search for the next collision bucket - and hence the whole addition process - is always O(1). The buckets as described already have a 'next' field to do this. On removal, the now unused bucket can just be put back at the head of the freelist again.

The only problem with this is if the collision buckets are also used as normal buckets - in this case, a non-colliding addition may want to snarf a bucket out of the middle of the freelist. To avoid an O(N) search for the preceding bucket in the freelist, you need to institute a back-pointer for the list - but since this is only needed when the bucket is unused, you can union() over the normal value data.

If you do that, than how can you distinguish between a free and and an used bucket? Usually, the bucket stores a *key pointer to data that is NULL if the cell is free. So you can use this technique only if you have larger data, and you can somehow mark it as invalid and signal that some part of the data is actually a back-pointer. 85.204.119.88 14:59, 2 August 2006 (UTC)

Also, there is no particular reason to O(N) search to the end of a collision chain on insertion. The quickest O(1) method is always to add after the head - this makes the ordering rather strange, but in most applications that shouldn't matter.

One reason would be to keep the average linked list within reasonable bounds. Otherwise a value can "fall" indefently long to the end of the list, making it's retrieval more expensive. Sure, this means you've made the path to other keys shorter, so it's the same on average.85.204.119.88 14:59, 2 August 2006 (UTC)

sandtreader 15:18, 28 March 2006 (UTC)

Unclear example

The "Bob Jenkins' One-at-a-Time hash algorithm" link goes to a page with many links, none of which appear to describe "Bob Jenkins' One-at-a-Time hash algorithm". This is confusing, and prevents the page from being self-contained. Since the actual hashing algorithm isn't important for the purposes of the example, it might be better to use something simple, such as "take the first character of the string".-crms (talk) 23:39, 12 October 2014 (UTC)

 Done. I changed the link to the hashing algorithm used in this example so that when you click on it, it now goes directly to a section of a Wikipedia article that gives a short self-contained description of the algorithm. --DavidCary (talk) 13:36, 29 July 2016 (UTC)