linear probing

### 线性探测的概念 线性探测是一种解决哈希冲突的方法，在这种方法中，当发生碰撞时（即两个不同的键映射到相同的索引），算法会在表中寻找下一个可用的位置。具体来说，如果位置 \( i \) 已经被占用，则尝试位置 \( (i+1)\%N \)，其中 \( N \) 是哈希表的大小。 这种策略简单直观，但在某些情况下可能导致聚集现象，使得一些区域变得非常密集而其他地方则相对稀疏[^1]。 ### 实现方法 以下是使用 Python 编写的线性探测法实现： ```python class HashTableLinearProbing: def __init__(self, size=7): self.size = size self.keys = [None] * self.size self.values = [None] * self.size def _hash(self, key): return sum(ord(c) for c in str(key)) % self.size def put(self, key, value): index = self._hash(key) while self.keys[index] is not None: if self.keys[index] == key: break # Key already exists; overwrite it. # Linear probing step index = (index + 1) % self.size self.keys[index] = key self.values[index] = value def get(self, key): start_index = index = self._hash(key) while True: if self.keys[index] == key: return self.values[index] elif self.keys[index] is None or index == start_index - 1: raise KeyError(f'Key {key} not found') index = (index + 1) % self.size if __name__ == '__main__': ht = HashTableLinearProbing() ht.put('apple', 'red fruit') ht.put('banana', 'yellow fruit') print(ht.get('apple')) # Output should be "red fruit" ``` 在这个例子中，`_hash()` 函数计算给定键对应的初始索引；`put()` 方法用于插入新项并处理可能发生的冲突；`get()` 则负责查找特定键所关联的数据项。