文章目录

    • 说一下HashMap的实现原理(非常重要)
      • ①HashMap的工作原理
      • HashMap存储结构
      • 常用的变量
      • HashMap 构造函数
        • tableSizeFor()
      • put()方法详解
      • hash()计算原理
      • resize() 扩容机制
      • get()方法
      • 为什么HashMap链表会形成死循环

说一下HashMap的实现原理(非常重要)

HashMap概述： HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。

HashMap的数据结构： 在Java编程语言中，最基本的结构就是两种，一个是数组，另外一个是模拟指针（引用），所有的数据结构都可以用这两个基本结构来构造的，HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体。

①HashMap的工作原理

HashMap基于hashing原理，我们通过put()和get()方法储存和获取对象。当我们将键值对传递给put()方法时，它调用键对象的hashCode()方法来计算hashcode，让后找到bucket位置来储存值对象。当获取对象时，通过键对象的equals()方法找到正确的键值对，然后返回值对象。HashMap使用链表来解决碰撞问题，当发生碰撞了，对象将会储存在链表的下一个节点中。 HashMap在每个链表节点中储存键值对对象。

HashMap存储结构

这里需要区分一下，JDK1.7和 JDK1.8之后的 HashMap 存储结构。在JDK1.7及之前，是用数组加链表的方式存储的。

但是，众所周知，当链表的长度特别长的时候，查询效率将直线下降，查询的时间复杂度为 O(n)。因此，JDK1.8 把它设计为达到一个特定的阈值之后，就将链表转化为红黑树。

这里简单说下红黑树的特点：

每个节点只有两种颜色：红色或者黑色
根节点必须是黑色
每个叶子节点（NIL）都是黑色的空节点
从根节点到叶子节点，不能出现两个连续的红色节点
从任一节点出发，到它下边的子节点的路径包含的黑色节点数目都相同
由于红黑树，是一个自平衡的二叉搜索树，因此可以使查询的时间复杂度降为O(logn)。（红黑树不是本文重点，不了解的童鞋可自行查阅相关资料哈）

常用的变量

在 HashMap源码中，比较重要的常用变量，主要有以下这些。还有两个内部类来表示普通链表的节点和红黑树节点

//默认的初始化容量为16，必须是2的n次幂static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16//最大容量为 2^30static final int MAXIMUM_CAPACITY = 1 << 30;//默认的加载因子0.75，乘以数组容量得到的值，用来表示元素个数达到多少时，需要扩容。//为什么设置 0.75 这个值呢，简单来说就是时间和空间的权衡。//若小于0.75如0.5，则数组长度达到一半大小就需要扩容，空间使用率大大降低，//若大于0.75如0.8，则会增大hash冲突的概率，影响查询效率。static final float DEFAULT_LOAD_FACTOR = 0.75f;//刚才提到了当链表长度过长时，会有一个阈值，超过这个阈值8就会转化为红黑树static final int TREEIFY_THRESHOLD = 8;//当红黑树上的元素个数，减少到6个时，就退化为链表static final int UNTREEIFY_THRESHOLD = 6;//链表转化为红黑树，除了有阈值的限制，还有另外一个限制，需要数组容量至少达到64，才会树化。//这是为了避免，数组扩容和树化阈值之间的冲突。static final int MIN_TREEIFY_CAPACITY = 64;//存放所有Node节点的数组transient Node<K,V>[] table;//存放所有的键值对transient Set<Map.Entry<K,V>> entrySet;//map中的实际键值对个数，即数组中元素个数transient int size;//每次结构改变时，都会自增，fail-fast机制，这是一种错误检测机制。//当迭代集合的时候，如果结构发生改变，则会发生 fail-fast，抛出异常。transient int modCount;//数组扩容阈值int threshold;//加载因子final float loadFactor;//普通单向链表节点类static class Node<K,V> implements Map.Entry<K,V> {//key的hash值，put和get的时候都需要用到它来确定元素在数组中的位置final int hash;final K key;V value;//指向单链表的下一个节点Node<K,V> next;Node(int hash, K key, V value, Node<K,V> next) {this.hash = hash;this.key = key;this.value = value;this.next = next;}}//转化为红黑树的节点类static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {//当前节点的父节点TreeNode<K,V> parent;//左孩子节点TreeNode<K,V> left;//右孩子节点TreeNode<K,V> right;//指向前一个节点TreeNode<K,V> prev;// needed to unlink next upon deletion//当前节点是红色或者黑色的标识boolean red;TreeNode(int hash, K key, V val, Node<K,V> next) {super(hash, key, val, next);}}

