哈希表超详解

小灰灰 2024-03-27 19:18 12阅读 0赞

**目录**

哈希表

概念

冲突-概念

冲突-避免

冲突-避免-哈希函数设计

冲突-避免-负载因子的调节

冲突-解决-闭散列

冲突-解决-开散列

哈希桶的实现

性能分析

java和类集的关系

--------------------

## 哈希表 ##

### 概念 ###

> **顺序结构及平衡树**中，元素关键码与其存储位置之间没有对应关系，因此查找一个元素时，必须要通过关键码的多次比较。**顺序查找的时间复杂度为O(N),平衡树中为树的高度，即O(log2 N)**,搜索的效率取决于搜索过程中元素的比较次数。
> 
> 因此我们就会想，有没有一种理想的方法，**可以不经过任何比较，一次从表中得到要搜索的元素**。**那么就可以构造某种函数，使该元素的存储位置与关键码之间存在映射关系，（即key->通过某种方法->一次定位到key的位置），那么这种通过函数的方式就很容易找到元素**

当向该结构中：

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

该方式即为哈希（散列）方法，**哈希方法中使用的转换函数称为哈希（散列）函数，构造出来的结构称为哈希表（或称为散列表）**

例如：数据集合\{1,7,6,4,5,9\};

哈希函数设置为：hash(key) = key % capacity;capacity为存储元素底层空间的总大小

存储情况如下：

![d7427d8f61344a04a6b9b62442600ad4.png][]

**用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快。**而此时又衍生出来了一个问题，万一两个关键码通过函数计算的存放位置相同，该怎么办？这就涉及到了冲突。

### 冲突-概念 ###

对于两个数据元素的关键字ki和kj(i!=j),有ki != kj,但有Hash(ki) == Hash(kj),即：**不同关键字通过哈希函数计算出相同的哈希地址，这种现象称为哈希冲突或哈希冲撞 。**

**把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。**

### **冲突-避免** ###

> 首先，我们明确一点，由于哈希表底层数组的容量往往是小于实际要存储的关键字数量的，这就导致了一个问题，**冲突发生是必然的，但我们能做到的是尽可能降低冲突率。**

### **冲突-避免-哈希函数设计** ###

> 引起哈希冲突的一个原因可能是：**哈希函数设计不够合理。哈希设计原则：**
> 
> 1.哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间。
> 
> **2.哈希函数计算出来的地址能均匀分布在整个空间中**
> 
> 3.哈希函数应该比较简单

**常见哈希函数(常用)**

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

**注意:哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突**

### **冲突-避免-负载因子的调节** ###

> **散列表的载荷因子定义为 ： a = 填入表中元素个数 / 散列表的长度**
> 
> **注：由于散列表长度是定值，所以填入表中的元素个数越多，产生冲突的可能性就越大。**
> 
> 对于开放定址法，荷载因子是特别重要的因素，应该严格限制在0.7-0.8以下，超过0.8，查表时CPU缓存不命中按照指数直线上升。因此，一些采用开放定址法的hash库，如Java系统库限制了荷载因子为0.75，如果超过荷载因子的话将对散列表进行扩容。

**负载因子和冲突率的关系粗略演示**

![486554e5b4214849bcd9582f37fc1603.png][]

所以当冲突率达到一个无法忍受的程度时，我们需要通过降低负载因子来降低冲突率。

**已知哈希表中已有关键字个数是不可变的，那么我们只能调整哈希表中数组的大小。**

**解决哈希冲突的两种常见方法有：闭散列和开散列。**

### 冲突-解决-闭散列 ###

> **闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置的下一个“空位置中去”。那么如何寻找空位置呢？**

**1.线性探测**

> 比如下面的场景：现在需要插入元素44，先通过哈希函数计算哈希地址，下标为4，因此44理论上应该插在该位置，但是该位置已经放了值为4的元素，即发生哈希冲突。 
> 
> 线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。

插入

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

![5947607be23a4728b30eef3e40e4fbaa.png][]

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

**2.二次探测**

