将线性探测法改为链地址法
时间: 2024-06-14 14:06:17 浏览: 15
链地址法是一种解决散列冲突的方法,它将散列表中的每个槽都看作是一个链表的头节点,当发生冲突时,将冲突的元素插入到对应槽的链表中。下面是将线性探测法改为链地址法的示例代码:
```python
class Node:
def __init__(self, key, value):
self.key = key
self.value = value
self.next = None
class HashTable:
def __init__(self, size):
self.size = size
self.table = [None] * size
def hash_function(self, key):
return key % self.size
def insert(self, key, value):
index = self.hash_function(key)
if self.table[index] is None:
self.table[index] = Node(key, value)
else:
node = self.table[index]
while node.next is not None:
node = node.next
node.next = Node(key, value)
def search(self, key):
index = self.hash_function(key)
node = self.table[index]
while node is not None:
if node.key == key:
return node.value
node = node.next
return None
# 示例用法
hash_table = HashTable(10)
hash_table.insert(5, "apple")
hash_table.insert(15, "banana")
hash_table.insert(25, "orange")
print(hash_table.search(5)) # 输出:apple
print(hash_table.search(15)) # 输出:banana
print(hash_table.search(25)) # 输出:orange
```
在上述代码中,我们定义了一个`Node`类来表示链表中的节点,每个节点包含一个键值对和一个指向下一个节点的指针。`HashTable`类中的`table`列表用于存储链表的头节点。当发生冲突时,我们将新的键值对插入到对应槽的链表的末尾。在搜索时,我们根据键的哈希值找到对应的链表,并遍历链表查找目标键的值。
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)