HashMap 构造函数

HashMap有四个构造函数可供我们使用，一起来看下：

//默认无参构造，指定一个默认的加载因子public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; }//可指定容量的有参构造，但是需要注意当前我们指定的容量并不一定就是实际的容量，下面会说public HashMap(int initialCapacity) {//同样使用默认加载因子this(initialCapacity, DEFAULT_LOAD_FACTOR);}//可指定容量和加载因子，但是笔者不建议自己手动指定非0.75的加载因子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;//这里就是把我们指定的容量改为一个大于它的的最小的2次幂值，如传过来的容量是14，则返回16//注意这里，按理说返回的值应该赋值给 capacity，即保证数组容量总是2的n次幂，为什么这里赋值给了 threshold 呢？//先卖个关子，等到 resize 的时候再说this.threshold = tableSizeFor(initialCapacity);}//可传入一个已有的mappublic HashMap(Map<? extends K, ? extends V> m) {this.loadFactor = DEFAULT_LOAD_FACTOR;putMapEntries(m, false);}//把传入的map里边的元素都加载到当前mapfinal void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {int s = m.size();if (s > 0) {if (table == null) { // pre-sizefloat ft = ((float)s / loadFactor) + 1.0F;int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY);if (t > threshold)threshold = tableSizeFor(t);}else if (s > threshold)resize();for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {K key = e.getKey();V value = e.getValue();//put方法的具体实现，后边讲putVal(hash(key), key, value, false, evict);}}}
tableSizeFor()

上边的第三个构造函数中，调用了 tableSizeFor 方法，这个方法是怎么实现的呢？

static final int tableSizeFor(int cap) {int n = cap - 1;n |= n >>> 1;n |= n >>> 2;n |= n >>> 4;n |= n >>> 8;n |= n >>> 16;return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;}

我们以传入参数为14 来举例，计算这个过程。

首先，14传进去之后先减1，n此时为13。然后是一系列的无符号右移运算。

//13的二进制0000 0000 0000 0000 0000 0000 0000 1101 //无右移1位，高位补00000 0000 0000 0000 0000 0000 0000 0110 //然后把它和原来的13做或运算得到，此时的n值0000 0000 0000 0000 0000 0000 0000 1111 //再以上边的值，右移2位0000 0000 0000 0000 0000 0000 0000 0011//然后和第一次或运算之后的 n 值再做或运算，此时得到的n值0000 0000 0000 0000 0000 0000 0000 1111...//我们会发现，再执行右移 4,8,16位，同样n的值不变//当n小于0时，返回1，否则判断是否大于最大容量，是的话返回最大容量，否则返回 n+1return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;//很明显我们这里返回的是 n+1 的值，0000 0000 0000 0000 0000 0000 0000 1111+ 10000 0000 0000 0000 0000 0000 0001 0000

将它转为十进制，就是 2^4 = 16 。我们会发现一个规律，以上的右移运算，最终会把最低位的值都转化为 1111 这样的结构，然后再加1，就是1 0000 这样的结构，它一定是 2的n次幂。因此，这个方法返回的就是大于当前传入值的最小（最接近当前值）的一个2的n次幂的值。

put()方法详解

