一文读懂系列－HashMap

前言

发现很多同学在开发过程中只听过某些技术概念或者用过一些jdk中常用的数据类型，但是真正能解释清楚甚至知道实现原理的同学并不多，所以准备写一个一文读懂系列文章，每篇文章介绍一个大家经常听到或者经常在项目中使用的技术或者数据类型，文中并不是简单的介绍如何使用，而是会通俗易懂的介绍这些技术、数据类型的核心原理和底层实现，让大家知道为什么，并不只是简单的会使用。
今天第一篇我们要介绍的是HashMap，大家在日常工作中使用HashMap的情况非常多，并且常用的一些方法也都知道如何使用，也知道使用HashMap会比使用Hashtable要快，但是大家有没有思考过为什么会快？为什么各种编程指南都推荐大家使用HashMap？如果你只是知道HashMap是非线程安全的所以快，那就太out了，下面我们就从HashMap使用场景和实现原理让大家深入了解HashMap。

HashMap基本概念

HashMap大家肯定是经常使用的，在头脑中的概念应该就是一个对key值通过hash散列后保存起来的一个Map集合。在日常使用过程中，对于一些非线程安全、需要使用Key-Value的数据集合场景可以使用HashMap。HashMap属于java Collection集合类，使用起来也是实现了集合类的基础方法，HashMap对比其他的List或者Stack、Queue在数据结构层面的差别在于，HashMap保存的Key值是不能重复的，其他集合类型是可以重复保存数据结构的。HashMap和HashTable的差别在于一个是线程安全的一个是非线程安全的，不过HashTable在JDK1.5以后已经不推荐使用了，因为HashTable是通过对整个存储数组进行锁定，是一种悲观锁的实现方案在高并发场景下性能非常低，在JDK1.5以后官方推荐对于需要线程安全的场景可以使用ConcurrentHashMap来实现内存key－Value的存储，因为ConcurrentHashMap是一种乐观锁的线程安全的实现。对于ConcurrentHashMap的内容其实就更多了，后面单独写一篇文章来介绍ConcurrentHashMap。

HashMap实现原理

上面介绍了下HashMap的大概内容，下面就步入正题介绍下下HashMap的具体实现原理。

HashMap的底层数据结构用一句话描述就是HashMap内部数据结构采用数组的方式保存entry(一个key－value键值对)，每个数组节点又是一个链表的表头，在表头中进行插入冲突的数据。

Screenshot 2018-02-05 11.26.58

下面我们通过描述数据的put、get过程来讲解下整个的实现原理.

HashMap.put()实现

下面我们看HashMap的put方法是如何实现的，上面我们已经说了HashMap的数据结构，在源码中定义了Node<K,V>[] table来表示数组基础结构，Node是定义的用于表示key－value的entry键值对的数据类型，在Node<K,V>中定义了节点的hash值、实际键值key、实际value数据和指向下一个节点的引用对象。

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

下面看下put（）方法的实现源码，入参是key和value，在put方法中调用了putVal（）方法，可以看到putVal（）方法才是真正的将entry put到HashMap中的方法，putVal（）的入参有5个，第一个为int型的hash数值，其实就是这个key的hash值，后面以此为key和value。

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

HashMap的核心没有别的，就是hash算法，hash算法的好坏直接关系到hash的读取性能，冲突越小越好，这样读取和插入的效率都是最高的，在面试过程中如果问到hashMap中的hash算法是如何实现的大部分人是说不上来的，很多人的回答可能是类似取模之类的散列，其实取模的散列算法是非常低级的，会导致大量的数据冲突，冲突值大了以后就会导致put和get的效率都下降很多，所以我们看下hash的源码算法是什么样的。

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

可以看到这个hash算法其实也没有大家想象的那么复杂，他只是对于非空的key值取了32位hashCode然后做位偏移运算，为什么要这么做偏移而不是简单的取模或者其他算法呢？这是因为在二进制的世界里，通过位偏移能够最大概率的将没有集中度的数据打散，减少正态分布的波峰，而且位运算的效率是非常高的。
从这里我们也可以了解到HashMap中Node<k,v>[]数组的默认大小为16，为什么是16不是12，14？这也是因为和hash算法有关，使用16个散列桶在这样的算法下冲突的概率比较低。
好了下面我们来看下putVal这个核心方法的代码。整个代码的核心思路就是判断待插入值的散列值是否和和现有的散列值冲突，如果不冲突则直接放入这个Node数组中，如果散列值冲突，在数组中已经有这个散列值了，则将这个待插入的值放入Node数组，并将原来数组这个位置上的值放到这个刚插入的Node节点的next节点上，这样所有冲突的散列值Node节点就串成了一个单向链表，但是这样的列表在查询的时候会导致查询时间复杂度为log（N），如果冲突层数比较深的节点，读取效率会比较低，所以在JDK1.8后进行了数据结构优化，JDK设置了一个阈值，这个阈值为8，当链表长度超过8后就将链表结构变化为红黑二叉树，通过二叉查找数来提高查询性能，这样的数据结构变化后时间复杂度变为了log2（N），查找性能大幅度提升，但是这样带来的问题就是在插入的时候有可能会导致红黑数的旋转影响到性能。

下图为链表数据结构图示（鼠标画的将就看吧）

Screenshot 2018-02-05 14.31.32

红黑二叉查找树数据结构，每个节点左边所有节点值都小于节点值，右边所有节点值都大于节点值。

Screenshot 2018-02-05 14.34.21

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //HashMap中的Node数组为空，则赋值给局部变量n
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        //如果Node数组的散列桶没有被占用，则将新插入节点
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {//如果散列桶被占用则将现有数组中的值放到新插入节点的链表后面
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        //在1.8后jdk进行了优化，当链表长度超过阈值8后将链表转化为红黑二叉树
                        if (binCount >= TREEIFY_THRESHOLD - 1) 
                            treeifyBin(tab, hash);
                        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的读取性能高了吧。

下面我们再来看看get（）方法，get（）方法其实就是put方法的一个逆向过程，如果put方法看明白了，那么get的实现其实不看也能明白具体是如何实现的。

HashMap.get()实现

可以从源码看到get方法的实现调用了Node<K,V> getNode(int hash, Object key)这个方法，getNode方法的入参为hash值和key值，hash值是用来快速定位到HashMap中的散列桶位置，key是用来在散列桶对应的链表或者红黑树中查找到相应entry。

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

getNode的代码直接贴出来，就不详细描述了，看代码就能很好理解什么意思，思路就是根据hash值找到Node<k,v>[] table的散列桶位置，然后判断首节点类型是链表还是红黑树，分别遍历链表和红黑树去查找key值，找到后返回Node节点对象。

final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
                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);
            }
        }
        return null;
    }