Data Structures and Algorithms: BRIDGES

Closed hashing stores all records directly in the hash table. Each record with a key value kR has a home position at h(kR), which is computed by the hash function. If the home position is occupied during insertion, the record is stored in another slot within the table, and the collision resolution policy determines which slot that will be. This policy is also followed during search to retrieve any record not found in its home position, repeating the collision resolution process.

One implementation of closed hashing involves grouping hash table slots into buckets. The M slots of the hash table are divided into B buckets, each containing M/B slots. Records are assigned to the first available slot within a bucket based on the hash function. If a slot is already taken, the bucket slots are searched sequentially until an open slot is found. If a bucket becomes full, records are stored in an overflow bucket with infinite capacity located at the end of the table. All buckets share the same overflow bucket. A well-designed implementation uses a hash function that evenly distributes records among the buckets to minimize the use of the overflow bucket.

During a search for a record, the key is hashed to determine the bucket that should contain the record. The records in this bucket are then searched. If the desired key value is not found and the bucket still has free slots, the search is complete. However, if the bucket is full, it is possible that the desired record is stored in the overflow bucket.

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