[数据结构与算法]超详细--java哈希表精讲

提示：以下是本篇文章正文内容，下面案例可供参考

一、概念

顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O( log2N)，搜索的效率取决于搜索过程中元素的比较次数。

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

当向该结构中：
插入元素
根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放

搜索元素
对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功

该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(HashTable)(或者称散列表)

二、冲突概念

（图片来自比特就业课）

我们可以通过上面的哈希函数进行数据集合的存放，比如存放4这个数据，hash(4)=4%10=4,就放在下标4的位置；

如果需要取数据，我们仍然根据这个哈希函数进行取数据，比如我们现在要取4这个数据，hash(4)=4%10=4，我们就在下标4进行取数据操作。

ps：这里可能有同学会说：啊你这个哈希函数只能对正数用啊，如果我要用负数怎么办？解决办法也很简单，我们对每个传输过来的key都加一个数m，让key+m>0即可

但是问题来了，如果我们现在存放14怎么办？hash(14)=14%10=4,那我们还放在下标4的位置吗？可是下标4的位置已经有4了啊，总不能用14把4覆盖掉吧，如果覆盖掉，将来你找4就找不到了。

所以，我们得出一个结论：
不同的关键字，通过相同的哈希函数，有可能找到相同的位置
这就是我们常说的哈希冲突/哈希碰撞。

三、冲突避免

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

3.1哈希函数设计

引起哈希冲突的一个原因可能是：哈希函数设计不够合理。

哈希函数设计原则：

1.哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间
举个例子：

图中我们的散列表允许有10个地址，那放进去的数必须是0-9

2.哈希函数计算出来的地址能均匀分布在整个空间中

3.哈希函数比较简单
下面是一些常用的哈希函数
（一般轮不到你来设计，直接拿别人的用就行/doge）

（图片来自比特就业课）

3.2负载因子调节（重点）

负载因子=存储散列表的元素个数/散列表的长度

一般我们的哈希Map负载因子是0.75，如果你的负载因子超过0.75，就需要做出修改了

（图片来自比特就业课）
如图，负载因子越大，冲突率越大，所以根据公式：

负载因子=存储散列表的元素个数/散列表的长度

我们需要增加散列表的长度，来间接减小负载因子

四、冲突解决

4.1闭散列

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

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

我们现在要往表里面放44,hash（44）=44%10=4，放在4位置，但是4位置已经被4占了，再往后一格；下标5的位置也有数；再往后一格，下标6位置没有数据，44放下标6的位置。

缺点：线性探测会把冲突的元素挨在一起，这就会造成，你如果要进行删除，比如我们现在要删除4，一旦我们不采取其他措施直接删除，我们后面想找到44就困难了

法二.二次探测：

简单来说就是冲突后放法改变了，放在Hi的位置，H0是你通过哈希函数得到的位置，比如hash(14)=14%10=4,这个4就是H0，i是第几次冲突，m是表大小，示例如下：

举例说明：

我们现在要往表里面放44和14

hash（44）=44%4=4,4与下标4里面的数据冲突，那就放在Hi=（4+1^2）%10=5，也就是下标5的位置；下标5内没有数据，不发生冲突，44就放进去了。

再继续放14，hash（14）=14%10=4，4与下标4里面数据发生冲突，注意，下标4位置之前已经发生过一次冲突了，这是第二次冲突，i=2。我们放在
HI=（4+2^2）%10=8，也就是下标为8的位置

经过这样的处理，我们的数据就不会“挨在一起”了

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

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

4.2开散列/哈希桶（重点）

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

现在，每个数组是一个桶，桶里面放的是节点（换句话说，现在数组类型为Node[ ]），节点里面包含3个元素：key，value，next（next存储下一个节点地址）。

比如我们现在有一个节点4，它里面的value是“g”，该节点地址为0x11，我们把4传过去，Hash（4）=4%10=4，4下标内没有数据，我们把它放在4下标

我们现在再放一个节点1，它里面value是“h”，该节点地址为Ox26，我们把1传过去，Hash（1）=1%10=1,1下标没有数据，我们把它放在1下标

我们继续往里面放一个节点14，它的value为"m",该节点地址为Ox33，我们把14传过去，Hash（14）=14%10=4,4下标有数据了，没有关系，我们让4节点的next指向14节点即可。

到这里，可能会有同学问，那这样如果一条一条next下去，找起来不是时间复杂度变O（N）了吗？但是不要忘记了，我们是会控制负载因子的，所以最终形成的链不会很长，时间复杂度仍然可以控制在O（1）

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

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

4.3冲突严重的解决办法

刚才我们提到了，哈希桶其实可以看作将大集合的搜索问题转化为小集合的搜索问题了，那如果冲突严重，就意味
着小集合的搜索性能其实也时不佳的，这个时候我们就可以将这个所谓的小集合搜索问题继续进行转化，例如：

1. 每个桶的背后是另一个哈希表
2. 每个桶的背后是一棵搜索树

五、代码实现

public class HashBuck {
    static class Node{
        public int key;
        public int value;//我们这里以整形value为例，如果需要其他类型可以自行修改
        public Node next;

        public Node(int key,int val){
            this.key=key;
            this.value=val;
        }
    }

    public Node[] array;
    public int usedSize;

    public HashBuck(){
        this.array=new Node[10];
    }

    public static final double DEFAULT_LOAD_FACTOR=0.75;
    //一般负载因子不可以改变，所以这里用 static final

    //put函数
    public void put(int key,int val){
        //1.找到key所在位置
        int index=key%this.array.length;

        //2.遍历这个下标的链表，看是不是有相同的key,如果有，就要更新value
        Node cur=array[index];
        while(cur!=null){
            if(cur.key==key){
                cur.value=val;
                return;
            }
            cur=cur.next;
        }
        //3.走到这里，说明没有key这个元素,我们这里用头插法(如果你想，尾插也可以的，后面用的时候没有影响)
        Node node=new Node(key, val);
        node.next=array[index];
        array[index]=node;
        this.usedSize++;
        //4.插入元素成功后，检查当前散列表的负载因子
        if(loadFactor()>=DEFAULT_LOAD_FACTOR){
            resize();
        }
    }
    //负载因子
    private double loadFactor(){
        return 1.0*this.usedSize/array.length;//1.0*是为了变成double型
    }

    //扩容
    private void resize(){
        //扩容也不仅仅是扩容，比如原先数组大小是10
        //我们扩容到20，那原先11本来是放在1号下标位置，现在要放到11号位置了
        //所以，每次扩容，我们都需要再重新哈希一遍（所有数据重新放入表内）
        Node[] newArray=new Node[array.length*2];
        for(int i=0;i<array.length;i++){
            Node cur=array[i];
            while(cur!=null){
                int index=cur.key% newArray.length;//获取重新哈希的index下标
                //下面就是需要把cur这个节点，以头插/尾插的形式插入新数组的index下标
                Node curNext=cur.next;
                cur.next=newArray[index];//先绑定前面
                newArray[index]=cur;
                cur=curNext;
            }
        }
        array=newArray;
    }

    //根据key获取value
    public int get(int key){
        //1.找到key所在位置
        int index=key%this.array.length;

        //2.遍历这个下标的链表，看是不是有相同的key,如果有，就要更新value
        Node cur=array[index];
        while(cur!=null){
            if(cur.key==key){
                return cur.value;
            }
            cur=cur.next;
        }
        return -1;
    }
}

后记

这就是我们今天要介绍的哈希表，由于它的增删查改时间复杂度都是O(1)，很多公司都在使用它，也经常会出现在面试中，请大家一定要好好学习。