//put方法，会先调用一个hash()方法，得到当前key的一个hash值，//用于确定当前key应该存放在数组的哪个下标位置//这里的 hash方法，我们姑且先认为是key.hashCode()，其实不是的，一会儿细讲public V put(K key, V value) {return putVal(hash(key), key, value, false, true);}//把hash值和当前的key，value传入进来//这里onlyIfAbsent如果为true，表明不能修改已经存在的值，因此我们传入false//evict只有在方法 afterNodeInsertion(boolean evict) { }用到，可以看到它是一个空实现，因此不用关注这个参数final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;//判断table是否为空，如果空的话，会先调用resize扩容if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;//根据当前key的hash值找到它在数组中的下标，判断当前下标位置是否已经存在元素，//若没有，则把key、value包装成Node节点，直接添加到此位置。// i = (n - 1) & hash 是计算下标位置的，为什么这样算，后边讲if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);else { //如果当前位置已经有元素了，分为三种情况。Node<K,V> e; K k;//1.当前位置元素的hash值等于传过来的hash，并且他们的key值也相等，//则把p赋值给e，跳转到①处，后续需要做值的覆盖处理if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;//2.如果当前是红黑树结构，则把它加入到红黑树 else if (p instanceof TreeNode)e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else {//3.说明此位置已存在元素，并且是普通链表结构，则采用尾插法，把新节点加入到链表尾部for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {//如果头结点的下一个节点为空，则插入新节点p.next = newNode(hash, key, value, null);//如果在插入的过程中，链表长度超过了8，则转化为红黑树if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);//插入成功之后，跳出循环，跳转到①处break;}//若在链表中找到了相同key的话，直接退出循环，跳转到①处if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}//①//说明发生了碰撞，e代表的是旧值，因此节点位置不变，但是需要替换为新值if (e != null) { // existing mapping for keyV oldValue = e.value;//用新值替换旧值，并返回旧值。if (!onlyIfAbsent || oldValue == null)e.value = value;//看方法名字即可知，这是在node被访问之后需要做的操作。其实此处是一个空实现，//只有在 LinkedHashMap才会实现，用于实现根据访问先后顺序对元素进行排序，hashmap不提供排序功能// Callbacks to allow LinkedHashMap post-actions//void afterNodeAccess(Node p) { }afterNodeAccess(e);return oldValue;}}//fail-fast机制++modCount;//如果当前数组中的元素个数超过阈值，则扩容if (++size > threshold)resize();//同样的空实现afterNodeInsertion(evict);return null;}

hash()计算原理

前面 put 方法中说到，需要先把当前key进行哈希处理，我们看下这个方法是怎么实现的。

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

运行一段程序，把它的 hashCode的二进制打印出来，如下。

public static void main(String[] args) {Object o = new Object();int hash = o.hashCode();System.out.println(hash);System.out.println(Integer.toBinaryString(hash));}//1836019240//1101101011011110110111000101000

然后，进行 (h = key.hashCode()) ^ (h >>> 16) 这一段运算。

//h原来的值0110 1101 0110 1111 0110 1110 0010 1000//无符号右移16位，其实相当于把低位16位舍去，只保留高16位0000 0000 0000 0000 0110 1101 0110 1111//然后高16位和原 h进行异或运算0110 1101 0110 1111 0110 1110 0010 1000^0000 0000 0000 0000 0110 1101 0110 1111=0110 1101 0110 1111 0000 0011 0100 0111

resize() 扩容机制

在上边 put 方法中，我们会发现，当数组为空的时候，会调用 resize 方法，当数组的 size 大于阈值的时候，也会调用 resize方法。 那么看下 resize 方法都做了哪些事情吧。

