Talk:Coalesced hashing

From Wikipedia, the free encyclopedia

[edit] 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)