Java-HashMap详解

发表于 分类于

HashMap是常用的用于存储key-value键值对数据的一个集合，底层是基于对Map的接口实现。每一个键值对又叫Entry，这些Entry分散的存储在一个由数组和链表组成的集合中。当然在Java8中，Entry变成了Node。

HashMap的数据结构

table数组

首先我们要知道，我们存在HashMap中的数据最终是存了什么地方，就是如下的结构。

1
transient HashMap.Node<K, V>[] table;

可能有人看到transient有些陌生，被这个关键字修饰的变量将不会被序列化。简单来说，就是序列化之后这个字段的值就会被干掉，用于一些不需要传递给第三方的字段。
例如一个矩形，在本地使用的时候，有长、宽和面积三个属性，但是你要把这个对象给第三方用，但是由于面积可以通过另外两个属性推导出来，这个key就不需要传递给第三方了。这种情况就可以用transient关键字修饰。总的来说就是，被transient修饰的变量将不再参与序列化。

Node节点

下面是Node节点的定义。

1
2
3
4
5
6
7
static class Node<K,V> implements Map.Entry<K,V> {
   final int hash;
   final K key;
   V value;
   Node<K,V> next;
   .....
}

上面的代码省略了一些Getter和Setter，结构还是非常清晰和简单。可以看到这个节点存储了下一个节点的对象的引用，形成了一个链表的结构。
为什么要用链表？用数组不行吗？刚刚上面提到过，这个集合是由链表和数组组成的。因为再完美的hash算法都有可能产生哈希冲突，所以两个不同key的元素可以被放在同一个地方。
而单用数组明显不能满足这个需求，而在数组的槽位上存一个链表就可以解决这个问题。

HashMap的使用

put存值

传入了两个参数，Key和Value，函数的定义如下。

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

应该跟大多数人YY的put方法差不多，put方法再调用了putVal 方法。
首先经过了hash之后的key，是一个整型的hashcode，其次是我们传入的key和value。最后两个布尔值，后面会提到。
首先一进入putVal就会声明存放数据的table，如果这个HashMap是首次设置值，就会被初始化一个默认size的table，且所有元素的初始值都是NULL，下面是初始化这块的核心代码，我省略掉了一些无关的变量声明。
有趣的是，初始化调用的是resize方法。

1
2
3
4
5
6
7
8
Node<K,V> p;
int n, i;
//如果当前map中无数据，执行resize方法。并且返回n
if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;
.....
newCap = 16;//默认容量
newThr = 12;//默认阈值

默认值为啥是16

上面初始化table的默认size给的是16，当然我们也可以自己定义，但是建议是最好是2的幂。有的朋（杠）友（精）就要问了，为什么是16呢？我13，14不他不香吗？我们接下来就要分析为什么不香。
当我们放元素进入map的时候，它是如何确定元素在table数组中的位置的呢？我们拿name这个key举例。

1
2
hash = (h = key.hashCode()) ^ h >>> 16;
p = tab[i = n - 1 & hash]

可以看到，是将hash之后key和数组的length-1做与运算得到了一个数组下标。而且，hash值的二进制的位数，大多数情况下都会比table的长度的二进制位数多。换句话说，与运算之后得到的数组下标index完全取决于hash值的后几位。

1
2
3
4
5
6
7
//16 n  	10000;
//15 n-1 	1111;
//14 		1110;
//13 		1101;
//12 		1100;
//11 		1011;
//10 		1010;

从13、14的二进制值可以看出来，存在0和1在二进制位数上分布不均匀的情况，这样一来就会造成一个问题，那就是会存在某些不同的hash值经过与运算得到的值是一样的。这样就会导致hash到的index不均匀，换句话说有些index可能永远都不会被hash到，而有些index也被频繁的hash到。
本来hash算法是要求计算的结果要均匀分布的，但是上述的结果明显不符合均匀分布的要求。用n-1而不用n也是因为同样的道理。如果这个值是2的幂，那么2的幂的值-1的所有二进制位数都是1，这样有利于hash计算的均匀分布。
综上所述，不一定是16，2的幂都可以，16只是一个经验值。

自动扩容

除了size，初始化的时候还会设定一个阈值，值为12，newThr = 12，这里需要提到一个概念负载因子，HashMap的实现里默认给的是0.75。

1
2
3
4
public HashMap(){
    //12/16 = 0.75F
    this.lodaFactor = 0.75F;
}

负载因子是用来干嘛的呢？最开始我们提到了，最开始存储的数据结构是数组，这种基础结构是有size设定的。当我们不停的往map里存数据的时候，总会存满，当元素快存满的时候，我们就需要扩大map的容量，来容纳更多的元素，这就需要一个自动扩容的机制了。
在当数据量大于超过设定的阈值的时候（容量*负载因子），自动对map进行扩容，以存放更多的数据。
自动扩容做了什么事情呢？总结来说就是两件事。
创建新的数组，大小是原来数组的一倍。将元素rehash到新的数组为什么要rehash呢？上面我们提到过了，当元素被放进map时，确认下标的方法是table的长度-1和hash值做与运算，现在table的长度发生了变化，那么自然而然，元素获取下标的运算结果也就跟之前的不一样了， 所以需要将老的map中的元素再按照新的table长度rehash到扩容后的table中。
所以在当你对性能有一定要求，且你知道你创建map的时候size的时候，可以指定size，这样一来就不会因为数据量持续的增大而去频繁的自动扩容了

