【数据结构】哈希表

目录

1、哈希表 

1.1 哈希表的简介 

1.2 降低哈希冲突率

1.3 解决哈希冲突 

1.3.1 闭散列

1.3.2 开散列（哈希桶） 

---

1、哈希表 

1.1 哈希表的简介 

假设我们目前有一组数据，我们要从这组数据中找到指定的 key 值，那么咱们目前的学习阶段可以利用三种方法：

• 把数据存储在数组当中，按顺序依次查找，时间复杂度为 O(n)
• 把数据存储在数组当中，此时数组有序，则可以用二分查找法，时间复杂度为 O(logn)
• 将其转化成搜索树进行查找，时间复杂度为 O(logn)

除了上述的查找方式以外，是否还有比上述查找方式的时间复杂度更优的呢？

答：有，还有一种方式可以做到查找时间复杂度为 O(1)，这种方式就是用哈希表进行查找 

哈希方法：通过某种函数使元素的存储位置与它的关键码(元素)之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素，不经过任何比较，一次直接从表中得到要搜索的元素

哈希函数和哈希表：哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表

• 插入操作：插入元素根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放 
• 搜索操作：对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功 

例如：假设我们现在有这样一种数据集合{1，6，7，5，4，9}

哈希函数设置为：hash = key % capacity

• hash：位置 
• key ：数据值
• capacity：数组长度

哈希表的长度为：10 

假设我们现在要将第一个元素 1，放进哈希表中，首先通过哈希函数确定插入的位置 hash = 1%10那么此时 1 插入的位置也就是哈希表中下标为 1 的位置，其他元素也都是按照同样的方式进行存放到哈希表中

当我们进行搜索操作的时候也是通过哈希函数进行搜索的，假设我们现在需要查找 6 这个元素所在的位置，hash = key % capacity 也就是 6 % 10 = 6，此时 6 这个元素所在的位置就在 6 下标

假设我们目前需要在上述哈希表中插入 11 ，通过哈希函数找到的下标位置为 1，然后此时 1 下标的位置已经有值了，此时也就造成了哈希冲突问题了 

哈希冲突：不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞 

哈希冲突产生的原因：由于我们哈希表底层数组的容量往往是小于实际要存储的关键字的数量的，这就导致一 个问题，冲突的发生是必然的，但我们能做的应该是尽量的降低冲突率

1.2 降低哈希冲突率

那如何降低哈希冲突呢？

1.设计合理的哈希函数（哈希函数往往并不是由我们设计的，而是由专业人员进行设计的） 

哈希函数设计原理： 

• 哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1 之间 哈希函数计算出来的地址能均匀分布在整个空间中 哈希函数应该比较简单
• 哈希函数计算出来的地址能均匀分布在整个空间中 
• 哈希函数应该比较简单 

常见的哈希函数，目前咱们也就只介绍两个： 

• 直接定制法：取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B。  优点：简单、均匀  缺点：需要事先知道关键字的分布情况 使用场景：适合查找比较小且连续的情况 
• 除留余数法：设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数： Hash(key) = key% p(p<=m),将关键码转换成哈希地址 

 2.调节负载因子

负载因子 = 填入表中的元素个数 / 表的长度 

负载因子的作用： 

通过上述图就可以看出当负载因子越大时，冲突率也是越高的 

那如何调节负载因子呢？ 

答：已知填入表中的元素个数是不变的，那么就只能调整哈希表的数组长度了。当数组长度越长，那么负载因子也就越小 

一般情况下，哈希表会有一个默认的负载因子值为 0.75f

设计合理函数和调节负载因子也不能完全避免冲突 ，那么此时就可以解决哈希冲突

1.3 解决哈希冲突 

解决哈希冲突常见的方法是：闭散列 和 开散列

1.3.1 闭散列

闭散列(开放地址法)：当发生哈希冲突时，如何哈希表未被装满还有空余的位置，那么就可以将元素 key 存放到冲突位置中的 “下一个” 空位置中

那么我们应该如何找到下一个空位置呢？ 

方法一：线性探测法 

线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止 

插入： 

•  通过哈希函数获取待插入元素在哈希表中的位置
• 如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到 下一个空位置，插入新元素 

假设我们要在上述的哈希表中插入11，通过哈希函数确定的位置是下标 1，但是下标 1 的位置此时有元素发生了哈希冲突，使用线性探测找到的下一个空位置为下标2的位置，则把11 插入到下标2的位置 

采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他 元素的搜索。比如删除元素1，如果直接删除掉，11查找起来可能会受影响。因此线性探测采用标 记的伪删除法来删除一个元素。

方法二：二次探测法

线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨 着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法为：

假设我们现在需要在上述表中插入元素 11，通过哈希函数确定的位置是下标 1，但是下标 1 的位置此时有元素发生了哈希冲突，这是与 下标1 位置发生的第一次冲突：（11 + 1*1）% 10 = 2。那么此时元素 11 插入的位置就是下标2的位置

研究表明：当表的长度为质数且表装载因子a不超过0.5时，新的表项一定能够插入，而且任何一个位置都不 会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情 况，但在插入时必须确保表的装载因子a不超过0.5，如果超出必须考虑增容 

闭散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷 

1.3.2 开散列（哈希桶） 

开散列：开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中

• JDK1.7版本及以前每个桶使用的是头插法
• JDK1.8版本及以后每个桶使用的是尾插法 

开散列可以认为是把一个在大集合中的搜索问题转化为在小集合中做搜索了 

那会不会哈希表中一个桶的长度太长，而导致搜索效率为 O(n)呢？

答：应该不会，因为有负载因子，当一个桶的长度太长时，会进行扩容

hashMap就是采用开散列的方式进行处理的， 当哈希表的长度到达64且桶的长度到底8时，会转换成红黑树 

虽然哈希表一直在和冲突做斗争，但在实际使用过程中，我们认为哈希表的冲突率是不高的，冲突个数是可控的， 也就是每个桶中的链表的长度是一个常数，所以，通常意义下，我们认为哈希表的插入/删除/查找时间复杂度是 O(1)