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

上一篇文章中，我们举了 身份证号为关键字 的例子。这里，我们假设真的有一个无限大的空间，那么，可以直接将身份证号作为索引吗？ 显然不合适。因为，并不是所有的身份证号都是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类设计哈希函数，可以像字符串那样，将类的属性值看着是一个字符这样，就求出了复合类的哈希值。一致性： 当关键字相同时，经过哈希函数求出的哈希值也是相同的。 反过来是不成立的，即当哈希值相同时关键字不一定相同。哈希值相同，取模后得到的索引也相同，即不同的关键字对应的存储位置相同，这也就是所谓的哈希冲突。 高效性： 我们设计哈希函数就是为了高效存储数据，如果哈希函数的设计就消耗过多性能，那么就得不偿失了 均匀性： 通过哈希函数求出的索引必须是分布均匀的。以上，就是转化为整型求哈希函数。但是， 这并不是求哈希函数唯一的方法 。