DS哈希查找—二次探测再散列
时间: 2024-01-06 19:05:52 浏览: 60
DS哈希查找-二次探测再散列是一种解决哈希冲突的方法。它使用二次探测再散列技术来解决冲突,即当发生冲突时,通过一定的算法找到下一个可用的位置。
以下是DS哈希查找-二次探测再散列的步骤:
1. 定义哈希函数:首先,需要定义一个哈希函数,将关键字映射到哈希表的位置。在这个例子中,哈希函数为H(key) = key%11,即将关键字除以11取余数。
2. 创建哈希表:根据输入的表长,创建一个具有相应大小的哈希表。
3. 插入关键字:将输入的关键字集合插入到哈希表中。如果发生冲突,即两个关键字映射到了同一个位置,就使用二次探测再散列来找到下一个可用的位置。
4. 查找给定关键字:根据给定的关键字,使用哈希函数计算出它在哈希表中的位置。如果该位置上的关键字与给定关键字相等,则找到了;否则,使用二次探测再散列找到下一个位置,直到找到相等的关键字或者遇到空位置。
下面是一个示例代码,演示了DS哈希查找-二次探测再散列的过程:
```python
def hash_function(key, table_size):
return key % table_size
def insert(hash_table, key, table_size):
index = hash_function(key, table_size)
if hash_table[index] is None:
hash_table[index] = key
else:
i = 1
while True:
new_index = (index + i*i) % table_size
if hash_table[new_index] is None:
hash_table[new_index] = key
break
i += 1
def search(hash_table, key, table_size):
index = hash_function(key, table_size)
if hash_table[index] == key:
return index
else:
i = 1
while True:
new_index = (index + i*i) % table_size
if hash_table[new_index] == key:
return new_index
elif hash_table[new_index] is None:
return -1
i += 1
# 创建哈希表
table_size = 11
hash_table = [None] * table_size
# 插入关键字
keys = [12, 23, 34, 45, 56, 67, 78, 89, 90]
for key in keys:
insert(hash_table, key, table_size)
# 查找给定关键字
search_key = 34
result = search(hash_table, search_key, table_size)
if result != -1:
print("关键字 {} 在哈希表中的位置是 {}".format(search_key, result))
else:
print("关键字 {} 不在哈希表中".format(search_key))
```
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)
![](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)