HashMap结构参考图 (红黑树叶子节点省去NULL)                                                                                                                                                           

     一. HashMap要点导航

    二. 代码分析

        从我们最常用的写法开始。无参构造初始化HashMap。

        好的，第一个成员变量出现。loadFactor 默认加载因子。常量值为 0.75 。这个字段代表的意思是，当前HashMap的元素数量到达容量的3/4的时候开始扩容（扩容机制下面会提）。

        1. 下面开始HashMap的核心方法。put(K key,V value)

       重点一：238行（注意我这里行数和源码不一样）hash值计算。

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

        这里代码不难看懂，用key的 hashcode 值和 hashcode 值右移16位进行异或操作的值作为返回值。为什么这么做呢，以 "money" 为 key 举例。字符串 "money" 的hashcode为：104079552。二进制：110001101000010000011000000   。右移 16 位之后 000000000000000011000110100  。先看一下如果不做这个操作会出现什么情况：

        // (h = key.hashCode()) ^ (h >>> 16)
        // 0110 0011 0100 0010 0000 1100 0000    // h
        // 0000 0000 0000 0000 0110 0011 0100    // h >>> 16
        // 0110 0011 0100 0010 0110 1111 0100    // h ^ (h >>> 16)
        // 0000 0000 0000 0000 0000 0000 1111    // 16 - 1
        // 0110 0011 0100 0010 0110 1111 0100    // h & (16 - 1)

        在谈这个问题之前，我们需要先了解一下什么叫做哈希碰撞。我们都知道HashMap的数据结构是 数组+链表（+红黑树）。那么一个元素被存放的时候就要计算hash索引，即它要被存放在数组哪个位置。比如计算出来的hash = 5。如果数组的第五个位置已经有元素了，那么就称为出现了哈希碰撞。

        上面代码中 h 是key的hashcode。因为hash索引值最终是 h & (容量 - 1) 来得出的，我们都知道HashMap容量是2的幂次方（最小为16）。减一之后二进制表现为 ***...*** 1111的形式。所以hash索引的值基本上取决于这个 h 。这里一开始的时候 HashMap 容量是16 。如果不进行无符号右移16位操作 将 h & (16 - 1) 。我们会发现运算之后  h 的高位特征消失。那么这高位的一点点差异就可能容易导致一次哈希碰撞，造成哈希碰撞的概率就被加大了。再看我们将 h >>> 16 之后。高位特征跑到低位。然后 h ^ (h >>> 16) 将高低位特征进行混合，这样再与容量进行按位与操作就降低了 hash 碰撞的概率。不得不说这真的是非常NB的做法。还记得刚开始提的 loadFactor  吗，为什么是0.75？因为源码有一段注释说明，当选取这个数字时，哈希碰撞超过8次几乎是不可能的！

        重点二：269行 从链表转为红黑树

        这之前的代码虽然乍看之下没有看下去的欲望，但是仔细分析还是不难的，而且我也放了注释。就不多说了，直接看JDK1.8新增的红黑树。267行 TREEIFY_THRESHOLD 这个值是 8 。用来判断当前数据结构是否要从链表和红黑树之间发生变化。266行将数据放进链表之后，判断当前链表的长度是不是等于8。如果是，并且数组长度大于等于 64 。那么就要改变存储的数据结构为红黑树。为什么要做这个改变呢？我们都知道链表是基于线性表的数据结构，物理内存不连续，只存放了下一个节点的指针，查找效率随着长度增加越来越低。而红黑树是一个自平衡二叉树，其本身的旋转和变色等特性能够保证增删和查询的效率。为了防止数据量过多导致查询效率问题，JDK8才引入了红黑树结构。

        重点三：287,288行 扩容机制

        由于篇幅问题这里就不再贴代码了……HashMap每次都是在元素数量大于容量的 3/4 时进行扩容，每次扩容都是2的幂次方，这里去看288行的 resize() 方法源码就一目了然了，因为要保证计算的hash索引均匀分布。如果不是2的幂次方，那么在做 h & (n - 1) 操作的时候，由于 n-1 二进制位上的0会导致和重点一一样的问题，丢失key的hashcode高低位的特征，增加哈希碰撞的概率。

          不知不觉已经写了这么多，原谅博主文采实在不好，自己也感觉写的很乱……代码细节基本有注释，希望大家能够参考，有错误欢迎指正！以上其实也是基于当年面试准备的时候老是看到这个面试题，所以不得不去研究下……估计过一段时间也就忘了吧……没办法，面试造火箭，入职。。。