Data Structures and Algorithms: BRIDGES

Hash functions aim to minimize collisions, but in practice, some collisions are inevitable. Thus, collision resolution policies are essential in hashing implementations. There are two primary classes of collision resolution techniques: open hashing (or separate chaining) and closed hashing (or open addressing). Despite the confusing naming convention, open hashing involves storing collisions outside the table, while closed hashing stores one of the records in another slot within the table.

In the simplest form of open hashing, each slot in the hash table is the head of a linked list. All records that hash to a particular slot are placed in that slot’s linked list. This creates a structure where each slot points to a linked list that holds the records associated with that specific slot. The hash function used in this case is the straightforward mod function. The following figure illustrates a hash table employing open hashing and the mod function for hash calculations.

Open hashing is well-suited for scenarios where the hash table is stored in main memory, and the lists are implemented using standard in-memory linked lists. However, using open hashing to store a hash table on disk efficiently poses challenges. Since members of a linked list may be stored in different disk blocks, searching for a specific key value would require multiple disk accesses, undermining the purpose of hashing.

Open hashing shares some similarities with Binsort. In open hashing, each record is placed in a bin, even though multiple records may hash to the same bin. This initial binning significantly reduces the number of records accessed during a search operation. Similarly, a simple Binsort organizes records into bins, reducing the number of records in each bin to a small manageable number that can be sorted using a different approach.

Here is a link to the OpenDSA textbook that can tell you more about open hashing: Read Me¹