线性探查法的两个难点
原创约 2352 字
In the previous article Core Principles of Hash Tables, I introduced the core principles and several key concepts of hash tables. I mentioned that there are two main methods to resolve hash collisions: the chaining method and the linear probing method (also known as open addressing):
Since the linear probing method is a bit more complex, this article will first explain the key challenges in implementing linear probing. The next article will provide the specific code implementation.
Simplified Scenario
The previously introduced chaining method is relatively simple: each element in the table is a linked list, and when a hash collision occurs, you just insert the element into the linked list.
The linear probing method is more complex and involves several array manipulation techniques. Before explaining these challenges, let's set up a simplified scenario:
Assume our hash table only supports key types as int and value types as int, with table.length fixed at 10. The hash function is implemented as hash(key) = key % 10. This setup easily simulates hash collisions, such as both hash(1) and hash(11) yielding a value of 1.
The basic logic of the linear probing method 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.