哈希表

哈希表

什么是哈希表

哈希表就是一个元素有一一对应位置的一个表，如下图，哈希表也叫散列表，和函数的一个x对应一个y类似，不存在多个y对应一个x，当然哈希表可能有多个数对应一个下标，我们后面讲，这里暂且理解为和函数一样，是一种映射。 在图中，哈希表存的数据位整形，如果我们存手机号，可以将后四位作为key，或者是后四位经过一个算数处理，当作key也可以。

哈希表作为一个查找时间复杂度只有O(1)的数据接结构，可以说效率非常高。 对于二叉搜索树而言，二叉搜索树中的元素存储位置和其值没有直接对应关系，需要多次将关键码进行比较来查询。 相比二叉搜索树，哈希表有一对一对应的映射关系，不需要多次比较来查找。 我认为这是典型的空间换时间的数据结构，通过一对一映射的方式，必将有空间为空，说明其空间利用率其实不是100%，像java中，哈希表的存储利用率为0.75，超过0.75这个预设值，哈希表将被扩容，我在这篇文章中所用的开放定址法的代码将这个值控制在0.7，而拉链法的比例控制为1。

哈希冲突 如上图一样，11和22在哈希表容量为11的时候，他们对应的都是0，这就有了冲突，解决冲突有两种办法，开散列和闭散列。

开散列 开散列又叫开放定址法，一个位置只存一个元素，如果新来的元素发现该位置有冲突，就向后寻找，直至找到一个空位为止，存入数据，但是很多时候这种方法很不好，容易造成过多的冲突，于是有了二次线性探测，和直接探测不同，二次探测是依次往后探测n的平方个，第一次往后一个，第二次往后4个，第三次往后9个。

闭散列（用此种方法实现的哈希表称之为哈希桶） 闭散列又称拉链法，当有数冲突的时候，不是往后找，而是直接挂在这个位置的下面，像链表一样挂起来，这个方式一容量和元素个数的比例一般控制为1，多了会影响查找效率。

但是这种方法也有个坏处，假如有人恶意将其所有元素均存在一个位置，然后进行访问，就会出现访问速度过慢的问题，假如这被应用在网站的话，就会造成网站崩溃，无法访问。

负载因子 负载因子我在上面也有带着提到过，这里详细说一下。 负载因子α = 表中元素个数 / 散列表的长度 由于表长是定值，所以α和填入表中的元素个数成正比，α越大，表明表中数据越多，冲突的可能性越大，反之冲突越小。 实际上，散列表的平均查找长度是载荷因子α 的函数，只是不同处理冲突的方法有不同的函数。 对于开放定址法，负载因子是特别中原的因素，应严格控制在0.7~0.8以下，超过0.8，查表时CPU的缓存不命中（cache missing）按照指数曲线上升，因此一些采用开放定址法的库比如java就是限制负载因子为0.75，超过则resize。 ———————————————— 版权声明：本文为CSDN博主「无聊星期三」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。 原文链接：https://blog.csdn.net/Boring_Wednesday/article/details/80316884