【Java 数据结构】HashMap和HashSet

- 日理万妓 2024-03-30 12:08 104阅读 0赞

![9278cc61d75a4b64a907ad074e5f4545.gif][]

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

**目录**

1、认识 HashMap 和 HashSet

2、哈希表

2.1 什么是哈希表

2.2 哈希冲突

2.2.1 概念

2.2.2 设计合理哈希函数 - 避免冲突

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

2.2.4 Java中解决哈希冲突 - 开散列/哈希桶

3、HashMap 的部分源码解读

3.1 HashMap 的构造方法

3.2 HashMap 是如何插入元素的？

3.3 哈希表下的链表，何时会树化？

4、相关面试题

4.1 链表转换成红黑树如何比较？

4.2 hashCode 和 equals 的区别

4.3 以下代码分配的内存是多少？

5、性能分析

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

## **1、认识 HashMap 和 HashSet** ##

![33f111bef7ad43aca354e253ce2e9a33.png][]

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

在上期中，学习到 TreeMap 和 TreeSet，因为他们实现了 SortedMap 和 SortedSet 接口(本质是 实现了 NavigableMap 和 NavigableSet)，表示你创建的 TreeMap 或 TreeSet，必须是可排序的，也就是里面的元素是可比较的。

HashSet 的底层也是 HashMap，跟上期 TreeSet 大同小异，感兴趣可以去看看源码。

本期的 HashMap 和 HashSet 并没有继承上述所说的俩个接口，也即表示 HashMap 和 HashSet 中的 key 可以不重写 compareTo 方法，由此也能得出，**HashMap 与 HashSet 不关于 key 有序！**

因为 Set 的底层就是 Map，那么这里我们就来验证下 TreeSet 关于 key 有序，而 HashSet 不关于 key 有序。

public class Test {
        public static void main(String[] args) {
            Set<String> treeSet = new TreeSet<>();
            Set<String> hashSet = new HashSet<>();;
            treeSet.add("0012");
            treeSet.add("0083");
            treeSet.add("0032");
            treeSet.add("0057");
            System.out.print("TreeSet: ");
            for (String s : treeSet) {
                System.out.print(s + " ");
            }
            hashSet.add("0012");
            hashSet.add("0083");
            hashSet.add("0032");
            hashSet.add("0057");
            System.out.print("\nHashSet: ");
            for (String s : hashSet) {
                System.out.print(s + " ");
            }
        }
    }

**打印结果：**

![a5e06eba45de4051907552760824cf4d.png][]

为什么 HashMap 和 HashSet 不关于 key 有序呢？随着往文章后续学习，你就会明白。

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

## **2、哈希表** ##

### 2.1 什么是哈希表 ###

之前的学习中，如果我们要查找一个元素，肯定是要经过比较的，那有没有一种办法，可以不用经过比较，直接就能拿到呢？

如果我们能构造一种存储结构，通过一种函数 (hashFunc) 使元素的存储位置与函数得出的关键码之间能够建立一一映射的关系，那么在查找某个元素的时候，就能通过这个函数来很快的找到该元素所在的位置。

**这种函数就叫做哈希(散列)函数，上述所说构造出来的结构，叫做哈希表或者称为散列表。**

![ea0900cb46ef4ca682bc359b6ae2f7b8.png][]

**插入元素的时候：**根据元素的关键码，Person中关键码可能是 age，这个具体情况具体分析，上述例子只是在插入整型的时候，通过关键码通过哈希函数得到的 **index** 就是要插入的位置。

**搜索元素的时候：**对元素的关键码，通过哈希函数得出的 **index** 位置，与该位置的关键码比较，若俩个关键码相同，则搜索成功。

采取上面的方法，确实能避免多次关键码的比较，搜索的效率也提高的，但是问题来了，拿上述图的情况来举例子的话，我接着还要插入一个元素 15，该怎么办呢？

### 2.2 哈希冲突 ###

#### 2.2.1 概念 ####

接着上面的例子来说，如果要插入 15，使用哈希函数出来的 index = 5，但是此时的 5，下标的位置已经有元素存在了，这种情况我们就称为哈希冲突！

