Java集合 | 重识HashMap

搬砖俱乐部

发布于 2019-06-15 17:32:35

7400

发布于 2019-06-15 17:32:35

文章被收录于专栏：BanzClubBanzClub

众所周知，Map是键值对<key，value>形式，Map又叫映射，可以理解为数学中的函数（key-x，value-y之间存在某种函数关系）。HashMap主要是用散列方式实现的Map容器，即散列映射，对key进行散列运算，可以直接找到value，而不需要像列表或者链表那样，线性遍历查找。HashMap不同于TreeMap，主要用于存储无序的数据。

在Java中，Map接口主要定义了映射容器的一些基本属性，包括长度（size）、是否为空（isEmpty）、获取（get）、存放（put）、移除（remove），包含（contains），迭代（forEach）等。HashMap继承自Map，在1.8版本也做了很大的调整，主要用数组 + 链表+ 红黑树的存储实现方式，代替了老版本的数组 + 链表的方式。1.8版本之前，在添加元素发生hash碰撞时（这里的hash碰撞，就是根据key值得到的hash值，在进行计算得到的下标相同，但hash可能不一样），随着发生碰撞的元素越来越多，链表会一直增长，使检索效率逐渐退化成线性。1.8版本，采用了红黑树之后，提升了发生hash碰撞的元素的检索效率，使整体结构更加平衡。

那HashMap是怎么实现散列映射的呢，一图胜千言：

将key值进行hash计算，再根据hash值得到索引值，确定value在数组中的位置，将key，value，hash构建成Node（链表节点的数据结构），即新元素。如果此位置没有元素，则放入数组，此时数组下标位置相当于只有头元素的链表；如果此位置已经存在元素，则将新元素追加到当前链表的尾部。当链表长度超过8时，将链表结构进化为红黑树。下面将对照HashMap源码来分析的其原理和实现。

基本属性
- 默认初始容量：DEFAULT_INITIAL_CAPACITY = 1 << 4
- 最大容量：MAXIMUM_CAPACITY = 1 << 30
- 默认负载系数：DEFAULT_LOAD_FACTOR = 0.75f
- 树进化阈值：TREEIFY_THRESHOLD = 8
- 树退化阈值：UNTREEIFY_THRESHOLD = 6

实例属性

map集合长度：size
扩容阈值：threshold
负载系数：loadFactor
修改数量：modCount

存储结构

链表节点的数据结构为Node，实现自Map.Entry

Node{
    int hash;
    K key;
    V value;
    Node<K,V> next;
}

链表数组

Node<K,V>[] table

红黑树节点的数据结构为TreeNode，是Node的子类，多了红黑树的属性（父，左右子，颜色等）。

TreeNode{
    int hash;
    K key;
    V value;
    Node<K,V> next;
    Entry<K,V> before, after;
    TreeNode<K,V> parent;
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;
}

Hash算法和容量

HashMap容器的创建，采用了延迟初始化，创建容器时，只是指定了负载系数（loadFactor）和扩展阈值（threshold），真正创建容器，是在put第一个元素的时候；而HashMap的容量被指定为2的整数平方倍，下面来看一下怎么保证容量始终为2的整数平方倍：

不指定容量的话，初始为16；
如果指定的话，会使用tableSizeFor（）方法转化为一个2的整数平方倍。赋给实例变量threshold，到创建容器时候又将threshold赋给了新容量。

这个方法可能不会那么直观的理解他的意思，下面通过一个图来说明一下：

指定了一个容量 1207959552，大概2的30次方左右，转化成二进制；
然后分别右移1位、2位、4位、8位、16位，并且每次移位之后，根移位之前的数做一次按位或操作；
最后就会得到都是1的数，这个数再加1，还是2的整数平方倍，也就是比指定数大的最小2的整数平方倍
两个问题：
1. 为什么每次1、2、4、8、16移动？这样才能保证所有的低位都能刚好被覆盖到，因为就是想得到2的整数平方倍-1的数，这样数的特点就是所有位都是1
2. 为什么一共移动31位？ HashMap指定了最大容量为 1 << 30（2的30次方），所以能保证将 1<<31的数都能转化成所有位都为1的数。

为什么容量始终是2的整数平方倍呢？我们先看一下Hash算法是怎么确定数组下标的：

发现用hash的值与容器容量减1做按位与运算。而容器容量为2的整数平方倍，再减一的话，转化成二进制除最高位左面的位上是0，其他所有位都是1，这样做与运算得到的结果，必然落在length内，而且效率要比取模运算快。

put、get、remove

HashMap的put操作

HashMap的get操作

HashMap的remove操作

通过分析put、get、remove源码，发现HashMap的添加、获取、删除操作，都是基于三种结构进行的，即数组、链表、红黑树。

数组：因为HashMap是对key进行，hash算法直接确定的数组位置，不进行数组元素的移动，所以数组添加、修改、删除操作时间复杂度是O(1)
链表：链表的添加操作是每次需要向链表尾部添加；查找也是线性的遍历链表以找到与key值相等的元素；删除操作包含查找操作，所以链表的时间复杂度是O(n)
红黑树：稍后分析

红黑树

为什么要将链表进行树化操作呢？可以看看1.7版本之前的HashMap实现，hash碰撞之后，将无限增加链表的长度，大家都知道链表的添加、查找、删除时间复杂度是O(n)，这使得HashMap在发生hash碰撞之后，效率变成了链表，而完全用散列实现，在元素比较多的时候，意味着资源的浪费，所以带有自平衡属性红黑树的引入，使得HashMap整体结构和效率更加平衡。二叉树的添加、查找、删除操作的时间复杂度是O(logn)。（对于红黑树的分析，不做展开，将有专门一篇专门的文章来分析红黑树）

链表树化

其实链表的树化操作，就是将第一个节点作为红黑树的根，逐渐向红黑树中添加元素，最后将平衡后的红黑树的根，放在数组下标位置，作为第一个元素

红黑树退化：红黑树退化存在两种场景

一、删除节点后，红黑树的数量太少（黑高小于2）

二、当发生扩容时，HashMap将进行rehash操作，所有元素要重新计算一次，红黑树进行将分裂操作，这时候如果子树长度小于树退化阈值（UNTREEIFY_THRESHOLD = 6），进行退化成链表处理

红黑树的添加、查找、删除

红黑树是一种自平衡的二叉查找树，红黑树的查找，还是二叉树的查找，时间复制度为O(logn)，而红黑树的添加和删除，因为红黑树具有平衡的性质，所以每次添加、删除操作之后，时需要进行再平衡操作，以保证继续满足红黑树的性质；

虽然红黑树添加、删除之后需要平衡操作，但平衡操作可以在几种固定情况的旋转操作，就可以重新恢复平衡，所以时间复制度还是O(logn)。

HashMap的多线程表现

在1.8之前，HashMap再多线程情况下，rehash会导致死循环，主要是由于rehash过程中，链表重新计算时，顺序会由原来的1->2->3，变成3->2->1，也就是将原链表的数据，按照依次向链表头插入元素的操作（链表添加动作，1.8向尾部添加，1.7向头部添加）。如果两个线程同时进入红色框中时，可能会导致链表的环状指向，导致死循环。

而在1.8中不存在这种情况，因为1.8不是向链表头追加元素的，而是向链表尾部添加元素，这样保证了链表的顺序操作；另外1.8版本使用高位链表和低位链表两个链表来完成rehash动作的，循环完成后，两个新链表再重新放到对应的数组下标下，所以无论多少个线程同时执行，都会是重复一样的动作，不会出现1.7那样的死循环。