The idea of Open Addressing is to store the keys in the Hash Table by checking whether the index as value of that key is occupied or not. If an index already have a key with that index as value, the Hash Function searches for the next empty slot consequently. During the search of a specific key, the Hash Function checks for the key until it is found, and if it is not able to find the key, the search function returns false.
Open Addressing is further divided into three parts,
- Linear Probing
- Quadratic Probing
- Double Hashing
Open Addressing:
Open Addressing is an approach where we store all of the keys inside the Hash Table itself. Whenever a collision occurs, we handle it in such a way that it can be inserted in the Hash Table itself. For this, we need a Hash Table of size larger than or equal to the number of elements present with us.
Open Addressing is done in following ways:
1. Linear Probing:
Linear probing is a method by which we search for the next empty slot one-by-one or linearly. If we found a slot already filled, we go the next index i.e., increment the index to be checked next by one.
Let us consider a simple hash function as “key mod 7” and a sequence of keys as 50, 700, 76, 85, 92, 73, 101.
When we inserted the key ‘50’, it got inserted in the index 1, (as 50%7 = 1).
Then we inserted 700 at index 0 and 76 at index 6, according to their hash values.
Then we inserted 85, it got collided with the element at index 1 (85%7 = 1), so we searched for the next free slot, we got index 2 free, so 85 got inserted at index 2.
We continue to insert the elements to their indexes and whenever a collision occurs, we insert that element to the next free slot.
We search for the next empty slots in a circular way, for example, if we got an element collided at index 6, we search for the empty slot from index 0 till index 5, because, their might be free slots anywhere in the Hash Table.
Let’s see how actually search works in open addressing:
We compute Hash Function, we go that index and compare, if we find the required element, we return true, otherwise, we search linearly.
We stop when one of the following three cases arrive,
When we found an empty slot
When we found the key
When we have traversed through the whole table circularly.
If we found the key, we return true, and return false in other cases.
How to handle deletion in Open Addressing?
We cannot simply delete an element from that index, because we have defined the search function in such as way that the search function will stop searching for the required element whenever the function encounter an empty cell and will return false, even if the key is present beyond that empty cell.
So, to handle this, we mark the deleted slot as ‘Deleted’ instead of making that cell empty. Due to this, the search function will continue its search even when it encounter a deleted slot. There’s a problem with the Linear Probing, and that is ‘Clustering’.
Read More About Collision Handling and the Problem of Clustering:
Collision Handling and Resolving Clustering using Double Hashing
Implementation of Open Addressing:
We can implement the open addressing by creating an array of a user defined size and initializing all of the elements as -1.
The initial size of the array would be 0, as all elements are currently –1.
We can implement the search, insert and erase function also, which will take the ‘key’ as input.
The detailed code for search, insert and erase will be discussed in the next section.
In Java, we can write the following code, which will create a class named ‘MyHash’ and a constructor which takes an integer as the initial capacity of the array.
In C++, we can write the following code,
We can further implement the search function as:
In Java and C++ (boolean in Java is to be replaced with bool in C++)
In this code, we are returning true whenever we found a key at the index which is provided by the hash function.
If that index does not contain the required key, we incremented the index by 1, according to Linear Probing. And if the index reaches the value provided by the hash function, we will return false, because, the index will reach the value of hash function when it has probed through the complete table circularly.
This function will return true only when the key is found, else will return false.
Insert function can be implemented as,
In Java and C++ (boolean in Java is to be replaced with bool in C++)
In this code, we are returning false if the size of the Hash Table is equal to capacity, i.e., the Hash Table is full.
In the while condition, we are checking whether the index where the key is to be inserted does not contain the key already or -1 and -2, and if all conditions met, we will increase the index by 1, according to Linear Probing.
We will return false if the key at the index is already present, as a Hash Table contains unique keys.
If all conditions are not met, we will insert the key using the else condition and increment the size by 1 and return true.
Erase function can be implemented as,
In Java and C++ (boolean in Java is to be replaced with bool in C++)
In this code, we are using a while condition for checking whether the key at Hash Value as index to be erased is not equal to -1.
If it is not equal to -1, i.e., is not empty, we will check whether the key is present there or not. If the key is present, we will assign that cell with a value of -2, which we are using as a deleted key value, and return true.
If the value of index reaches its Hash Value again by circularly checking for the complete table, we will return false, because we are not able to find the key to be removed.
You might wonder, why did we marked the deleted cell as -2.
This is because, if we mark the deleted key cell as -1 as it was used to be before, then our search function will fail. Also, we won’t be able to check whether any specific cell used to have a value before or not.
How to handle cases when -1 and -2 are input keys?
What would we do when the keys to be inserted are -1 or -2 itself.
Our Search, Insert and Erase functions, all use the -1 and -2 as the default values in the Hash Table.
So, to handle this, most of the libraries use the pointers (in C++) or refrences (in Java) to store a key. This helps in managing any type of key without the worry or the mathematical value of the key.
For the deletion of a key, libraries use a ‘Dummy’ cell to mark the cell as erased. This helps them identify that a specific cell used to have a value before, but is now empty. This helps in smooth functioning of all of the function.
