Explain why is meant by the terms closed bucket, collision and load factor in the context of hash tables.

Closed Bucket

In the context of hash tables, a "closed bucket" refers to a strategy for handling collisions within the hash table. A hash table is a data structure that maps keys to values, using a hash function to compute an index into an array of buckets or slots, where the corresponding value is to be stored.

When two different keys produce the same index, a collision occurs. The closed bucket approach, also known as "open addressing," resolves collisions by finding another bucket within the hash table for the second key-value pair. This is done through various probing techniques such as linear probing, quadratic probing, or double hashing.

Collision

A collision in a hash table is an event that occurs when two different keys hash to the same index. Since a hash function maps multiple keys to a finite number of buckets, collisions are inevitable in any non-trivial hash table.

There are several strategies to handle collisions:

1. Chaining: Each bucket is independent, and contains a list of all key-value pairs that hash to the same index.
2. Open Addressing (Closed Bucket): All key-value pairs are stored within the array itself. When a collision occurs, the hash table seeks out the next empty slot according to a probing sequence.

Load Factor

The load factor is a measure that gives an idea of how full a hash table is. It is defined as the ratio of the number of entries (or keys) to the number of buckets (or slots) in the hash table.

The formula for the load factor (α) is:

[ \alpha = \frac{n}{m} ]

Where:

• ( n ) is the number of entries in the hash table.
• ( m ) is the total number of buckets.

The load factor is an important metric because it affects the performance of the hash table. A low load factor means there are many empty buckets, which can lead to wasted memory. A high load factor increases the likelihood of collisions, which can degrade the performance of the hash table, especially with open addressing where the cost of probing for an empty slot increases.

Comparison Table

Term	Definition	Relevance	Handling Strategy	Example
Closed Bucket	A collision resolution strategy where all elements are stored within the hash table array itself.	Used in open addressing schemes.	Probing (linear, quadratic, double hashing).	If two keys, k1 and k2, hash to the same index, k2 is placed in the next available slot found by probing.
Collision	Occurs when two keys hash to the same index.	Inevitable in hash tables due to the pigeonhole principle.	Chaining, Open Addressing.	Keys k1 and k2 produce the same hash value h(k1) = h(k2).
Load Factor	The ratio of the number of entries to the number of buckets in the hash table.	Indicates how full the hash table is.	Resize the hash table, adjust the hash function.	A hash table with 100 buckets and 75 entries has a load factor of 0.75.

Example of Collision and Load Factor

Consider a hash table with 10 buckets, and a simple hash function h(x) = x mod 10. If we insert the following keys: 2, 12, 22, they will all hash to the same index (2), causing collisions.

After inserting these keys, the load factor would be:

[ \alpha = \frac{3}{10} = 0.3 ]

This load factor indicates that the hash table is 30% full. If we continue to add more keys and the number of entries increases to 8, the load factor becomes:

[ \alpha = \frac{8}{10} = 0.8 ]

At this point, the hash table is 80% full, and the likelihood of collisions is much higher. To maintain efficient operations, it might be necessary to increase the number of buckets (resize the hash table) or improve the hash function to better distribute the keys.