动态查找表代码
时间: 2023-07-10 19:16:34 浏览: 43
动态查找表可以使用各种数据结构来实现,比如哈希表、红黑树、AVL树等等。以下是一个使用哈希表实现的动态查找表代码示例:
```python
class DynamicHashTable:
def __init__(self):
self.capacity = 16 # 初始容量
self.size = 0 # 元素个数
self.table = [None] * self.capacity # 哈希表
# 哈希函数
def _hash(self, key):
return hash(key) % self.capacity
# 扩容
def _resize(self):
self.capacity *= 2
new_table = [None] * self.capacity
for i in range(len(self.table)):
item = self.table[i]
if item is not None:
key, value = item
index = self._hash(key)
while new_table[index] is not None:
index = (index + 1) % self.capacity
new_table[index] = (key, value)
self.table = new_table
# 插入
def insert(self, key, value):
if self.size >= self.capacity * 0.75:
self._resize()
index = self._hash(key)
while self.table[index] is not None:
if self.table[index][0] == key:
self.table[index] = (key, value)
return
index = (index + 1) % self.capacity
self.table[index] = (key, value)
self.size += 1
# 查找
def find(self, key):
index = self._hash(key)
while self.table[index] is not None:
if self.table[index][0] == key:
return self.table[index][1]
index = (index + 1) % self.capacity
return None
# 删除
def delete(self, key):
index = self._hash(key)
while self.table[index] is not None:
if self.table[index][0] == key:
self.table[index] = None
self.size -= 1
return
index = (index + 1) % self.capacity
```
这个示例使用哈希表来实现动态查找表,哈希函数使用了Python内置的`hash`函数。在插入元素时,如果哈希表的负载因子大于0.75,则进行扩容操作。在查找和删除元素时,使用线性探测解决哈希冲突。