系统优化专题6——HashMap

在Java语言中定义了一个Map接口，主要用来存放键值对数据。而HashMap作为日常使用最频繁的容器之一，我们来聊一聊它的设计与优化。

常用的数据结构

我们先了解一下常用的数据结构。

数组
采用一段连续的空间来存储数据。对于指定下标的查找，时间复杂度为O(1)，但在数组中间及头部插入数据时，需要复制移动后面的元素。
链表
一种在空间上不连续、非顺序的存储结构，数据元素的逻辑顺序通过链表中的指针链接顺序实现。链表由一系列结点(链表中的每一个元素)组成，结点可以在运行时动态生成。每个节点都包含"存储数据单元的数据域"和"存储下一个结点地址的指针域"这两个部分。由于链表不是必须按顺序存储，所以链表在插入的时候可以达到O(1)的复杂度，但查找一个结点或者访问特定下标的结点需要O(n)的时间。
哈希表
根据键(Key)直接访问值(Value)的数据结构。通过把键映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫哈希函数，存放记录的数组就叫哈希表。

HashMap的实现结构

作为最常用的Map类，它基于哈希表实现，继承了AbstractMap并且实现了Map接口。

哈希表将键的Hash值映射到内存地址，即根据键获取对应的值，并将其存储到内存地址。也就是说HashMap是根据键的Hash值来决定对应值的存储位置，通过这种索引方式，HashMap获取数据的速度会非常快。

例如：存储键值对(x,"aa")时，哈希表会通过哈希函数f(x)得到"aa"的真实地址。

但哈希表有时也会有新问题。如果再有一个(y,"bb")，哈希函数f(y)的哈希值跟之前f(x)是一样的，这样两个对象的存储地址就冲突了，这种现象就是哈希冲突。

哈希冲突的解决方法

哈希表有很多解决哈希冲突的方法，比如开放定址法，再哈希函数法和链地址法等。

开放定址法
开放定址法很简单，当发生哈希冲突时，如果哈希表没有装满，说明哈希表中一定还有空位置，那么可以把Key存放到冲突位置后面的空位置上。这种方法存在着许多缺点，例如查找、扩容等，所以不作为解决哈希冲突的首选。
再哈希法
故名思意就是在发生地址冲突时在计算另一个哈希函数地址，直到不再有冲突为止。这种方法不易产生"聚集"，但却增加了计算时间。如果我们不考虑添加元素的时间成本，且对查询元素的要求极高，就可以考虑使用这种算法设计。
链地址法
采用数组(哈希表)+链表的数据结构，当发生哈希冲突时，使用一个链表存储相同的Hash值的数据。

HashMap综合考虑了所有因素，采用链地址法解决哈希冲突问题。

HashMap的重要性

从HashMap的源码中，我们可以发现，HashMap是由一个Node数组构成，每个Node包含了一个Key-Value键值对。

transient Node<K,V>[] table;

Node类作为HashMap中的一个内部类，除了key、value两个属性外，还定义了一个next指针。当有哈希冲突时，HashMap会用之前的数组当中相同的哈希值对应存储的Node对象，通过指针指向新增的相同哈希值的Node对象的引用。

static class Node<K,V> implements Map.Entry<K,V>{
    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;
    }
}

HashMap还有两个重要的属性：加载因子(loadFactor)和边界值(threshold)。在初始化HashMap时，就会涉及到这两个关键初始化参数。

int threshold;
final float loadFactor;

LoadFactor属性是用来间接设置Entry数组(哈希表)的内存空间大小，在初始HashMap不设置参数的情况下，默认LoadFactor值为0.75。

为什么是0.75这个值呢？这是因为对于使用链表法的哈希表来说，查找一个元素的平均时间是O(1+n)，这里的n指的是遍历链表的长度，因此加载因子越大，对空间的利用就越充分，这意味着链表的长度越长，查找的效率就越低。如果设置的加载因子过小，那么哈希表的数据将过于稀疏，会对空间造成严重的浪费。加载因子是扩容的参考标准，如果加载因子越大，例如默认数组初始化大小为16，加载因子由0.75改成1.0，原来数组长度到了12就扩容，变成数组大小为16，也就是说被占满了，才会进行扩容，这也可能意味着已经发生了很多哈希冲突，这样导致某些数组中的链表长度增加，影响查询效率。

