引言

唉！

金九银十转眼已过，

面试现场不知所措；

不懂原理是我过错，

今日弥补只为求过。

======================================================

小学弟呀，小学弟！

平时不努力，

全来学押韵；

近来找工作，

处处不如意；

闲来送你一篇原理文，

让你对HashMap不再愁。

=======================================================

话不多说，就让我们开始HashMap的原理讲解吧。

正文

Hash表

HashMap其实就是用Hash表这种数据结构来实现的；如果你对Hash表了如指掌，我相信，对于HashMap你已经成功一半了。那我们就先来说说什么是Hash表吧。

先来举个例子：

    在上学时我们都排过队，当老师没有做要求的时候，大家都会随便站，关系好的站在一起等等没有统一规则，甚至还有插班的行为。当一个老师从这个长长的队列时找人时，往往都是从第一个开始找，直到找到他想找的人为止。这种方式就可以看做链表或者数组，每次都需要逐个遍历筛选。
  这时候教导主任来了，说这样排队太乱了，于是制定了排队规则，必须按照年级+班级+自己的序号顺序站队并记住这个序号。当老师再次找一个陌生的同学时，只要对教导主任说我要找二年级五班006同学，教导主任通过信息就可以直接找到张三同学站的位置，并不需要遍历了。这种方式就是Hash表的方式进行添加或者查找的。

我们来解释一下上面的例子：

• 例子中所提到的二年级五班006就是Hash值：根据key值（例子中的某个学生）计算得出一个固定长度的目标值，而这个目标值就叫做Hash值；
• 教导主任所制定的排队规则就是所制定的一个Hash函数：用key怎么计算Hash值的呢？就是通过Hash函数的计算；在项目中每一个hash函数的实现都是不一样的，而大部分hash函数的具体实现是非公开的，因为可能会造成安全问题。

简单的来说，哈希表是一种表结构，我们可以直接根据给定的key值计算出目标位置。在工程中这一表结构实现通常采用数组。

那么一个好的Hash函数具备什么样的特性呢？

• 1，同一性：也可以叫做散列性，即每一个Hash值都要尽可能的均匀；因为存储在数组时要尽可能的均匀存储。（也可以说每个数组下标的命中率尽可能相同。）
• 2，遵循雪崩效应：当有微小的key值输入时，Hash值要发生巨大的变化；有些Hash函数是为了进行加密使用的（如https协议）遵循这条可以保证更高的安全性。
• 3，尽量避免Hash冲突：当我们要把十个苹果放到九个抽屉里的时候，总会有至少两个苹果放到同一个抽屉里（抽屉原理），存在两个苹果的抽屉，我们就可以叫它Hash冲突，或者Hash碰撞；同样因为我们Hash值的长度是固定的，而key可以是任意值，所以总会造成两个key值的hash值相同，这种情况叫做Hash冲突，Hash冲突是不可避免的，但我们要尽可能的减少冲突。

现在看看我们例子中教导主任制定的Hash函数是不是可以被我们吐槽一番呢。

所以，Hash表他的查询速度快，一个良好的Hash表时间复杂度可以达到o(1)，对于庞大的海量数据，这种查找速度还是非常惊人的。

HashMap原理

JDK1.7

了解了Hash表，我们再来看HashMap，我们先来分析JDK1.7中的HashMap的实现：

JDK1.7中的HashMap采用的是数组加链表的形式进行存储的，数组每个下标所对应的位置我们都可以叫做一个hash桶。


put过程：

public V put(K key, V value) {
        if (key == null) //1
            return putForNullKey(value);
        int hash = hash(key); //2
        int i = indexFor(hash, table.length); //3
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {//4
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i); //5
        return null;
    }

1，key不能为空：

在存储元素前，HashMap将判断元素的key是够为空，如果为空，直接返回。

