哈希表的设计与实现毕业论文

上一篇文章中，我们举了 身份证号为关键字 的例子。这里，我们假设真的有一个无限大的空间，那么，可以直接将身份证号作为索引吗？ 显然不合适。因为，并不是所有的身份证号都是18位的，对于那些位数在17位以下的，就太浪费这个大空间了。 设计哈希函数的原则是，将我们所关心的键通过哈希函数求出索引， “键”通过哈希函数得到的“索引”分布越均匀越好 (实际上，实现起来非常困难) 那么，对于像身份证号这样的大整数为关键字时，该怎么计算对应的索引呢？ 或者像复合类、字符串、浮点数这样类型的关键字，该如何计算它们对应的索引呢？ 对于哈希函数来说，我们只能将整型数据作为关键字来求解索引。所以，不管什么类型的关键字，我们应该先将其转化为整型类型的数据。 按照这个思路，以下介绍几种最简单、最基础、最一般、最通用的哈希函数 小范围正整数直接使用 例如，上一篇讲的ASCII值作为关键字 再例如，一个班有30个学生，1—30表示每位学生对应的学号，并作为关键字 像这样的小范围正整数，可以直接将关键字作为索引，存储到数组中去 小范围负整数进行偏移 例如，-100～100的数作为关键字，这时可以每个数都加上100，变为0～200的正整数 这样，就可以将关键字直接作为索引存储到数组中去 大整数取模 例如，身份证号作为关键字，4126374 取后四位(6354)。也就是，mod 10000 假如，取后六位(096354)。即，mod 100 0000 这样，会 分布不均匀 对于身份证号来说，后六位的前两位(09)代表着日期数，也就是1～31的数字。那么，这个六位数不会达到32 0000这么大，中国这么多人口，显然这个数字是不够的，这也就造成了索引分布不均匀 这也就体现了哈希函数的复杂性，也说明了具体问题要具体分析。 上面的取模方式还有一个问题，没有 有效利用所有信息。 我们这样取模，只是利用了关键字的一部分，也就是不管这个人是哪个地区哪个年份出生的，都有可能存储到一个地址中去，这样会增加哈希冲突的概率。那么，该如何解决这个问题呢？ 一个简单的解决办法： 模一个素数 为什么要模一个素数呢？简单举个例子显然，模一个素数，结果会分布的更均匀，哈希冲突的概率也会变小。我们该如何选择这个素数呢？相关的领域专家已经为我们研究出了答案。假如，需要存储的数在2^5～2^6之间，模上53就可以了。 注：这个表并不是唯一的，一个区间内可以有多个素数 将浮点型解析成大整型，之后再相应取模(如上) 先看一个例子把一个整数用科学计数法来表示，同样，字符串也可以类似表示。将这个字符串看成26进制，是因为有26个小写字母，如果字符串中有大写字母或者标点符号，那么看成26进制显然是不够的，可以看成是100进制或者256进制等。显然，这个进制是用户可以自己选择的，我们用 B 来表示这个进制每一个小写字母对应一个数字，这样我们把字符串也转化成了大整型，之后就可以利用上面取模的方式计算哈希值了。这样就可以计算出字符串的哈希值了。当B是一个比较大的数或者字符串比较长时，求B的k次方是比较浪费时间的，所以我们可以优化这个表达式这样就省去了求次方运算。但是，还有可能会出现整型溢出的情况，当B是一个很大的数字或者字符串很长的时候，我们可以再次优化这个表达式这样，每退出一个小括号，数字都会变成比M先得数字，就不会出现溢出情况了 假如我们自己定义一个类，日期类 Date：year，month，day 为这个Date类设计哈希函数，可以像字符串那样，将类的属性值看着是一个字符这样，就求出了复合类的哈希值。一致性： 当关键字相同时，经过哈希函数求出的哈希值也是相同的。 反过来是不成立的，即当哈希值相同时关键字不一定相同。哈希值相同，取模后得到的索引也相同，即不同的关键字对应的存储位置相同，这也就是所谓的哈希冲突。 高效性： 我们设计哈希函数就是为了高效存储数据，如果哈希函数的设计就消耗过多性能，那么就得不偿失了 均匀性： 通过哈希函数求出的索引必须是分布均匀的。以上，就是转化为整型求哈希函数。但是， 这并不是求哈希函数唯一的方法 。

概念：这是什么？

大家可能想知道这一串英文是什么意思？其实只需要了解在collections库当中有一个非常重要的抽象基类MutableMappin

g，专门用于实现map的一个非常有价值的工具。后边我们会用到它。

2-我们的map基类

实现这个类

这个基类其实也就是确定了键值对的属性，并且存储了基本的比较方法。它的对象就是一个键值对咯。这个很好理解。有点类似object的感觉。

3-通过map基类实现的无序映射

给大家看一个上边的例子，这个例子来源于网络，自己改了改，能用，更加详细而已，凑合看.

4-Python哈希表的实现的基类

咱有话直说：上才（代）艺（码）

如果还不知道哈希表概念的同xio，请参考 python进阶之数据结构与算法–中级-哈希表（小白piao分享） 。废话不多说，咱们撸代码：

OK了，基本的哈希表就实现了，其实仔细想想很容易，但是自己要能实现还是要理解哈希表的本质哦，外加一定量的练习才可以熟练掌握，练习的目的就是为了熟练而已。

5-分离链表实现的具体哈希map类

说明：这玩意只是一种降低冲突的手段，上一节提过，降低冲突最好的地方是发生在元组进入桶的时候，所以想必大家猜到了，接下来的分离链表也就是为了系列方法做准备。这里之所以在上边使用@abstractmethod就是为了继承实现，目的可以实现多种将冲突的哈希表。分离链表的概念上一节也有的。 “见码入面”（借鉴：见字如面这个电视节目，有兴趣可以看看，还不错的）：

6-用线性探测处理冲突的哈希map类

这种方式的好处不需要再去借助其他额外的赋值结构来表示桶。结构更加简单。不会再像上一种方法还要让桶是一个UnsortedTableMap的对象。 代码如下：