final Node<K,V>[] resize() {//旧数组Node<K,V>[] oldTab = table;//旧数组的容量int oldCap = (oldTab == null) ? 0 : oldTab.length;//旧数组的扩容阈值，注意看，这里取的是当前对象的 threshold 值，下边的第2种情况会用到。int oldThr = threshold;//初始化新数组的容量和阈值，分三种情况讨论。int newCap, newThr = 0;//1.当旧数组的容量大于0时，说明在这之前肯定调用过 resize扩容过一次，才会导致旧容量不为0。//为什么这样说呢，之前我在 tableSizeFor 卖了个关子，需要注意的是，它返回的值是赋给了 threshold 而不是 capacity。//我们在这之前，压根就没有在任何地方看到过，它给 capacity 赋初始值。if (oldCap > 0) {//容量达到了最大值if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}//新数组的容量和阈值都扩大原来的2倍else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // double threshold}//2.到这里，说明 oldCap  0，这就是 map 初始化的时候，第一次调用 resize的情况//而 oldThr的值等于 threshold，此时的 threshold 是通过 tableSizeFor 方法得到的一个2的n次幂的值(我们以16为例)。//因此，需要把 oldThr 的值，也就是 threshold ，赋值给新数组的容量 newCap，以保证数组的容量是2的n次幂。//所以我们可以得出结论，当map第一次 put 元素的时候，就会走到这个分支，把数组的容量设置为正确的值（2的n次幂)//但是，此时 threshold 的值也是2的n次幂，这不对啊，它应该是数组的容量乘以加载因子才对。别着急，这个会在③处理。else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;//3.到这里，说明 oldCap 和 oldThr 都是小于等于0的。也说明我们的map是通过默认无参构造来创建的，//于是，数组的容量和阈值都取默认值就可以了，即 16 和 12。else { // zero initial threshold signifies using defaultsnewCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}//③ 这里就是处理第2种情况，因为只有这种情况 newThr 才为0，//因此计算 newThr（用 newCap即16 乘以加载因子 0.75，得到 12） ，并把它赋值给 thresholdif (newThr == 0) {float ft = (float)newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}//赋予 threshold 正确的值，表示数组下次需要扩容的阈值（此时就把原来的 16 修正为了 12）。threshold = newThr;@SuppressWarnings({"rawtypes","unchecked"})//我们可以发现，在构造函数时，并没有创建数组，在第一次调用put方法，导致resize的时候，才会把数组创建出来。这是为了延迟加载，提高效率。Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];table = newTab;//如果原来的数组不为空，那么我们就需要把原来数组中的元素重新分配到新的数组中//如果是第2种情况，由于是第一次调用resize，此时数组肯定是空的，因此也就不需要重新分配元素。if (oldTab != null) {//遍历旧数组for (int j = 0; j < oldCap; ++j) {Node<K,V> e;//取到当前下标的第一个元素，如果存在，则分三种情况重新分配位置if ((e = oldTab[j]) != null) {oldTab[j] = null;//1.如果当前元素的下一个元素为空，则说明此处只有一个元素//则直接用它的hash()值和新数组的容量取模就可以了，得到新的下标位置。if (e.next == null)newTab[e.hash & (newCap - 1)] = e;//2.如果是红黑树结构，则拆分红黑树，必要时有可能退化为链表else if (e instanceof TreeNode)((TreeNode<K,V>)e).split(this, newTab, j, oldCap);//3.到这里说明，这是一个长度大于 1 的普通链表，则需要计算并//判断当前位置的链表是否需要移动到新的位置else { // preserve order// loHead 和 loTail 分别代表链表旧位置的头尾节点Node<K,V> loHead = null, loTail = null;// hiHead 和 hiTail 分别代表链表移动到新位置的头尾节点Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;do {next = e.next;//如果当前元素的hash值和oldCap做与运算为0，则原位置不变if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}//否则，需要移动到新的位置else {if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);//原位置不变的一条链表，数组下标不变if (loTail != null) {loTail.next = null;newTab[j] = loHead;}//移动到新位置的一条链表，数组下标为原下标加上旧数组的容量if (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead;}}}}}return newTab;}

上边还有一个非常重要的运算，我们没有讲解。就是下边这个判断，它用于把原来的普通链表拆分为两条链表，位置不变或者放在新的位置。

if ((e.hash & oldCap) == 0) {} else {}

get()方法

有了前面的基础，get方法就比较简单了。

public V get(Object key) {Node<K,V> e;//如果节点为空，则返回null，否则返回节点的value。这也说明，hashMap是支持value为null的。//因此，我们就明白了，为什么hashMap支持Key和value都为nullreturn (e = getNode(hash(key), key)) == null ? null : e.value;}final Node<K,V> getNode(int hash, Object key) {Node<K,V>[] tab; Node<K,V> first, e; int n; K k;//首先要确保数组不能为空，然后取到当前hash值计算出来的下标位置的第一个元素if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {//若hash值和key都相等，则说明我们要找的就是第一个元素，直接返回if (first.hash == hash && // always check first node((k = first.key) == key || (key != null && key.equals(k))))return first;//如果不是的话，就遍历当前链表（或红黑树）if ((e = first.next) != null) {//如果是红黑树结构，则找到当前key所在的节点位置if (first instanceof TreeNode)return ((TreeNode<K,V>)first).getTreeNode(hash, key);//如果是普通链表，则向后遍历查找，直到找到或者遍历到链表末尾为止。do {if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;} while ((e = e.next) != null);}}//否则，说明没有找到，返回nullreturn null;}

为什么HashMap链表会形成死循环

准确的讲应该是 JDK1.7 的 HashMap 链表会有死循环的可能，因为JDK1.7是采用的头插法，在多线程环境下有可能会使链表形成环状，从而导致死循环。JDK1.8做了改进，用的是尾插法，不会产生死循环。

那么，链表是怎么形成环状的呢？

关于这一点的解释，我发现网上文章抄来抄去的，而且都来自左耳朵耗子，更惊奇的是，连配图都是一模一样的。（别问我为什么知道，因为我也看过耗子叔的文章，哈哈。然而，菜鸡的我，那篇文章，并没有看懂。。。）

我实在看不下去了，于是一怒之下，就有了这篇文章。我会照着源码一步一步的分析变量之间的关系怎么变化的，并有配图哦。

我们从 put()方法开始，最终找到线程不安全的那个方法。这里省略中间不重要的过程，我只把方法的跳转流程贴出来：

//添加元素方法 -> 添加新节点方法 -> 扩容方法 -> 把原数组元素重新分配到新数组中put()--> addEntry()--> resize() -->transfer()

问题就发生在 transfer 这个方法中。

我们假设，原数组容量只有2，其中一条链表上有两个元素 A,B，如下图

现在，有两个线程都执行 transfer 方法。每个线程都会在它们自己的工作内存生成一个newTable 的数组，用于存储变化后的链表，它们互不影响（这里互不影响，指的是两个新数组本身互不影响）。但是，需要注意的是，它们操作的数据却是同一份。

因为，真正的数组中的内容在堆中存储，它们指向的是同一份数据内容。就相当于，有两个不同的引用 X，Y，但是它们都指向同一个对象 Z。这里 X、Y就是两个线程不同的新数组，Z就是堆中的A，B 等元素对象。

假设线程一执行到了上图1中所指的代码①处，恰好 CPU 时间片到了，线程被挂起，不能继续执行了。 记住此时，线程一中记录的 e = A ， e.next = B。

然后线程二正常执行，扩容后的数组长度为 4， 假设 A，B两个元素又碰撞到了同一个桶中。然后，通过几次 while 循环后，采用头插法，最终呈现的结构如下：

此时，线程一解挂，继续往下执行。注意，此时线程一，记录的还是 e = A，e.next = B，因为它还未感知到最新的变化。

我们主要关注图1中标注的①②③④处的变量变化：

/*** next = e.next* e.next = newTable[i]* newTable[i] = e;* e = next;*///第一次循环,(伪代码)e=A;next=B;e.next=null //此时线程一的新数组刚初始化完成，还没有元素newTab[i] = A->null //把A节点头插到新数组中e=B; //下次循环的e值

第一次循环结束后，线程一新数组的结构如下图：

然后，由于 e=B，不为空，进入第二次循环。

//第二次循环e=B;next=A;//此时A，B的内容已经被线程二修改为 B->A->null，然后被线程一读到，所以B的下一个节点指向Ae.next=A->null// A->null 为第一次循环后线程一新数组的结构newTab[i] = B->A->null //新节点B插入之后，线程一新数组的结构e=A;//下次循环的 e 值

第二次循环结束后，线程一新数组的结构如下图：

此时，由于 e=A，不为空，继续循环。

这时，有的同学可能就会问了，就算他们成环了，又怎样，跟死循环有什么关系？

我们看下 get() 方法（最终调用 getEntry 方法），

可以看到查找元素时，只要 e 不为空，就会一直循环查找下去。若有某个元素 C 的 hash 值也落在了和 A，B元素同一个桶中，则会由于， A，B互相指向，e.next 永远不为空，就会形成死循环。