Linear Probing in Python
Linear probing is a technique used in hash tables to handle collisions. When a collision occurs (i.e., when two keys hash to the same index), linear probing searches for the next available slot in the hash table by incrementing the index until an empty slot is found.
What is Linear Probing?
In linear probing, the hash table is searched sequentially that starts from the original location of the hash. If in case the location that we get is already occupied, then we check for the next location.
Linear Probing Algorithm:
- Calculate the hash key. i.e. key = data % size
- Check, if hashTable[key] is empty
- store the value directly by hashTable[key] = data
- If the hash index already has some value then
- check for next index using key = (key+1) % size
- Check, if the next index is available hashTable[key] then store the value. Otherwise try for next index.
- Do the above process till we find the space.
Below is the implementation of the above approach:
class LinearProbeHashTable:
def __init__(self, size):
self.size = size
self.keys = [None] * size
self.values = [None] * size
def hash_function(self, key):
return hash(key) % self.size
def put(self, key, value):
index = self.hash_function(key)
# Linear probing to find an empty slot
while self.keys[index] is not None:
if self.keys[index] == key:
# If key already exists, update its value
self.values[index] = value
return
index = (index + 1) % self.size
# Insert the key-value pair
self.keys[index] = key
self.values[index] = value
def get(self, key):
index = self.hash_function(key)
# Linear probing to find the key
while self.keys[index] is not None:
if self.keys[index] == key:
return self.values[index]
index = (index + 1) % self.size
# Key not found
return None
hash_table = LinearProbeHashTable(10)
hash_table.put('apple', 5)
hash_table.put('banana', 7)
hash_table.put('orange', 3)
print(hash_table.get('banana')) # Output: 7
print(hash_table.get('grape')) # Output: None
Output
7 None
Time complexity: O(n)
Auxiliary Space: O(n)