浅谈哈希表与其映射函数（哈希函数）
哈希表⼜称散列表，通过把关键字key映射到数组中的⼀个位置来访问记录。映射过程通过函数实现，⽽这个函数就叫哈希函数，存放关键字的数组称为散列表。 哈希表结构
前⾯说了，关键字是存放在数组中的，所以哈希表的结构其实就是⼀个数组，为什么要采⽤数组来作为哈希表的数据结构呢？这⾥我不得不说数组的⼀些特性。
数组的时间复杂度是O(1)，这⾥说的时间复杂度是访问复杂度，不是遍历复杂度。计算机内存被设定为直接访问任意⼀个地址的时间是⼀致的，结合该特性，我们知道数组在内存中的存储是，数组名存放在栈内存中，保存数组第⼀个元素的地址，⽽数组本⾝存放在堆内存中，其存储空间是连续的，所以我们只需要知道数组名就可以⾮常快速的定位数组任意位置。华北煤炭医学院学报
哈希算法的作⽤是将关键字通过⼀系列计算，得出的结果作为数组下标，然后再将关键字存放到该下标
谋杀章鱼保罗对应的位置。哈希算法是决定哈希表中元素排列结构的最主要因素，不同的哈希算法会导致同样的数据出现不同的存储顺序。针对不同类型的关键字哈希算法也不同。下⾯是针对整数关键字的⼏种哈希算法（如果关键字是字符串，也可将字符串所有字符的ASCII码加起来得到⼀个整数再进⾏计算）：
直接取余：顾名思义，直接取余法是⽤关键字除以⼀个固定值取余数，⼀般这个固定值取哈希表的⼤⼩。如果⼀个哈希表的⼤⼩是16，那么关键字100的存放位置应该是数组下标为4的位置。
乘积取整：成绩取整法是⽤关键字乘以⼀个常数A(0<A<1)，然后取乘积的⼩数部分再与哈希表的⼤⼩求积，最后取结果的整数部分。同上，若哈希表的⼤⼩为16，A取0.025，那么关键字100的存放位置应该是数组下标为8的位置。
上⾯提到的两种算法都⾮常简单，但都存在很⼤的问题，这两种算法在某种程度上都会产⽣⼤量的冲突，即不同的数通过算法得出的结果相同，这样会令哈希的效果⼤打折扣。下⾯介绍⼀种解决冲突⾮常有效的哈希算法，经典哈希算法Time33 uint32_t time33(char const *str, int len)
{
unsigned long hash = 0;
for (int i = 0; i < len; i++) {
hash = hash *33 + (unsigned long) str[i];
}
return (hash & 0x7FFFFFFF);
}
从代码中我们可以看出，这种算法就是将关键字每⼀位拿出来，逐个相加，每相加⼀次都乘以33，最终获得我们要的结果。该算法可最⼤程度防⽌冲突的发⽣，亦可避免字符串类型的关键字顺序不同⽽所含字符相同导致计算结果相同（如adcfg和dcfga）。在php中，⼀个字符串长度过长不好计算，我们可以将其先利⽤MD5加密转化为32位的字符串，然后再对这个字符串进⾏计算即可。
在学习Time33之前，我⾃⼰也想过⼀个避免该类问题的算法，供⼤家讨论，思想如下：
海德堡cp2000如图，针对⼀个关键字，我们可对其从1开始进⾏依次编号，然后取每⼀位的值或者ASCII码值与它所
对应的编号相乘，最后求和。这种⽅法与Times33类似，都可以有效的解决⼤量冲突问题，但是仍避免不了⼀些及特殊的情况。为了防⽌这些哈希算法⽆法避免的冲突，所以⼈们开始从哈希表的结构下⼿，希望通过改变哈希表的结构来避免这些冲突，因此⼜出现了许多避免冲突的⽅法，如“拉链法”解决冲突。
笑蜀
“拉链法”解决冲突的做法是将所有哈希值相同的关键字节点链接在同⼀个链表中。如下图：
山核桃采摘机
“拉链法”将哈希值相同的关键字通过链表的⽅式连接起来，确实有效的解决了冲突问题，但是在查询关键字的时候，若所查询的位置⽆冲突，那么查询的时间复杂度为O(1)，但如果所查询的位置出现冲突，就需要进⼀步遍历链表去查询，这样的话查询的效率⼤打折扣，时间复杂度并不能满⾜所谓的O(1)，所以说哈希表只能在理想⽆冲突的情况下，时间复杂度才能到达O(1)。因此来看，要降低时间复杂度最终的瓶颈还是在怎么防⽌冲突的问题上⽽不是出现冲突怎样处理的问题上。但是并不产⽣冲突⼏乎是不可能实现的，那么有没有⼀种办法既能有效处理出现的冲突，⼜能优化时间复杂度呢？我不知道现在有没有这种⽅法，但是我提供⼀种思路供⼤家思考，这种思路叫“⼆次散列”。
“⼆次散列”，说⽩了就是对每⼀个关键字都进⾏两种不同形式/函数的散列，然后根据两次的结果确定该关键字的位置（如果两个不同的关键字通过哈希函数A算出的哈希值相等，那么他们通过哈希函数B
所算出的哈希值⼏乎不可能相等，哈希函数A和B可⾃⾏决定，但是最好取两种散列思路不同的算法）。⽽存储⽅式就叫“坐标法”，跟”拉链法”⼤体相似，不同的是，”拉链法”采⽤链表储存冲突，“坐标法”利⽤数组存储冲突。该结构的特点是它有⼀个纵向数组，类似于哈希表的原始结构，纵向数组每⼀位对应⼀个横向数组（横向数组命名应为编号式，下划线后的数字为所对应的纵向数组下标，如M_0[]、M_1[]….），第⼀次散列所计算出哈希值为纵向数组下标，若该位置为空说明⽆冲突发⽣，直接存储；若有值，判断是否相等，若不等说明冲突，先为该下标申请其所对应的横向数组，然后进⾏第⼆次散列，第⼆次散列所对应的哈希值为横向数组的下标，也就是该关键字所要存放的位置，类似于X/Y轴，查询的时候最多只需做两次散列⼀次⽐较，就可以确定关键字的具体位置。为什么不直接使⽤⼆维数组呢？因为毕竟不是所有位置都会发⽣，使⽤⼆维数组会过度消耗内存空间。该⽅法还是存在很多缺陷，只提供⼀个思考的⽅向。
总的来说，散列函数的好坏是决定哈希表性能的关键，⼀个好的哈希函数⼀定具备两个特性，⼀是⾜够聚集，⼆是不重叠，这样即保证了内存的有效利⽤也保证了查询的时效，但这两个特性在理论上相悖，只能去⼀个平衡点，使性能最⼤化。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议