DS哈希查找--链地址法(表头插入)
时间: 2023-06-27 10:01:05 浏览: 68
链地址法是哈希表解决冲突的一种方法,它的基本思想是将哈希表中的每个槽作为一个链表的头结点,将哈希值相同的元素插入到相应的链表中。
在链地址法中,每个槽都是一个链表的头结点,每个元素都被插入到相应槽对应的链表中。当发生哈希冲突时,只需要在相应槽对应的链表中插入新元素即可。
具体实现时,可以使用一个数组来存储链表的头结点。插入元素时,先计算出它在哈希表中的位置,然后将它插入到相应槽对应的链表的头部即可。
下面是一个使用链地址法解决哈希冲突的示例代码:
```python
class Node:
def __init__(self, val):
self.val = val
self.next = None
class HashTable:
def __init__(self, size):
self.size = size
self.table = [None] * size
def hash(self, val):
return val % self.size
def insert(self, val):
index = self.hash(val)
node = Node(val)
node.next = self.table[index]
self.table[index] = node
def search(self, val):
index = self.hash(val)
node = self.table[index]
while node:
if node.val == val:
return True
node = node.next
return False
def delete(self, val):
index = self.hash(val)
node = self.table[index]
if not node:
return False
if node.val == val:
self.table[index] = node.next
return True
while node.next:
if node.next.val == val:
node.next = node.next.next
return True
node = node.next
return False
```
在这个实现中,我们使用了一个 `Node` 类来表示链表中的节点。在 `HashTable` 类中,我们使用一个数组 `table` 来存储链表的头结点。`hash` 方法用来计算元素的哈希值。`insert` 方法用来插入元素,将它插入到相应槽对应的链表的头部。`search` 方法用来查找元素,遍历相应槽对应的链表,直到找到元素或遍历完链表。`delete` 方法用来删除元素,首先需要遍历相应槽对应的链表,找到要删除的元素,然后将它从链表中删除即可。