2，计算Hash值：

    final int hash(Object k) {
        int h = 0;
        if (useAltHashing) {
            if (k instanceof String) { //2.1
                return sun.misc.Hashing.stringHash32((String) k);
            }
            h = hashSeed;
        }

        h ^= k.hashCode(); 

        // 2.2
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

通过hash源码我们看到：

2.1，这里JDK1.7对String类型的元素进行了重新hash的过程，为什么String要重新hash呢？

要从一篇邮件开始说起...在JDK1.7出现后，Tomcat发布了一篇邮件，里边写到了JDK1.7中HashMap的一个潜在安全漏洞。

mail-archives.apache.org/mod_mbox/to…4EFB9800.5010106@apache.org

这篇邮件中，因为Tomcat使用了Hashtable存储了HTTP请求参数，由于String的hash算法是公开的，可能会导致一些专业人员可以获取到无数个hashcode都相同的key值，当这些请求参数同时请求后，就会使hash表退化成链表，使cpu存在大量的链表，由于链表查找的时间复杂度O(n)，查找速度会受到很大的影响，所以会遭受DDos攻击。

当然Tomcat也给出了解决方案，而随后在JDK1.7的版本后也修复了这个bug。

2.2，我们看在2.2处进行了一堆的>>>和^操作，原因就是为了要增加它的同一性，让命中每个数组下标的概率相同。

3，获得数组下标：

    static int indexFor(int h, int length) {
        return h & (length-1);
    }

在步骤2中，我们得到了Hash值，那么怎么通过hash值来决定存在哪个桶里呢？

可能有些人我们会想到取余操作，但是取余操作有两个缺点：1，相比于java的&运算速度相对慢一点；2，负数取余还是负数，数组下标（桶的位置）不能为负数。

所以Java采用的是按位与，这样就可以根据数组长度和Hash值计算出该元素桶的具体位置。

采用这种方式计算数组下标也是有损失的，如果length不为2的次幂，那么每次按位与时，为零的那一位永远为零，导致有些下标永远无法得到，如下图。

HashMap为了解决这个问题，如果你的值不为2的幂，那么在构造函数中HashMap将找到大于等于我们赋给HashMap的初始容量的最小2的幂。所以为了减少这次转换，我们初始化HashMap的容量时一定要为2的幂。

4，我们接着向下看注释4的地方：这里就是做了一个循环链表，去插入元素这么一个操作。

5，我们能看到这里调用了一个addEntry()函数，这个函数是干什么的呢，我们点击去：

    void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }

        createEntry(hash, key, value, bucketIndex);
    }

我们大致能了解到，这个其实就是扩容机制，知道这些就可以了，接着我们讲讲具体是怎么扩容的。

threshold：即阔值，当数组的使用大小大于等于这个值时，则将数组扩容。threshold = capacity（数组容量）* load_factor（负载因子）

load_factor（负载因子）：默认为0.75，官方解释说：在时间和空间成本之间做了权衡后，得出的0.75这个值。

进入到if后，执行了resize()这个函数，这个函数可以说是一切根源的罪魁祸首。

我们点resize()进去看看

    void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) { //MAXIMUM_CAPACITY默认是2的30次幂，所以基本不会到达这一容量
            threshold = Integer.MAX_VALUE;
            return;
        }

        Entry[] newTable = new Entry[newCapacity];
        boolean oldAltHashing = useAltHashing;
        useAltHashing |= sun.misc.VM.isBooted() &&
                (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
        boolean rehash = oldAltHashing ^ useAltHashing;
        transfer(newTable, rehash);
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

    void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Entry<K,V> e : table) {
            while(null != e) {
                Entry<K,V> next = e.next;
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }

这两个方法主要是rehash操作，然后将数组中的链表使用头插法重新插入到了新的数组中，其实这在单线程中是没有问题的，但是如果多个线程同时操作的时候，将会出现循环链表的情况。当再次访问这个循环链表时，就会出现死循环，cpu100%的情况，虽然HashMap中明确表示它并不是线程安全的，但还是有人会用到它，造成这样的问题。

• 这里给大家分享一篇文章，里边明确说明了为什么会产生循环链表：coolshell.cn/articles/96…

这就是JDK1.7中的HashMap的put过程，接下来我们简单说一说get过程：

    public V get(Object key) {
        if (key == null)
            return getForNullKey();
        Entry<K,V> entry = getEntry(key);

        return null == entry ? null : entry.getValue();
    }

这是JDK1.7的get方法，当key为空时返回null，否则调用getEntry()函数：

    final Entry<K,V> getEntry(Object key) {
        int hash = (key == null) ? 0 : hash(key);
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                return e;
        }
        return null;
    }

就是计算key的hash值，然后循环该桶下的链表，查找数据。

JDK1.8

上面我们说到，JDK1.7的HashMap存在着安全隐患，如多线程下会可能出现循环链表（这完全是用户自己的锅，因为Java团队明确表示HashMap不是线程安全的）。

• 所以JDK1.8的HashMap在结构上使用了数组加链表加红黑树的数据结构，防止当链表过长时导致搜索时间退化到o(n)。

当链表的元素达到了8的时候，将会使用红黑树代替链表，选择8的原因是因为Java团队解释说：

大致上说，他们采用了泊松分布的原理（大学数学我们应该都学过），当链表达到8时只有0.00000006的概率。

• 在hash()函数上也做了改进：

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

• 另外一个比较明显的改进是在resize()这个函数中从之前的头插法改为了尾插法，这样在多线程的情况下就不会存在循环链表，进而导致死循环的情况了。但是值得注意的是，HashMap任然不是线程安全的，这在HashMap注释中就已经明确说明了。

结束

这就是HashMap的比较重要的部分，也是面试过程中在问到HashMap时比较常见的问题。如果还有什么没有提到的，大家可以在评论中告诉我，我会尽量补充的。

作者：张子江
链接：https://juejin.im/post/6880712401143595021
来源：掘金