Coalesced hashing

From Wikipedia, the free encyclopedia

Coalesced hashing, also called coalesced chaining, is a strategy of collision resolution in a hash table that forms a hybrid of separate chaining and open addressing. As such, it trades performance for lower memory requirements. Recall, that open addressing generally achieves O(1) lookup time as long as the hash table is not too full. This results is a large memory requirement. Separate chaining, however, is packed in memory with very low overhead. The shortcomings of separate chaining are exactly the same as naive forms of open addressing in that long chains are akin to long probings. After the initial hash, they both require linear lookup time. Thus one could say that separate chaining also exhibits a clustering phenomenon.

In much the same way as it is for sorting, there are a number of ways to do hashing, however, there is usually only one that is used in practice: double hashing. Double hashing is a form of collision resolution for open addressing. And in practice double hashing allows one to keep lookup complexity lower while having a higher occupancy rate in the table.