Coalesced hashing

Coalesced hashing, also called coalesced chaining, is a collision resolution strategy for hash tables that blends separate chaining with open addressing. Items that hash to the same address are linked together as in a chained table, but the links run through ordinary buckets of the table itself rather than through separately allocated list nodes. When a collision occurs the new item goes into the first empty bucket, called the collision bucket, and is linked onto the chain. A new item can land on a chain that has a different hash address, so that two chains join, or coalesce, which gives the method its name. An optimisation reserves a cellar, a region of the table used only for items that collide, and the source states that restricting hash addresses to about 0.86 of the table gives near-optimum performance for most load factors. Coalescing is mild compared with the clustering of open addressing, and the search routine used for separate chaining works unchanged. Deletion is awkward and resizing is expensive.