Coalesced hashing

Given a sequence "qrj," "aty," "qur," "dim," "ofu," "gcl," "rhv," "clq," "ecd," "qsu" of randomly generated three character long strings, the following table would be generated (using Bob Jenkins' One-at-a-Time hash algorithm) with a table of size 10: This strategy is effective, efficient, and very easy to implement.

However, sometimes the extra memory use might be prohibitive, and the most common alternative, open addressing, has uncomfortable disadvantages that decrease performance.

Coalesced hashing uses a similar technique as separate chaining, but instead of allocating new nodes for the linked list, buckets in the actual table are used.

An important optimization, to reduce the effect of coalescing, is to restrict the address space of the hash function to only a subset of the table.

[1] Insertion in C: One benefit of this strategy is that the search algorithm for separate chaining can be used without change in a coalesced hash table.