【Java集合】之HashMap详解

ゝ一纸荒年。 2023-02-22 10:46 19阅读 0赞

***小王，听说你对HashMap很熟悉呀，可以说说它的数据结构和底层原理吗？***

好的，没问题！我们知道 HashMap 是我们非常常用的数据结构，由**数组和链表组合构成**的数据结构，数组里面每个地方都存了Key-Value这样的实例，在Java7叫Entry在Java8中叫Node，因为他本身所有的位置都为null，在put插入的时候会根据key的hash去计算一个index值。

***你提到的还有链表，为啥需要链表，链表又是怎么样子的呢？***

我们都知道数组长度是有限的，在有限的长度里面我们使用哈希，哈希本身就存在概率性，也就是说当hash值一样的时候，就形成了链表。每一个节点都会保存自身的hash、key、value、以及下个节点，我们来看看Node的源码：

static class Node<K,V> implements Map.Entry<K,V> { 
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
        ...
    }

***说到链表我想问一下，你知道新的Entry节点在插入链表的时候，是怎么插入的么？***

**Java8之前是头插法**，就是说新来的值会取代原有的值，原有的值就顺推到链表中去，就像上面的例子一样，因为写这个代码的作者认为后来的值被查找的可能性更大一点，提升查找的效率。

但是，**在java8之后，都是使用尾部插入了。**

***为啥改为尾部插入呢？***

这个要从HashMap的扩容机制说起，我们知道，HashMap的数组容量是有限的，数据多次插入的，到达一定的数量就会进行扩容，也就是resize，而影响扩容的因素有两个：

*  Capacity：HashMap当前长度
 *  LoadFactor：负载因子，默认值0.75f

怎么理解呢，就比如当前的容量大小为100，当你存进第76个的时候，判断发现需要进行resize了，那就进行扩容，但是HashMap的扩容也不是简单的扩大点容量这么简单的，它分为两步：

*  扩容：创建一个新的Entry空数组，长度是原数组的2倍
 *  ReHash：遍历原Entry数组，把所有的Entry重新Hash到新数组

***等一下，为什么要重新Hash呢，直接复制过去不行么？***

额。。。这是因为长度扩大以后，Hash的规则也随之改变：

Hash的公式 ==> index = HashCode（Key） & （Length - 1）

原来长度（Length）是8你位运算出来的值是2 ，新的长度是16你位运算出来的值明显不一样了。

好了，说完扩容机制后，我们来解释一下为什么 Java8 之后改成尾插法了。由于resize的赋值方式，也就是使用了**单链表的头插入方式，同一位置上新元素总会被放在链表的头部位置**，在旧数组中同一条Entry链上的元素，通过重新计算索引位置后，有可能被放到了新数组的不同位置上，一旦几个线程都调整完成，就可能出现环形链表，如果这个时候去取值，就会出现无限循环(Infinite Loop)。

但是如果**使用尾插**，在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题了，而且因为**Java8之后链表有红黑树**的部分，大家可以看到代码已经多了很多if else的逻辑判断了，红黑树的引入巧妙的将原本O(n)的时间复杂度降低到了O(logn)。

**所以，Java7在多线程操作HashMap时可能引起死循环，原因是扩容转移后前后链表顺序倒置，在转移过程中修改了原来链表中节点的引用关系，而Java7在多线程操作HashMap时可能引起死循环，原因是扩容转移后前后链表顺序倒置，在转移过程中修改了原来链表中节点的引用关系。**

***那是不是意味着Java8就可以把HashMap用在多线程中呢？***

我认为即使不会出现死循环，但是通过源码看到put/get方法都没有加同步锁，多线程情况最容易出现的就是：无法保证上一秒put的值，下一秒get的时候还是原值，所以线程安全还是无法保证。

***那你知道HashMap的默认初始化长度是多少吗？***

/** * The default initial capacity - MUST be a power of two. */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

从源码中我们可以看到初始化大小是16

***你那知道为啥是16么？***

从源码中我们可以看到，初始容量使用的是位运算 1 << 4，而不是直接写16，这样是为了位运算的方便，**位与运算比算数计算的效率高了很多**，之所以选择16，是为了服务将Key映射到index的算法。

前面说了所有的key我们都会拿到他的hash，但是我们怎么尽可能的得到一个均匀分布的hash呢？答案是我们通过Key的HashCode值去做位运算，我们再看下index的计算公式：

index = HashCode（Key） & （Length- 1）

15的的二进制是1111，那10111011000010110100 &1111 十进制就是4