> 线性探测的缺陷是产生的数据堆积在一块（导致不能均匀分布在空间中），这与其找下一个空位置有关系，因为找空位置的方式就是挨个往后逐个去找 ，因此二次探测为了避免该问题，找下一个空位置的方法为：Hi = (H0 + i ^ 2) % m.**H0为应该放置的位置，m为冲突次数，m为表的大小。**
> 
> 研究表明：当表的长度为质数且表装载因子a不超过0.5时，新的表项一定能够插入，而且任何一个位置都不会被探查两次。只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子a不超过0.5，如果超出必须考虑增容。

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

### 冲突-解决-开散列 ###

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

方法如图所示：

![b7f6f539d4004686a2e00c67c3fba0d3.png][]

从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素。

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

### **哈希桶的实现** ###

下面是基于key-value模型写的哈希桶部分方法的代码：

//key-value模型
    public class HashBucket {
        private static class Node {
            private int key;
            private int value;
            Node next;
    
            public Node(int key, int value) {
                this.key = key;
                this.value = value;
            }
        }
    
        //用数组表示哈希表
        private Node[] array;
        //当前哈希表元素个数
        private int size;
        //定义荷载因子
        private static final double LOAD_FACTOR = 0.75;
    
        public int put(int key, int value) {
            //根据哈希函数确定存放的下标
            int index = key % array.length;
    
            //在链表中查找key所在的结点
            //如果找到了，更新
            //所有节点都不是key，插入一个新的结点
            for (Node cur = array[index]; cur != null; cur = cur.next) {
                if(key == cur.key) {
                    int oldValue = cur.value;
                    cur.value = value;
                    //返回更新前key对应的value
                    return oldValue;
                }
            }
            //链表遍历完成，没有找到这个key
            Node node = new Node(key, value);
            node.next = array[index];
            array[index] = node;
            size++;
    
            if(loadFactor() >= LOAD_FACTOR) {
                resize();
            }
            return -1;
        }
    
        private void resize() {
            //创建一个扩容数组,并将原来数组中的元素按照新的规则放入新的数组当中
            Node[] newArray = new Node[array.length * 2];
            //遍历原来的数组
           for(int i = 0; i < array.length; i++) {
               //遍历一个数组中的链表
               Node cur = array[i];
               while(cur != null) {
                   //利用tmp记录cur的位置
                   Node tmp = cur.next;
                   //计算元素在新数组中的位置
                   int newIndex = cur.key % newArray.length;
                   //头插法
                   cur.next = newArray[newIndex];
                   newArray[newIndex] = cur;
                   //回溯cur的位置
                   cur = tmp;
               }
           }
            //将新数组赋值给原数组
            array = newArray;
        }
    
        //计算当前荷载因子的大小
        private double loadFactor() {
            return size * 1.0 / array.length;
        }
    
        public HashBucket() {
            array = new Node[8];
            size = 0;
        }
    
        //get方法
        public int get(int key) {
            int index = key % array.length;
    
            Node head = array[index];
            Node cur = head;
            while(cur != null) {
                if(key == cur.key) {
                    return cur.value;
                }
                cur = cur.next;
            }
    
            //未找到，则返回-1
            return -1;
        }
    }

### 性能分析 ###

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

### java和类集的关系 ###

> 1.HashMap和HashSet即java中利用哈希表实现的Map和Set
> 
> 2.java中使用的是哈希桶的方式解决冲突的
> 
> 3.java会在冲突链表长度大于一定阈值后，将链表转变为二叉搜索树（红黑树）
> 
> 4.java中计算哈希值实际上是调用的类的hashCode方法，进行key的相等性比较是调用key的equals方法。所以如果要用自定义类作为HashMap的key或者HashSet的值，**必须覆写hashCode和equals方法**，而且要做到equals相等的对象，hashCode一定是一致的

[d7427d8f61344a04a6b9b62442600ad4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/352b53c1cb57447ab2bdcfd7978786e9.png
[486554e5b4214849bcd9582f37fc1603.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/8680f8ad630b4895baa219511a89963f.png
[5947607be23a4728b30eef3e40e4fbaa.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/03faf00614d9438dbd58fe3bc820664d.png
[b7f6f539d4004686a2e00c67c3fba0d3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/fb3a3a6ff66f44eb9090fd2d572d13d5.png