⭐️前面的话⭐️

本篇文章将介绍哈希表的基本概念，哈希函数，哈希冲突的预防以及哈希冲突的解决方式，哈希表的简单实现。

📒博客主页：未见花闻的博客主页
🎉欢迎关注🔎点赞👍收藏⭐️留言📝
📌本文由未见花闻原创，CSDN首发！
📆首发时间：🌴2022年8月31日🌴
✉️坚持和努力一定能换来诗与远方！
💭参考书籍：📚《Java核心技术》，📚《Java编程思想》，📚《Effective Java》
💬参考在线编程网站：🌐牛客网🌐力扣
博主的码云gitee，平常博主写的程序代码都在里面。
博主的github，平常博主写的程序代码都在里面。
🙏作者水平很有限，如果发现错误，一定要及时告知作者哦！感谢感谢！

1.哈希表概要

1.1什么是哈希表

哈希表，又称散列表，它是直接根据关键码值key直接获取到数据的一种数据结构，就是你给出一个key，它就能找到一个对应的value，所以使用哈希表进行查找的时间复杂度能够达到 $O(1)$。

比如将数据key与数组下标做一个映射，数组里面存入的元素作为value，我们首先可以通过一个哈希函数找到某个key映射到数组的下标，将对应的某个数据存入数组，以此类推，将数据全部通过哈希函数映射到数组中，然后我们就可以通过相同的哈希函数和key找到对应数据所储存的下标，最后直接访问即可查询到数据。

1.2哈希函数

上面我们说了，哈希表是将key通过哈希函数映射生成一个下标，然后将对应的数据存入到下标对应的数组位置上。

那这个哈希函数应该怎么设定呢？哈希函数必须满足以下要求，不然容易造成数据在数组某一处位置集中，产生严重的哈希冲突：

• 哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间，也就是保证通过哈希函数计算的值要覆盖所有的数组下标。
• 哈希函数计算出来的地址能均匀分布在整个空间中，就是尽量保证生成的哈希值比较稀疏，而不是集中。
• 哈希函数的设计应当尽量简单。

如上面所举例的哈希函数是通过数据取数组长度的模计算出来的。

1. 直接寻址法：取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a*key + b，其中a和b为常数（这种散列函数叫做自身函数）。
2. 数字分析法：分析一组数据，比如一组员工的出生年月日，这时我们发现出生年月日的前几位数字大体相同，这样的话，出现冲突的几率就会很大，但是我们发现年月日的后几位表示月份和具体日期的数字差别很大，如果用后面的数字来构成散列地址，则冲突的几率会明显降低。因此数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。
3. 平方取中法：取关键字平方后的中间几位作为散列地址。
4. 折叠法：将关键字分割成位数相同的几部分，最后一部分位数可以不同，然后取这几部分的叠加和（去除进位）作为散列地址。
5. 随机数法：选择一随机函数，取关键字的随机值作为散列地址，通常用于关键字长度不同的场合。
6. 除留余数法：取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key % p, p<=m。不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。对p的选择很重要，一般取素数或m，若p选的不好，容易产生同义词。

哈希函数的设计方式有很多种，其中最常见的就是直接寻址和除留余数法。

1.3哈希冲突

1.3.1什么是哈希冲突？

但是呢，只要你的关键字个数大于数组的长度，就一定会产生冲突，就是某个下标下有多个数据，即不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。

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

也就是说哈希冲突不可避免，我们只能尽量去降低哈希冲突。

1.3.2如何降低哈希冲突的概率？

方式1：设计好哈希函数

我们要知道，哈希地址是通过哈希函数计算出来的，所以如果通过哈希函数计算出来的哈希地址分布比较均匀，那就能够有效降低哈希冲突的概率。

方式2：调节负载因子

负载因子的定义为：填入表中的元素个数与散列表的长度之比就叫做负载因子。研究表明冲突率与负载因子的关系图如下（单位均为%）：

从图中我们大致可以看出最适的负载因子在70%左右，在java的HashMap类中，HashMap的底层就是哈希表，在jdk8中，默认的负载因子为0.75。

所以当冲突率达到一个无法忍受的程度时，我们需要通过降低负载因子来变相的降低冲突率。已知哈希表中已有的关键字个数是不可变的，那我们能调整的就只有哈希表中的数组的大小，即当负载因子超过某值，我们就对数组进行扩容。

1.4解决哈希冲突的方式

1.4.1闭散列

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

方式1：线性探测

从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。如在下面这个哈希表的基础上再插入一个25。