简单来说，不同的关键字通过相同的哈希函数计算出相同的哈希地址（前面我们称为 index），这种现象就被称为**哈希冲突**或**哈希碰撞！**

#### 2.2.2 设计合理哈希函数 - 避免冲突 ####

如果哈希函数设计的不够合理，是可能会引起哈希冲突的。

哈希函数的定义域，必须包括所需存储的全部关键码，哈希函数计算出来的地址，应能均匀的分布在整个空间中，哈希函数不能设计太过于复杂。(工作中一般用不着我们亲自设计)

**常见的哈希函数：**

**直接定制法：**取关键字的某个线性函数作为哈希地址：**hash = A \* key + B**， 这样比较简单，但是需要事先知道关键字的分布情况，适合于查找比较小且连续的情况。

**除留余数法：**设哈希表中允许的地址数为 m，取一个不大于 m 的数，但接近或等于 m 的质数 p 作为除数，即哈希函数：**hash = key % p**，(p <= m)。

还有其他的方法感兴趣可以查阅下相关资料，这两个只是比较常见的方法了，当然，就算哈希函数设计的再优秀，只是产生哈希的冲突概率没那么高，但是仍然避免不了哈希冲突的问题，于是又有了一个降低冲突概率的办法，调节负载因子。

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

> **负载因子 α = 哈希表中元素个数 / 哈希表的长度**

哈希表的长度没有扩容是定长的，即 α 与 元素的个数是成正比的，当 α 越大，即代码哈希表中的元素个数越多，元素越多，发生哈希冲突的概率就增加了，因此 α 越小，哈希冲突的概率也就越小。所以我们应该严格控制负载因子的大小，在 Java 中，限制了负载因子最大为 0.75，当超过了这个值，就要进行扩容哈希表，重新哈希(重新将各个元素放在新的位置上)。

**所以负载因子越大，冲突率越高，我们就需要降低负载因子来变相的降低冲突率，哈希表中元素个数不能改变，所以只能给哈希表扩容了。**

#### 2.2.4 Java中解决哈希冲突 - 开散列/哈希桶 ####

上面讲述的都是避免冲突的方法，其实还往往不够，不管怎么避免，还是会有冲突的可能性，那么通常我们解决哈希冲突有两种办法，分别是 **闭散列** 和 **开散列** 那么今天我们主要介绍 Java 中的开散列是如何解决的，感兴趣可以下来自己了解下闭散列。

**开散列又叫链地址法，或开链法，其实简单来说就是一个数组加链表的结构。如图：**

![19dfd3d05db6411ca90525c9711f81fc.png][]如上图我们可得出，通过哈希函数得出的地址相同的关键码放在一起，这样的每个子集合称为桶，接着桶中的元素用链表的结构组织起来，，每个链表的头节点存放在哈希表中。

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

## **3、HashMap 的部分源码解读** ##

### 3.1 HashMap 的构造方法 ###

public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }
    
    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }
    
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
    
    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                    initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                    loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }

这几个构造方法相信都不难理解，第一个无参构造方法，默认负载因子是 0.75，第二个构造方法是你可以传一个 Map 进去，构造出一个新的 Map，负载因子仍然是默认的 0.75， 第三个构造方法就是指定开辟的容量了(并不是你想象那样简单哦，面试题讲解)，这个很简单，第四个构造方法指定容量并且自定义负载因子。

**在 HashMap 中，实例化对象的时候并不会默认开辟空间(指定空间除外)。**

### 3.2 HashMap 是如何插入元素的？ ###

前面对 HashMap 的讲解，已经大概了解了一点，但是 HashMap 底层的哈希函数是如何设定的呢？而且 Map 中不能有重复值的情况，是利用什么来判断这两个值是相同的值呢？

这里我们通过查看 put 方法的源码，来带大家一层层揭开这个面纱：

public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

进入到 put 方法，随之调用了 putVal 方法，而第一个参数就是我们哈希函数的实现了，我们转到hash() 方法中：

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