Entry数组的Threshold是通过初始容量和LoadFactor计算所得，在初始HashMap不设置参数的情况下，默认边界值为12。如果我们在初始化时设置的初始化容量较小，HashMap中Node的数量超过边界值，HashMap就会调用resize()方法重新分配table数组。这将会导致HashMap的数组复制，迁移到另一块内存中去，从而影响HashMap的效率。

HashMap添加元素优化

初始化完成后，HashMap就可以使用put()方法添加键值对了。当程序将一个key-value对添加到HashMap中，程序首先会根据该key的hashCode()返回值，在通过hash()方法计算出hash值，再通过putVal方法中的(n-1)&hash决定该Node的存储位置。

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

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

if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;
    //通过 putVal 方法中的 （n - 1) & hash 决定该 Node 的存储位置
    if((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash ,key ,value ,null);

我们先来了解一下hash()方法中的算法。如果我们没有使用hash()方法计算hashCode，而是直接使用对象的hashCode值，会出现什么问题？

假设要添加两个对象a、b，如果数组长度是16，这时对象a和b通过公式(n-1)&hash运算，也就是(16-1)&a.hashCode和(16-1)&b.hashCode，15的二进制为0000 0000 0000 0000 0000 0000 0000 1111，假设对象A的hashCode为0100 0010 0011 1000 1000 0011 1100 0000，对象B的hashCode为0011 1011 1001 1100 0101 0000 1010 0000，你会发现上述与运算的结果都是0，这样的哈希结果表示这明显不是一个好的哈希算法。

但如果我们将hashCode值右移16位(h >>> 16 代表无符号右移16位)，也就是取int类型的一半，刚好可以将该二进制数对半切开，并且使用位异或运算(如果两个数对应的位置相反，则结果为1，否则为0)，这样的话，就能避免上面的情况发生。这就是hash()方法的具体实现方式。简言之，就是尽量打乱hashCode()真正参与运算的低16位。

再来解释下(n-1) & hash 是怎么设计的，这里的n代表哈希表的长度，哈希表习惯将长度设置为2的n次幂，这样恰好可以保证(n-1) & hash 的计算得到的索引值总是位于table数组的索引之内。例如：hash=15，n=16时，结果为15；hash=17，n=16时，结果为1。

在获得Node的存储位置后，如果判断Node不在哈希表中，就新增一个Node，并添加到哈希表中，整个流程使用下图来说明：

image.png

从图中我们可以看出：在JDK1.8中，HashMap引入了红黑树数据结构来提升链表的查询效率。

这是因为链表的长度超过8后，红黑树的查询效率要比链表高，所以当链表超过8时，HashMap就会将链表转换为红黑树，这里值得注意的一点是，这时新增由于存在左旋、右旋效率会降低。这就是前面说的‘因链表过长导致的查询时间复杂度高’的问题。

以下就是put的实现源码:

/**
     * Implements Map.put and related methods.
     *
     * @param hash hash for key
     * @param key the key
     * @param value the value to put
     * @param onlyIfAbsent if true, don't change existing value
     * @param evict if false, the table is in creation mode.
     * @return previous value, or null if none
     */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
//1、当table为null或tab的长度为0，即table尚未初始化时，通过resize() 方法得到初始化的table
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
//1.1、通过(n-1) & hash计算的值作为tab的下标i，并令p表示tab[i]，即该链表第一个节点的位置。并判断p是否为null；
            tab[i] = newNode(hash, key, value, null);
//1.1.1、当p为null时，表明tab[i]上没有任何元素，那么就new第一个Node节点，调用newNode方法返回新节点赋值给tab[i]
        else {
//2.1 当p不为null，有三种情况：p为链表节点、p为红黑树节点、p是长度为临界长度TREEIFY_THRESHOLD的链表节点，再插入就会转换为红黑树
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
//2.1.1 HashMap中判断key相同的条件是key的hash相同，且符合equals方法。这里判断了p.key是否和插入的key相等，如果相等，则将p的引用赋给e
                e = p;
            else if (p instanceof TreeNode)
//2.1.2 若p为红黑树节点，插入后仍是红黑树节点，所以直接将p强转调用TreeNode.putTreeVal方法，将返回的引用赋给e
//TreeNode是Node的子类
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
//2.1.3 若p为链表节点，插入后仍为链表/插入后转红黑树
                for (int binCount = 0; ; ++binCount) {
//定义一个计数器binCount保存当前链表的元素个数，并遍历链表
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//插入成功后，要判断是否需要转换成红黑树，因为插入后链表长度加1，而binCount不包含新节点，所以判断时需要将临界阈值减1
                            treeifyBin(tab, hash);
//当新长度满足转换条件时调用treeifyBin方法，将该链表转换为红黑树
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

HashMap获取元素优化

当HashMap中只存在数组，而数组中没有Node链表时，是HashMap查询数据性能最好的时候。一旦发生大量的哈希冲突，就会产生Node链表，这个时候每次查询都有可能遍历Node链表，从而降低查询数据的性能。

特别是在链表长度过长的情况下，性能将明显降低。红黑树的使用很好的解决了这个问题，使得查询的平均时间复杂度降低到了O(log(n))，链表越长，使用红黑树替换后的查询效率提升越明显。

我们在编码中也可以优化HashMap的性能，例如重写key值的hashCode()方法，降低哈希冲突，从而减少链表的产生，高效利用哈希表，达到提高性能的效果。

HashMap扩容优化

HashMap也是数组类型的数据结构，所以一样存在扩容的情况。
在JDK1.7中，HashMap整个扩容过程就是分别取出元素，一般该元素是最后一个放入链表的元素，然后遍历以该元素为头的单向链表元素，依据每个被遍历元素的hash计算其在新数组中的下标，然后进行交换。这样的扩容方式会将原来哈希冲突的单向链表尾部变成扩容后单向链表的头部。

而在JDK1.8中，HashMap对扩容操作做了优化。由于扩容数组的长度是2倍关系，所以对于假设初始tableSize = 4要扩容到8来说就是0100到1000的变化(左移一位就是2倍)，在扩容中只用判断原来的hash值和左移动的一位(newtable的值)按位与操作是0或1就行，0的话索引不变，1的话索引就变成原索引加上扩容前数组。

之所以能通过这种“与运算”来重新分配索引，是因为hash值本来就是随机的，而hash按位与上newTable得到的0(扩容前索引位置)和1(扩容前索引位置加上扩容前数组长度的值索引处)就是随机的，所以扩容的过程就是把之前哈希冲突的元素再随机分布到不同的索引中去。

总结

HashMap通过哈希表数据结构的形式来存储键值对，这种设计的好处就是查询键值对的效率高。

我们在使用HashMap时，可以结合自己的场景来设置初始容量和加载因子两个参数。当查询操作较为频繁时，我们可以适当减少加载因子；如果对内存利用率要求较高，可以适当增加加载因子。

还可以在预知存储数据量的情况下，提前设置初始容量(初始容量 = 预知数据量/加载因子)。这样做的好处是可以减少resize()操作，提高HashMap的效率。

HashMap还使用了数组+链表这两种数据结构相结合的方式实现了链地址法，当有哈希冲突时就可以将冲突的键值对链成一个链表。但这种方式又存在一个性能问题，如果链表过长，查询数据的时间复杂度就会增加。hashMap在Java8中使用了红黑树来解决链表过长导致的查询性能下降的问题。

image.png

HashMap设置初始容量最好是2的整数幂，因为2的幂次方减1后每一位都是1，让数组每一个位置都能添加到元素。

例如十进制8，对应二进制1000，减1是0111，这样在&hash值使数组每个位置都是可以添加到元素的，如果有一个位置为0，那么无论hash值是多少那一位总是0，例如0101，&hash后第二位总是0，也就是说数组中下标为2的位置总是空的。
如果初始化大小设置的不是2的幂次方，hashmap也会调整到比初始化值大且最近的一个2的幂作为capacity。