实现OPEN 哈希表模板类
时间: 2024-03-26 08:30:38 浏览: 78
OPEN哈希表是一种基于哈希表的数据结构,它使用开放定址法来解决哈希冲突。实现OPEN哈希表模板类的步骤如下:
1. 定义一个哈希表类,包含哈希表的大小、哈希函数、哈希表的存储数组等成员变量和方法。
2. 定义哈希函数,常用的哈希函数方法为除留余数法,即H(key)=key MOD p (p<=m,m为表长)。
3. 处理哈希冲突使用开放定址法中的线性探测再散列的方法:当哈希值出现冲突时,我们找到出现冲突后存储的位置进行存储,如果仍然有冲突那么继续向后。
4. 定义put()函数,用于将键值对存储到哈希表中。在put()函数中,判断当哈希值在哈希表中的下标位置是否为空,不为空就把这个哈希值数值在哈希表中的下标赋值分别为键和值,如果哈希值数值下标在哈希表中的位置上不为空但是键值一样(也就是上面有相同的键),那就新值替换旧值,也就是哈希表中的值修改一下。如果在这个位置既不是空而且键值不相等,那么就使用线性探测再散列的方法将哈希值往后+1位,并使用while进行判断直到哈希表中的位置为空或键值相等时结束,再把哈希表中的值进行赋值。
5. 定义get()函数,用于根据键获取值。在get()函数中,输入一个键值得到它的哈希值,然后循环找到对应的哈希表中键值与输入的键比较,找到对应的键值,然后返回出哈希表中的值。
6. 定义哈希表的存储数组,可以使用Python中的列表来实现。
7. 最后,可以编写一些测试代码来测试哈希表的功能是否正常。
阅读全文