由于插入25时，已经存在元素5了，所以我们将它插入到5后面的第一个空位上，如果后面没有空位，就会回到数组开头进行查找，也就是说使用该方法必须保证数组长度大于元素个数，并且如果有很多数据冲突，那么数据就会堆积到一块。

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

方式2：二次探测

线性探测的缺陷是产生冲突的数据堆积在一块，这与其直接寻找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，二次探测为了避免该问题，找下一个空位置的方法为： $H_i = ( H_0+ i^2)\%m$与 $H_i = ( H_0-i^2)\%m$轮换的方式求新的地址，其中： $i = 1,2,3…$， $H_0$ 是通过散列函数 $Hash(key)$对元素的关键码 $key$ 进行计算得到的位置， $m$是数组的大小。

如求得的地址冲突，就会以 $哈希值+i^2,哈希值 -i^2....$的顺序进行探测新的位置。

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

1.4.2开散列

开散列，也叫挂地址法，就是将冲突的元素挂在一个集合中，进行储存，常用的集合有链表，红黑树等。

如果挂的是链表，此时的数组就是一个链表数组或者叫做结点数组，毕竟链表是许多结点构成的。

我们在查找的时候，首先通过哈希函数找到对应的链表，然后在链表上遍历查找即可，如果哈希函数和负载因子适宜，其实每个链表的元素不会有很多，因此遍历链表的时间开销也是常数级别的。

下面我们来简单实现一下哈希表。

2.哈希表的简单实现

2.1哈希表实现思路

首先我们要明确哈希表的底层是一个数组，为了有效解决哈希冲突的问题，我们设置的负载因子为0.75，使用开散列的方式进行冲突的解决，也就是使用链表数组来进行元素的储存。

哈希表最大的用处就是查找，查找之前我们需要进行插入操作，所以我们模拟实现主要是实现哈希表的插入和查找，删除其实也是查找，只不过查找到不是将元素返回而是删除。

构造时哈希表中数组的默认容量就随便定一个吧，就16吧。

哈希函数，由于我们模拟的是整数类型数据的哈希表，所以直接对key取数组长度的模即可。
即： $hash(key)=key\%len$。

2.2哈希表实现代码

2.2.1类基本属性定义

负载因子，默认数组长度，有效元素个数等属性定义如下：

    //默认哈希表初始数组大小16
    private final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
    //默认负载因子为0.75
    private final double DEFAULT_LOAD_FACTOR = 0.75;
    //元素个数
    private int usedSize;

