Java-数据结构-(HashMap HashSet)

一、Tree和Hash的区别

在上一篇文章中，我们讲到了"TreeMap"和"TreeSet"，但当我们刷题的时候却会发现，实际应用Map和Set时，却常常都只会用"HashMap"和"HashSet"，这是为什么呢？

① 效率不同

📚"TreeMap"和"TreeSet"：

都是基于"红黑树"实现的，这种方法的实现就导致了无法直接查询到存储进去的数据，而是需要进去不断的查找，即便已经有了非常好的优化，树的遍历效率也只能达到O(logn)。

📚"HashMap"和"HashSet"：

是基于哈希表实现的，一般使用HashMap和HashSet进行存入和查找时，时间复杂度都能达到O(1)。

而这种效率是远远高于O(logn)的，并且平时刷题时测试用例中都有大量难缠的数据，所以平时"Hash"的应用场景是多于"Tree"的。

② 适用场景不同

📚 "TreeMap"和"TreeSet"：

这种数据结构会对存入的数据自动进行排序，适用于数据规模不太大，或者需要有序数据或范围查询时，使用TreeMap是一个很好的选择。

这里使用HashMap是没办法使用该方法的，因为HashMap并不会对数据进行排序。

📚"HashMap"和"HashSet"：

相对的，哈希表能做到快速存入和查询，肯定也有对应的缺点，那就是"不会对存入的数据进行自动排序"

但是实际中，对Map和Set的使用还是以"存入和查询"居多，所以"HashMap"和"HashSet"的使用还是会更多的。

二、哈希表

① 什么是哈希表？

通过上面我们能了解到，哈希表的存入和查询速率都是O(1)。

O(1)是什么概念？就是比较的次数非常少，甚至有时候可以忽略不计。

那么让我们回顾一下，之前学习的"排序算法"中，就有这么一种比较次数非常少的排序—"桶排序"
在哈希表的实现中，也使用了类似"桶排序"中的一种思想—"分桶的核心思想"

📕 分桶：哈希表通过某种规则将数据分散到多个容器(桶)中。

📕 映射规则：哈希表通过哈希函数映射键到桶。

哈希表除了使用了这种类似桶排序的分桶思想，剩下的操作比较类似于"计数排序"

📕 插入元素：根据待插入元素的关键码，计算出元素的存储位置。

📕 搜索元素：同样对关键码进行运算，并查找该位置，若关键码相同则搜索成功。

而其中对关键码进行操作就是通过"哈希函数"来进行转换的。

比如此时我们将哈希函数设置为：int index = key % elem.length;
那么对于元素的处理就会像这样：

在这个存储过程中我们可以发现，并没有元素进行比较。这就是一种最理想的状态。但让我们再想想，如果再往表中插入14呢？24呢？34、44呢？

② 哈希冲突的概念

上面我们提到，如果在表中继续插入元素，如"14"，"24"，"34"等。它们经过哈希函数后，得到的对应位置与先前存入的"4"是一样的。

而这也就是"不理想的情况"，因为遇到这种情况，我们的哈希表就需要进行"元素之间的比较"了，这种情况也被称为"哈希冲突"。

③ 哈希冲突的避免

我们要知道，使用哈希表进行数据的存储时，造成"哈希冲突"是必然的。

因为理想状态下我们通过哈希函数，计算每个数据的对应键值并将数据存入哈希表中，但这也就意味着肯定会有些数据会计算出相同的键值，并且哈希表的空间也是有限的(未扩容之前)，当存入的数据达到一定的限度，则会出现"经常发生哈希冲突"的情况。

而为了避免这种情况发生，我们能做到的就是：尽量设计一个合理的哈希函数。

哈希函数设计原则：

📕 哈希函数的定义域必须包括需要存储的全部关键码，如果表中允许有n个地址，则哈希函数的值域必须在0到n-1之间

📕 哈希函数计算的值最好能均匀分布在整个空间中

④ 常见的哈希函数

📚 直接定制法：Hash(Key) = A * Key + B

优点：简单、均匀
缺点：需要事先知道关键字的分布情况使用场景

📚 除留余数法：Hash(key) = key % p(p<=m)

⑤ 负载因子调节

上面我们提到过：

哈希表的空间也是有限的(未扩容之前)，当存入的数据达到一定的限度，则会出现"经常发生哈希冲突"的情况。

这种情况会大大降低我们的哈希表的存取效率，而为了避免这种情况发生，我们就需要在每次存入数据时，计算一下此时哈希表的负载因子，如果此时的负载因子超过了我们希望的限定值，那么此时我们将对哈希表进行扩容。

1. 负载因子的定义

负载因子：表示哈希表中已存储元素数量与当前总容量的比值

如：此时哈希表容量为 10 ，已存入 7 个元素，则此时的负载因子为 0.7 。

2. 负载因子的作用

📕 衡量哈希表填充程度：

负载因子越高，哈希表填充越满，发生哈希冲突的概率越大。

📕 触发扩容的阈值：

当负载因子超过预设值(java中默认为0.75,后续我们模拟实现哈希表也会采取这个阈值)时，哈希表自动扩容，以降低冲突概率。

📕 平衡时间与空间开销：

低负载因子：冲突少，操作效率高，但内存利用率低。
高负载因子：内存利用率高，但冲突频繁，操作效率下降。