put的过程中到底发生了什么

了解了底层数据结构和自动扩容机制，接下来我们来看一下put过程中究竟发生了什么。我们上面说过了，会通过数组的长度-1和hash值与运算得到一个数组下标。

如果该位置没有元素，那么就很简单，直接新建一个节点即可然后放置在数据的具体位置即可。

1
tab[i] = this.newNode(hash, key, value, (HashMap.Node)null);

但是如果该下标已经有元素了，这种情况HashMap是怎么处理的呢？这也要看情况。

如果是跟当前槽位相同的key，就直接覆盖。这就是我们修改某个key的值会发生的情况。那HashMap怎么来判断是不是同一个key呢？就像下面这样。p就是当前槽位上已经有的元素，如果新、老元素的key的hashCode和值都相同且key不为空，那么就能证明这两个key是相同的，那么此时只需要覆盖即可。p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))而如果p是TreeNode的实例，那么就代表当前槽位已经是一个红黑树了，此时只需要往这个树里putTreeVal即可。至于为什么是红黑树，哪儿来的红黑树，下面马上就要讲到了。最后一种情况就是，既不是已经存在的元素也不是TreeNode的实例，也不是红黑树。这种情况下，它就是一个普通的Node。你可以理解为链表，如果hash冲突了，就把这个Node放到该位置的链表末尾。Java8之前采用的头插法，而Java8换成了尾插法，至于为什么要换，后面会讲。当该位置的链表中的元素超过了TREEIFY_THRESHOLD所设置的数量时，就会触发树化，将其转化为红黑树。Java8里给的默认值是8。

为啥要转化成红黑树

首先我们要知道为什么要树化。当大量的数据放入Map中，Hash冲突会越来越多，某些位置就会出现一个很长的链表的情况。这种情况下，查询时间复杂度是O(n) ，删除的时间复杂度也是O(n)，查询、删除的效率会大大降低。而同样的数据情况下，平衡二叉树的时间复杂度都是O(logn)。

有的朋（杠）友（精）看到这个小标题不乐意了，怎么就直接用红黑树了？我用二叉查找树它不香吗？

不了解二叉查找树的，我把它的特点列在了下面。

左子树上的所有节点的值都小于根节点的值右子树上的所有节点的值都大于根节点的值再精简一下就是，左小右大

但是，如果数据大量的趋近于有序，例如所有的节点都比根节点大，那这个时候二叉查找树就退化成了链表，查询效率就会急剧下降。看到这是不是觉得有点不对，我才从链表树化，你这又给我退化成了链表？

朋友看到这又不乐意了，好好好，就算二叉查找树不行，那AVL树它也不行？用了AVL树就不会出现上面所描述的效率急剧退化的情况了不是吗？

的确是这样，AVL也可以叫平衡二叉搜索树。AVL树会在其有退化成链表的趋势的时候（左右子树的高度差超过某个阈值）调整树的结构，也就是通过左旋和右旋来使其左右子树的高度尽量平衡。

那为什么一定要用红黑树？

具体的细节也就不在这里赘述，不知不觉已经写了这么多了，直接说结论吧。AVL树的查找速度更快，但是相应的插入和修改的速度较慢。而红黑树则在插入和修改操作较为密集的时候表现更好。

而总结我们日常的HashMap使用，大多数情况下插入和修改应该是比查找更频繁一些的。而在这种情况下，红黑树的综合表现会更好一些。

至于红黑树的相关细节，涉及的东西还是挺多，我之后会单独拿一个篇幅来讲。

为什么要用尾插法

我们目前用的最多的是Java8，在Java8中采用的是尾插法，Java8之前采用的是头插法。

那为什么后面又变成了尾插法呢？放心，肯定不是设计者闲的蛋疼，没事来改个设计。这样做一定是有一定的道理的。在解释这个问题之前，我们先来看看，如果采取头插法在多线程下的情况下会出现什么问题。

我们讲过，假设数组中index=1的位置已经有了元素A，之后又有元素B被分配到了index=1的位置。那么在下标为1的槽位上的链表就变成了B -> A。

此时再分配了一个新元素C，链表又被更新成了C -> B -> A。这也是为什么叫头插法，新的元素会被放在链表的头节点，因为当时设计的时候考虑到后被放入map的元素被访问的可能性更大。

上面讲到了在当不停的往map中放置元素后，超过了设定的阈值，就会触发自动扩容。此时会触发两个操作，一是创建一个容量为之前两倍的底层数组，并且将老的数组中的元素rehash到新的数组中。

