Key Points to Implement Linear Probing
OriginalAbout 2353 words
In the previous article Core Principles of Hash Tables, I introduced the core principles of hash tables and several key concepts. It mentioned two main methods for resolving hash collisions: chaining and linear probing (also known as open addressing):
Since linear probing is slightly more complex, this article will first explain some challenges in implementing linear probing, and the next article will provide specific code implementation.
Simplified Scenario
The previously introduced chaining method is relatively simple. Basically, each element in the table is a linked list, and when a hash collision occurs, you just add the element to the list.
Linear probing is more complex, mainly due to two challenges involving various array operation techniques. Before explaining these challenges, let's set up a simplified scenario:
Assume our hash table only supports key and value types as int, and table.length is fixed at 10. The hash function is implemented as hash(key) = key % 10. This setup easily simulates hash collisions, for example, hash(1) and hash(11) both result in 1.
The basic logic of linear probing is as follows:
java 🟢
// The basic logic of linear probing, pseudocode implementation
class MyLinearProbingHashMap {
// Each element in the array stores a key-value pair
private KVNode[] table = new KVNode[10];
private int hash(int key) {
return key % table.length;
}
public void put(int key, int value) {
int index = hash(key);
KVNode node = table[index];
if (node == null) {
table[index] = new KVNode(key, value);
} else {
// Logic of linear probing
// Probe backwards until the key is found or an empty slot is found
while (index < table.length && table[index] != null && table[index].key != key) {
index++;
}
table[index] = new KVNode(key, value);
}
}
public int get(int key) {
int index = hash(key);
// Probe backwards until the key is found or an empty slot is found
while (index < table.length && table[index] != null && table[index].key != key) {
index++;
}
if (table[index] == null) {
return -1;
}
return table[index].value;
}
public void remove(int key) {
int index = hash(key);
// Probe backwards until the key is found or an empty slot is found
while (index < table.length && table[index] != null && table[index].key != key) {
index++;
}
// Remove table[index]
// ...
}
}cpp 🤖
// The basic logic of linear probing, pseudo-code implementation
class KVNode {
public:
int key;
int value;
KVNode(int k, int v) : key(k), value(v) {}
};
class MyLinearProbingHashMap {
private:
// Each element in the array stores a key-value pair
KVNode* table[10] = {nullptr};
int hash(int key) {
return key % 10;
}
public:
void put(int key, int value) {
int index = hash(key);
KVNode* node = table[index];
if (node == nullptr) {
table[index] = new KVNode(key, value);
} else {
// The logic of linear probing
// Probe backwards until the key is found or an empty slot is found
while (index < 10 && table[index] != nullptr && table[index]->key != key) {
index++;
}
table[index] = new KVNode(key, value);
}
}
int get(int key) {
int index = hash(key);
// Probe backwards until the key is found or an empty slot is found
while (index < 10 && table[index] != nullptr && table[index]->key != key) {
index++;
}
if (index >= 10 || table[index] == nullptr) {
return -1;
}
return table[index]->value;
}
void remove(int key) {
int index = hash(key);
// Probe backwards until the key is found or an empty slot is found
while (index < 10 && table[index] != nullptr && table[index]->key != key) {
index++;
}
// Delete table[index]
// ...
}
};python 🤖
# Basic logic of linear probing, pseudo-code implementation
class KVNode:
def __init__(self, key, value):
self.key = key
self.value = value
class MyLinearProbingHashMap:
# Each element in the array stores a key-value pair
def __init__(self):
self.table = [None] * 10
def hash(self, key):
return key % len(self.table)
def put(self, key, value):
index = self.hash(key)
node = self.table[index]
if node is None:
self.table[index] = KVNode(key, value)
else:
# Logic of linear probing
# Probe backwards until key is found or an empty slot is found
while index < len(self.table) and self.table[index] is not None and self.table[index].key != key:
index += 1
self.table[index] = KVNode(key, value)
def get(self, key):
index = self.hash(key)
# Probe backwards until key is found or an empty slot is found
while index < len(self.table) and self.table[index] is not None and self.table[index].key != key:
index += 1
if self.table[index] is None:
return -1
return self.table[index].value
def remove(self, key):
index = self.hash(key)
# Probe backwards until key is found or an empty slot is found
while index < len(self.table) and self.table[index] is not None and self.table[index].key != key:
index += 1
# Delete table[index]
# ...go 🤖
// Basic logic of linear probing, pseudo-code implementation
// Each element in the array stores a key-value pair
type KVNode struct {
key int
value int
}
type MyLinearProbingHashMap struct {
table []*KVNode
}
func NewMyLinearProbingHashMap() *MyLinearProbingHashMap {
return &MyLinearProbingHashMap{
table: make([]*KVNode, 10),
}
}
func (m *MyLinearProbingHashMap) hash(key int) int {
return key % len(m.table)
}
func (m *MyLinearProbingHashMap) Put(key int, value int) {
index := m.hash(key)
node := m.table[index]
if node == nil {
m.table[index] = &KVNode{key: key, value: value}
} else {
// Logic of linear probing
// Probe backwards until you find the key or an empty slot
for index < len(m.table) && m.table[index] != nil && m.table[index].key != key {
index++
}
m.table[index] = &KVNode{key: key, value: value}
}
}
func (m *MyLinearProbingHashMap) Get(key int) int {
index := m.hash(key)
// Probe backwards until you find the key or an empty slot
for index < len(m.table) && m.table[index] != nil && m.table[index].key != key {
index++
}
if m.table[index] == nil {
return -1
}
return m.table[index].value
}
func (m *MyLinearProbingHashMap) Remove(key int) {
index := m.hash(key)
// Probe backwards until you find the key or an empty slot
for index < len(m.table) && m.table[index] != nil && m.table[index].key != key {
index++
}
// Delete table[index]
// ...
}
func main() {
hashMap := NewMyLinearProbingHashMap()
hashMap.Put(1, 10)
hashMap.Put(2, 20)
fmt.Println(hashMap.Get(1)) // 10
fmt.Println(hashMap.Get(2)) // 20
fmt.Println(hashMap.Get(3)) // -1
hashMap.Put(2, 30)
fmt.Println(hashMap.Get(2)) // 30
hashMap.Remove(2)
fmt.Println(hashMap.Get(2)) // -1
}javascript 🤖
// basic logic of linear probing method, pseudo-code implementation
class MyLinearProbingHashMap {
constructor() {
// each element in the array stores a key-value pair
this.table = new Array(10).fill(null);
}
hash(key) {
return key % this.table.length;
}
put(key, value) {
var index = this.hash(key);
var node = this.table[index];
if (node === null) {
this.table[index] = { key: key, value: value };
} else {
// logic of linear probing method
// probe backwards until a key is found or an empty slot is found
while (index < this.table.length && this.table[index] !== null && this.table[index].key !== key) {
index++;
}
this.table[index] = { key: key, value: value };
}
}
get(key) {
var index = this.hash(key);
// probe backwards until a key is found or an empty slot is found
while (index < this.table.length && this.table[index] !== null && this.table[index].key !== key) {
index++;
}
if (this.table[index] === null) {
return -1;
}
return this.table[index].value;
}
remove(key) {
var index = this.hash(key);
// probe backwards until a key is found or an empty slot is found
while (index < this.table.length && this.table[index] !== null && this.table[index].key !== key) {
index++;
}
// delete this.table[index]
// ...
}
}Based on this hypothetical scenario, let's examine the two challenges of linear probing.