⑥ 冲突的解决方案(开放寻址法)

1. 线性探测

📕 规则：

若当前的桶已经被占用，则顺序查询下一个桶(如 index = (index + 1) % size)，直到找到空桶。

📕 优点：实现简单，空间利用率高，缓存性能好(连续存储)。

📕 缺点：产生聚集现象(大量连续占用桶)，导致查找效率下降。

📕 适用场景：负载因子较低时。

2. 二次探测

📕 规则：

使用第二个哈希函数计算下一个空位置(如：index1 = (index0 + i ^ 2) % m)

📕 优点：冲突分布更均匀，减少聚集。

📕 缺点：装载因子不能太大，否则性能会急剧下降，容易发生二次聚集。

📕 适用场景：对性能要求高的场景。

⑦ 冲突的解决方案(链地址法)

又叫做"开散列法"，我们需要对传进的数据关键码通过散列函数计算出散列地址，将具有相同地址的关键码放入同一个子集合中，每一个子集合都是一个桶，每个桶中的元素都通过一个单链表进行连接，然后将每个链表的结点都存储在哈希表中。

三、哈希表的模拟实现

① 基本框架

在这里我们采用"开散列法"

所以我们需要用到链表结构，因此我们需要在基本框架中实现一个结点类

同时，我们还需要设定一个触发扩容的阈值(负载因子)，上面我们提到java中默认为0.75，所以我们这里也使用0.75作为触发扩容的阈值。

📖 代码示例：

public class HashBucket {
    public static class Node {
        public int key;
        public int val;
        public Node next;
        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
   }
   //初始哈希表
    public Node[] elem = new Node[10];
    public int usedSize;
    //负载因子
    public static final double LOAD_FACTOR = 0.75;
}

② 插入元素

实现插入元素，我们需要考虑很多种情况，比如：如何避免哈希冲突，将结点插入链表的何处，在何时计算负载因子，如何进行扩容等。

这里我们一个个的进行讲解：

📕 如何避免哈希冲突：

我们采用"开散列法"，首先通过哈希函数寻找对应链表的index：

int index = key % elem.length;

然后判断当前index指向的链表中是否含有key，如果存在key，则修改结点的值为新的val。

📕 将结点插入链表何处：

如果不存在key，则将新节点插入链表(尾插和头插都可以，这里我们采取头插法)

📕 在何时计算负载因子：

当新元素加入后，计算此时的负载因子，如果超过阈值则扩容

📖 代码示例：

    //新增元素
    public void put(int key,int val){
        //1.通过哈希函数,找到对应链表的index
        int index = key % elem.length;
        //2.判断当前的链表是否有key
        Node cur = elem[index];
        while(cur != null){
            //3.找到key,修改改结点的val
            if(cur.key == key){
                cur.val = val;
                return;
            }
            cur = cur.next;
        }
        //4.如果没有key,则将新结点插入链表(这里采取头插法)
        Node newCur = new Node(key,val);
        newCur.next = elem[index];
        elem[index] = newCur;
        usedSize++;
        //5.计算当前的负载因子,如果超过则扩容
        if(getLoadFactor() >= LOAD_FACTOR){
            upsize();
        }
   }
   //计算当前负载因子
    public double getLoadFactor(){
        return usedSize * 1.0 / elem.length;
    }

③ 哈希表扩容

当为哈希表进行扩容时，并不是简单的将数组大小扩大一倍即可，因为可能会发生如下情况：

当扩容之后，其实14应该放在新的空间14内，而不是还处在4的位置，所以哈希表的扩容其实是一个(再次哈希)的过程，这个过程的时间复杂度是O(n)的，需要我们遍历所有元素，重新创建一个哈希表：

📖 代码示例：

    //哈希表扩容(再次哈希)
    public void upsize(){
        //1.创建新的哈希表
        Node[] newElem = new Node[elem.length * 2];
        for(int i = 0;i < elem.length;i++){
            Node cur = elem[i];
            while(cur != null){
                Node curN = cur.next;
                int index = cur.key % newElem.length;
                cur.next = newElem[index];
                newElem[index] = cur;
                cur = curN;
            }
        }
        elem = newElem;
    }

④ 获取元素

这个就很简单了，经过之前我们对各种数据结构的学习，对于大家来说肯定也是不必多说，只需要计算出对应链表的index并遍历链表求目标元素即可。

📖 代码示例：

    //通过key获取元素
    public int get(int key) {
        //找到key的对应下标
        int index = key % elem.length;
        Node cur = elem[index];
        //查找链表
        while (cur != null) {
            if (cur.key == key) {
                return cur.val;
            }
            cur = cur.next;
        }
        return -1;
    }

⑤ 测试

我们设定初始大小为10，扩容阈值为0.75，此时我们向哈希表中存入八个元素：

当存储到14时，14存在index = 4的链表中：

当存入第八个元素，也就是19的时候，就会触发扩容，此时我们的14应该从index = 4的链表，移动到新的index = 14的位置上：

四、自定义类使用哈希表

📖 People：

class People {
    public int id;
    public String name;
    public People(int id,String name) {
        this.id = id;
        this.name = name;
    }
}

有些时候，我们希望对自定义的一些类也是使用哈希表进行存储，但是有时会发生这样的情况：