而由于数组的长度发生了变化，这就导致了元素的rehash结果跟之前在老数组中的位置不一样。

首先我们来模拟一下rehash的过程，假设新的数组中下标为2的槽位是空的。

首先元素C，被放置在了其他位置。然后元素B，被rehash到了下标为2的槽位， 至此都没有问题。最后元素A，同样被rehash到了下标为2的槽位，此时链表变成了A -> B。到这就有问题了，最开始B的next指向的是A节点。但是rehash之后A的next又指向B，看到这你应该就能明白发生了什么。我看到很多的对JDK1.7版的HashMap在多线程的情况下扩容会出现死锁的解释都只到了环形链表。但是其实就算是环形链表，只要找到了对应的元素，就会直接退出循环的逻辑，也不会造成死循环。

实际情况是，当自动扩容形成了环形链表后，当你去Get了一个在entry链上不存在的元素时，就会出现死循环的情况。

get取值

上面聊了给HashMap赋值的大概过程，接下来聊一下从HashMap获取值会发生什么。get方法的开始，跟put一样很简单。

1
2
3
4
public V get(Object key){
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

可以看到，取值的核心操作是getNode来负责完成的。

首先第一件事就是去check的第一个元素是不是当前查找的元素。

如果不是，而且当前槽位已经被树化成了红黑树，就走红黑树的getTreeNode方法。

如果还没有被树化，只是普通的链表，则顺着next一路找下去。

由于get方法逻辑和实现都比较容易理解，就不贴太多源码了。

关于HashMap的问题

为什么HashMap要树化

本质上这是个安全问题。因为在元素放置过程中，如果一个对象哈希冲突，都被放置到同一个桶里，则会形成一个链表，我们知道链表查询是线性的，会严重影响存取的性能。而在现实世界，构造哈希冲突的数据并不是非常复杂的事情，恶意代码就可以利用这些数据大量与服务器端交互，导致服务器端CPU大量占用，这就构成了哈希碰撞拒绝服务攻击，国内一线互联网公司就发生过类似攻击事件。

用哈希碰撞发起拒绝服务攻击(DOS，Denial-Of-Service attack),常见的场景是攻击者可以事先构造大量相同哈希值的数据，然后以JSON数据的形式发送给服务器，服务器端在将其构建成为Java对象过程中，通常以Hashtable或HashMap等形式存储，哈希碰撞将导致哈希表发生严重退化，算法复杂度可能上升一个数据级，进而耗费大量CPU资源。

为什么要将链表转红黑树的阈值设置为8

我们可以这么来看，当链表长度大于或等于阈值（默认为 8）的时候，如果同时还满足容量大于或等于 MIN_TREEIFY_CAPACITY（默认为 64）的要求，就会把链表转换为红黑树。同样，后续如果由于删除或者其他原因调整了大小，当红黑树的节点小于或等于 6 个以后，又会恢复为链表形态。

每次遍历一个链表，平均查找的时间复杂度是 O(n)，n 是链表的长度。红黑树有和链表不一样的查找性能，由于红黑树有自平衡的特点，可以防止不平衡情况的发生，所以可以始终将查找的时间复杂度控制在 O(log(n))。最初链表还不是很长，所以可能 O(n) 和 O(log(n)) 的区别不大，但是如果链表越来越长，那么这种区别便会有所体现。所以为了提升查找性能，需要把链表转化为红黑树的形式。

还要注意很重要的一点，单个 TreeNode 需要占用的空间大约是普通 Node 的两倍，所以只有当包含足够多的 Nodes 时才会转成 TreeNodes，而是否足够多就是由 TREEIFY_THRESHOLD 的值决定的。而当桶中节点数由于移除或者 resize 变少后，又会变回普通的链表的形式，以便节省空间。

默认是链表长度达到 8 就转成红黑树，而当长度降到 6 就转换回去，这体现了时间和空间平衡的思想，最开始使用链表的时候，空间占用是比较少的，而且由于链表短，所以查询时间也没有太大的问题。可是当链表越来越长，需要用红黑树的形式来保证查询的效率。

在理想情况下，链表长度符合泊松分布，各个长度的命中概率依次递减，当长度为 8 的时候，是最理想的值。

事实上，链表长度超过 8 就转为红黑树的设计，更多的是为了防止用户自己实现了不好的哈希算法时导致链表过长，从而导致查询效率低，而此时转为红黑树更多的是一种保底策略，用来保证极端情况下查询的效率。

通常如果 hash 算法正常的话，那么链表的长度也不会很长，那么红黑树也不会带来明显的查询时间上的优势，反而会增加空间负担。所以通常情况下，并没有必要转为红黑树，所以就选择了概率非常小，小于千万分之一概率，也就是长度为 8 的概率，把长度 8 作为转化的默认阈值。

如果开发中发现 HashMap 内部出现了红黑树的结构，那可能是我们的哈希算法出了问题，所以需要选用合适的hashCode方法，以便减少冲突。