通过哈希函数，能看出，首先调用 key 的hashCode 方法，接着无符号右移 16 位，即将 key 的高16位 与 低 16位 异或得到的 hash 值，通过这个也就在说明，我们如果是自定义类型的话，比如 Person，那么一定要重写 hashCode 方法，不然则是调用 Object 里的 hashCode 方法了。

接着我们再往下看，putVal 方法里面的逻辑，这里代码比较长，我们分段演示：

![d442cdbbd7c14c729bd42c699287e098.png][]

这里就是判断哈希表是否为有元素，如果表为 null 或者 哈希表的长度为 0，就会初始化数组(Node类型的数组)，即调用 resize() 方法。初始哈希表的长度是 16，临界阈值为 16 \* 0.75 = 12，也就是数组元素达到 12个即会扩容。往后走代码：

![1fac046efc71435e9ee152b527dc87d7.png][]

这里作用是通过 hash 值得到索引 i，也就是数组的下标，判断这个位置是否有元素了，如果没有则直接 new 一个节点放到该处。反之走 else 就表示该数组下标已经有元素了。

![a0a7f98b3ff8447f99abf3c627cd0b14.png][]

如果得到的 i 索引处有元素，则需要判断当前下标元素的 hash 值是否与我们要插入的元素 hash 值相同，如果相同，接着判断 下标元素的 key 与我们要插入元素的 key一样，或者通过 equals 方法比较是一样了，则表示是同一个元素，则不用插入了，e 保存这个已经存在的元素。到这里也能发现，这其实就是 Map 底层不能有重复 key 的原因了。

那如果他们不相同的情况下，就会判断该下标 i 的位置值是不是红黑树的节点(到了一定条件哈希桶中的元素会采用红黑树来组织数据)，如果是，则采用红黑树的方式进行插入元素，这里我们就不往里面看了。

最后都不满足的情况，也就是元素不相同，并且不是红黑树结构，则走后面的 else，首先这个 else 里面是个死循环，要想退出，必须满足两个条件，① 找到了可以插入的地方，② 在哈希桶中发现了相同的元素。

比较该数组索引 i 下标的下一个节点，如果为 null，则直接插入该节点，如果链表长度大于8，则可能需要树化，也就是转换成红黑树，如果找到了相同的 key，则不用插入直接跳出循环。

上面的 else 走完后，如果存在添加相同的元素的时候，e 则不为 null，只需要将待添加元素的 value 值赋值给原本存在元素的 value 值即可，也就是更新一下元素的 value 值。afterNodeAccess 方法不用管，是使用 LinkedHashMap 实现的一个操作，这里并没有使用。

最后部分：

![c5e228414f9c4b388c0a134af2756731.png][]

这里有效元素个数自增，如果超过了数组长度，则重新判断是否扩容（两倍扩容）。 afterNodeInsertion 也不用管，LinkedHashMap中的，这里也没有实际用途。

> **总结：HashMap 的 put 方法，是根据 key 的 hashCode 来计算 hash 值的，即我们要在自定义类型中重写 HashCode 方法，再者，是根据 equals 来判断 key 是否相同，也表示着我们同时需要去重写 equals 方法。**

### 3.3 哈希表下的链表，何时会树化？ ###

在上述讲解 put 方法的时候，发现插入元素的时候，数组索引位置的链表不止一个元素的时候会判断是否要转换成红黑树，那么具体要达到什么条件才能转换成红黑树呢？我们直接看上述的 treeifyBin 方法即可。

![97fda9d4229e46bca48be44305c52aaf.png][]树化的前提是，链表的长度大于等于 8，就会树化，因为是从 binCount 是从 0 开始的，所以 TREEIFY\_THRESHOLD - 1。那么链表的长度大于等于 8，一定会从链表变成红黑树吗？我们往后看：

![80db7bcb192e4003882bc862d75ebe30.png][]

第一个 if 当哈希表为空，或者表(数组)的长度小于64，只进行扩容即可，不会转换成树，当哈希表的长度大于 64，才有可能转换成红黑树。

所以我们最终得出，HashMap 中哈希表下的链表，当链表长度大于等于 8，并且哈希表的长度大于等于 64 则会将此链表转换成红黑树。

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

