This article has not yet been rated on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||||||
|
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.
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.
sandtreader 15:18, 28 March 2006 (UTC)
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)