基于上述LinkList类,建立一个采用链接法处理散列冲突的散列表,实现插入、 查找和删除操作。散列函数采用除法散列法,假定表中要存放500个元素,装载 因子约为3,选择合适的散列表大小python。
时间: 2023-06-26 15:10:10 浏览: 111
数据结构实验:链地址法解决冲突构建散列表
首先,根据装载因子和元素个数,可以计算出散列表的大小为 `table_size = 500 // 3 = 167`。
接下来,我们需要实现一个散列函数。这里我们采用除法散列法,即将关键字除以散列表大小取余数。代码如下:
```python
def hash_func(key, table_size):
return key % table_size
```
然后,我们定义一个散列表类,其中包含插入、查找和删除操作。在插入操作中,如果发生冲突,我们使用链接法解决。代码实现如下:
```python
class HashTable:
def __init__(self, table_size=167):
self.table_size = table_size
self.table = [None] * table_size
def insert(self, key, value):
index = hash_func(key, self.table_size)
if self.table[index] is None:
self.table[index] = LinkList()
self.table[index].append((key, value))
def find(self, key):
index = hash_func(key, self.table_size)
if self.table[index] is not None:
for node in self.table[index]:
if node.data[0] == key:
return node.data[1]
return None
def delete(self, key):
index = hash_func(key, self.table_size)
if self.table[index] is not None:
for node in self.table[index]:
if node.data[0] == key:
self.table[index].remove(node)
return True
return False
```
在这个散列表类中,我们使用了一个长度为 `table_size` 的列表来存储链表。每个元素是一个链表节点,其中包含一个键值对 `(key, value)`。在插入操作中,我们首先计算出关键字的散列值,然后将其插入到对应的链表中。如果链表不存在,则创建一个新的链表。在查找和删除操作中,我们也需要计算出关键字的散列值,然后遍历对应的链表找到相应的节点。如果找到了,我们就可以返回或删除节点。
现在我们可以创建一个散列表对象,然后测试插入、查找和删除操作了。代码如下:
```python
hash_table = HashTable()
# 插入操作
hash_table.insert(1, 'a')
hash_table.insert(2, 'b')
hash_table.insert(3, 'c')
hash_table.insert(4, 'd')
hash_table.insert(5, 'e')
# 查找操作
print(hash_table.find(3)) # 输出:c
print(hash_table.find(6)) # 输出:None
# 删除操作
hash_table.delete(4)
print(hash_table.find(4)) # 输出:None
```
在这个例子中,我们向散列表中插入了5个元素,然后分别查找了关键字为3和6的节点,最后删除了关键字为4的节点。运行结果如下:
```
c
None
None
```
阅读全文