冰冻非一日之寒
上一篇文章中，我们举了身份证号为关键字的例子。这里，我们假设真的有一个无限大的空间，那么，可以直接将身份证号作为索引吗？
显然不合适。因为，并不是所有的身份证号都是18位的，对于那些位数在17位以下的，就太浪费这个大空间了。
设计哈希函数的原则是，将我们所关心的键通过哈希函数求出索引，“键”通过哈希函数得到的“索引”分布越均匀越好(实际上，实现起来非常困难)
那么，对于像身份证号这样的大整数为关键字时，该怎么计算对应的索引呢？
或者像复合类、字符串、浮点数这样类型的关键字，该如何计算它们对应的索引呢？
对于哈希函数来说，我们只能将整型数据作为关键字来求解索引。所以，不管什么类型的关键字，我们应该先将其转化为整型类型的数据。
按照这个思路，以下介绍几种最简单、最基础、最一般、最通用的哈希函数
整型
小范围正整数直接使用
例如，上一篇讲的ASCII值作为关键字
再例如，一个班有30个学生，1—30表示每位学生对应的学号，并作为关键字
像这样的小范围正整数，可以直接将关键字作为索引，存储到数组中去
小范围负整数进行偏移
例如，-100～100的数作为关键字，这时可以每个数都加上100，变为0～200的正整数
这样，就可以将关键字直接作为索引存储到数组中去
大整数取模
例如，身份证号作为关键字，412637199707096354
取后四位(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类设计哈希函数，可以像字符串那样，将类的属性值看着是一个字符
复合类哈希函数
这样，就求出了复合类的哈希值。
求哈希函数原则
原则
一致性：当关键字相同时，经过哈希函数求出的哈希值也是相同的。
反过来是不成立的，即当哈希值相同时关键字不一定相同。哈希值相同，取模后得到的索引也相同，即不同的关键字对应的存储位置相同，这也就是所谓的哈希冲突。
高效性：我们设计哈希函数就是为了高效存储数据，如果哈希函数的设计就消耗过多性能，那么就得不偿失了
均匀性：通过哈希函数求出的索引必须是分布均匀的。
以上，就是转化为整型求哈希函数。但是，这并不是求哈希函数唯一的方法。
网友评论