## **4、相关面试题** ##

### 4.1 链表转换成红黑树如何比较？ ###

前面我们学过 TreeMap TreeSet 底层就是红黑树，里面的元素必须是可比较的，那哈希表下的链表转换成红黑树之后，没有重写 compareTo 怎么办呢？这里会按照 key 的哈希值来进行比较，所以就算转换成红黑树后，也不会关于 key 有序，再者可能只是哈希表其中一个索引位置下的结构是红黑树，其他的仍然可能是链表。

### 4.2 hashCode 和 equals 的区别 ###

hashCode 是虚拟出对象的地址，底层是 native 封装的，即 C/C++实现的，而 equals 则是比较两个对象是否相同。

当我们重写 hashCode 的时候，是调用 Objects 里面的 hash 方法：

@Override
    public int hashCode() {
        return Objects.hash(name, age);
    }

举个例子，person1 和 person2 两个对象的 hashCode 完全不一样，但通过 hash 函数得到的 hash 值是相同的！而 hashCode 也是通过 hash 出来的，即对象的 hashCode 可以称为 hash 值，所以得出，两个对象的 hashCode 相同，但是这两个对象不一定相同。

对于 persong1.equals(person2) 的值为 true 的情况，则代表这两个对象里面的值都是一样的，所以 equals 为 ture，两个一模一样的对象，最终的 hash 值肯定也是一样的，并且 HashMap 也是调用 key 中的 equals() 方式来进行判断是否有重复的 key 值。

@Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Person person = (Person) o;
        return age == person.age &&
                Objects.equals(name, person.name);
    }

**总结：**

两个对象的 HashCode 相同，不代表这两个对象完全相同。

两个对象的 equals 的结果为 true，则代表这两个对象完全相同。

### 4.3 以下代码分配的内存是多少？ ###

public static void main(String[] args) {
        Map<Integer, Integer> map = new HashMap<>(25);
    }

如果你天真的回答是 25 个数组元素大小，那就错了，我们点进去构造方法，发现是调用另一个构造方法，在接着点进去，看到最后一行代码即 tableSizeFor 方法：

![6e6884a161b8472abc7ef68ad0f671a2.png][]

这里就没必要慢慢算了，实际就是给你找到一个离 cap 最近的 2 的 n 次方数，取值范围得大于等于 cap，例如上述 25 则实际开辟的就是 1 2 4 8 16 **32** 64....，那么上述代码实际开辟的大小就是 32 个数组空间大小。

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

## **5、性能分析** ##

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

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

**下期预告：【Java 数据结构】模拟实现HashMap**

[9278cc61d75a4b64a907ad074e5f4545.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/216161325f024e0daebf3439dfa9b09c.gif
[33f111bef7ad43aca354e253ce2e9a33.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/22153a42d7d344ba819f09e1841e1e9e.png
[a5e06eba45de4051907552760824cf4d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/91e2abbf79704ac6a20d62027dd3aa70.png
[ea0900cb46ef4ca682bc359b6ae2f7b8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/404af85fbb344d18af2ae8a63c87804e.png
[19dfd3d05db6411ca90525c9711f81fc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/07013f3e6c49420eb7639bca4ca90a9e.png
[d442cdbbd7c14c729bd42c699287e098.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/2506e4b247934698a3745aea953eff16.png
[1fac046efc71435e9ee152b527dc87d7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/24842507582d46e68bef72f6421f5cbe.png
[a0a7f98b3ff8447f99abf3c627cd0b14.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/6c7949308e824248bcac46749f06f243.png
[c5e228414f9c4b388c0a134af2756731.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/df328bd9359042e590e56560c3882f2b.png
[97fda9d4229e46bca48be44305c52aaf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/fff6e8ac0e9d47078cdae392213571d2.png
[80db7bcb192e4003882bc862d75ebe30.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/35b63060895143b18bc50567d7f30bc9.png
[6e6884a161b8472abc7ef68ad0f671a2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/4d3e4354f25c4eaea40fbbe09221b889.png