链表结点定义，里面包含键值对key与vakue以及next指针：

    //定义结点
    static class Node {
        public int key;
        public int value;
        public Node next;

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

储存数据的是一个Node数组：

    //链表数组
    public Node[] array;

构造方法：

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

2.2.2哈希表的插入

第一步，通过哈希函数和key找到数组对应的下标。
第二步，遍历数组中对应下标的链表是否有重复的元素，如果有则更新值。
第三步，如果没有重复的元素，根据传入的key与vaule建立结点，采用尾插或头插的方式将结点插入到链表中。
第四步，使有效元素个数加上1。
第五步，检查负载因子（即有效元素个数/数组长度）是否大于默认的负载因子，如果满足此条件则进行扩容resize()。

    /**
     * 插入键值对
     * @param key
     * @param value
     */
    public void put(int key, int value) {
        //找到key所在的位置
        int index = key % this.array.length;

        //查找是否存在重复的元素
        Node cur = array[index];
        while (cur != null) {
            if (cur.key == key) {
                cur.value = value;
                return;
            }
            cur = cur.next;
        }
        //如果不存在重复的元素，那就插入结点，头插也行尾插也行
        Node node = new Node(key, value);
        node.next = array[index];
        array[index] = node;
        usedSize++;
        //插入完成之后，检查负载因子
        if (loadFactory() >= DEFAULT_LOAD_FACTOR) {
            //扩容
            resize();
        }
    }

计算负载因子的方法：

    /**
     * 计算负载因子
     * @return 当前负载因子的大小
     */
    public double loadFactory() {
        return 1.0 * this.usedSize / this.array.length;
    }

2.2.3扩容方法的实现

扩容我们采用2倍的方式进行扩容，但是不能直接拷贝原数组的内容，因为随着数组长度发生改变，数组所挂链表的所有元素通过哈希函数计算的下标都有可能发生变化，所以我们需要遍历原来的所有元素，全部重新通过哈希函数计算对应扩容后数组映射的下标，并插入到新数组当中。

    /**
     * 扩容
     */
    private void resize() {
        //扩容需要对全部的元素进行重新哈希
        Node[] newArray = new Node[2 * usedSize];

        for (int i = 0; i < array.length; i++) {
            Node cur = array[i];
            //遍历全部结点元素重新哈希到另外一个数组上面
            while (cur != null) {
                int index = cur.key % newArray.length;
                //先保存原链表下一个结点
                Node next = cur.next;
                cur.next = newArray[index];
                newArray[index] = cur;
                cur = next;
            }
        }
        this.array = newArray;
    }

2.2.4哈希表查找的实现

这个就很简单了，我们只需要通过哈希函数和所给的key计算出对应数组的下标，然后遍历对象下标的链表，找到key相同的结点返回即可。

    public int get(int key) {
        int index = key % this.array.length;

        Node cur = array[index];
        while (cur != null) {
            if (cur.key == key) {
                return cur.value;
            }
            cur = cur.next;
        }
        return -1;
    }

2.3hashCode与equals

hashCode方法和equals方法都是Obect类中的方法，hashCode方法默认情况下根据对象的地址生成一个随机数，equals方法默认使用==比较两个对象的引用值或者基本数据类型的变量是否相等。

对于比较两个对象，我们一般是比较两个对象的内容是否相等（所以后所说的对象相等都是指对象的内容相等），而不是比较地址，所以说如果要实现两个对象内容的比较，需要重写equals方法，但是hashCode与equals有某种关系，所以重写equals方法的同时也需要重写hashCode方法。

hashCode与equals有以下关系：

• 使用hashCode方法计算出哈希值不相等的两个对象，则两个对象一定不相等。
• 使用equals方法得到两个对象相等，则这两个对象的哈希值一定相等。

如果只重写equals方法而不重写hashCode方法，如果存在两个内容相等但是地址不同的对象，就会出现hashCode得到两个对象的哈希值不同，但equals方法比较的结果是true，这就与hashCode与equals中的关系矛盾了。

2.4实现泛型哈希表

泛型实现哈希表与上面只实现只支持整型类型的哈希表其实没有很大的区别，就是将类改为泛型类，链表改为泛型链表。

代码中只需要将原哈希函数中的key改为hashCode(key)就可以了，意思就是根据key的哈希值确认对应的下标，毕竟对象不能直接取模，还有一点就是将使用==比较改为通过equals比较就可以了。

基本的实现逻辑没有发生变化。

基本属性： 类名为MyHashMap<K, V>。

    //默认哈希表初始数组大小16
    private final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
    //默认负载因子为0.75
    private final double DEFAULT_LOAD_FACTOR = 0.75;
    //元素个数
    private int usedSize;
    //链表+数组实现哈希表
    //定义结点
    static class Node<K, V> {
        public K key;
        public V value;
        public Node<K, V> next;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
    //链表数组
    public Node<K, V>[] array;
    
    public MyHashMap() {
        array = (Node<K, V>[]) (new Node[DEFAULT_INITIAL_CAPACITY]);
    }

插入put方法：

    public void put(K key, V value) {
        //获取下标
        int hash = key.hashCode();
        int index = hash % array.length;
        //查找是否具有重复的元素，使用equals判断是否相等
        Node<K, V> cur = array[index];
        while (cur != null) {
            if (cur.key.equals(key)) {
                cur.value = value;
                return;
            }
            cur = cur.next;
        }
        //如果没有重复的key则插入
        Node<K, V> node = new Node<>(key, value);
        node.next = array[index];
        array[index] = node;
        usedSize++;

        //检查负载因子是否需要扩容
        if (loadFactory() >= DEFAULT_LOAD_FACTOR) {
            resize();
        }
    }

扩容方法：

    /**
     * 获取当前的负载因子
     * @return
     */
    private double loadFactory() {
        return 1.0 * usedSize % array.length;
    }

    private void resize() {
        //扩容需要对全部的元素进行重新哈希
        Node<K, V>[] newArray = (Node<K, V>[]) new Node[2 * usedSize];

        for (int i = 0; i < array.length; i++) {
            Node<K, V> cur = array[i];
            //遍历全部结点元素重新哈希到另外一个数组上面
            while (cur != null) {
                int hash = cur.key.hashCode();
                int index = hash % newArray.length;
                Node<K, V> next = cur.next;
                cur.next = newArray[index];
                newArray[index] = cur;
                cur = next;
            }
        }
        this.array = newArray;
    }

获取元素get方法：

    public V get(K key) {
        int hash = key.hashCode();
        int index = hash % array.length;
        Node<K, V> cur = array[index];

        while (cur != null) {
            if (cur.key.equals(key)) {
                return cur.value;
            }
            cur = cur.next;
        }
        return null;
    }

---

下期预告：HashMap的底层原理