Map是Java开发常用的数据结构，也是面试常考的一个知识点。了解其源码对我们以后无论是面试还是开发都有很大帮助。 Map中最常用的就是HashMap，这里就针对HashMap源码进行解读。 众所周知，在JAVA8中HashMap是有数组+链表+红黑树构成。这里只解析数组+链表的部分，能力有限，红黑树自己都不太懂，以后再补吧。 学习HashMap，首先我们要清除HashMap内部的两个变量：threshold，loadFactor。 如果我们首先看HashMap的构造函数：
public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity); //1 } public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } public HashMap() { //0.75 this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted }这个loadFactor被称为加载因子，这个值用来计算threshold。threshold称为阈值，表示当前Map中最大可以存多少数据（不是数组设置容量是多少就可以存多少，如果超过阈值，会进行扩容操作，threshold也会随着增大）。 细心看上边的代码还会发现构造函数中使用了一个tableSizeFor的方法去计算threshold，这个方法是怎么样的呢，我们继续看：
static final int tableSizeFor(int cap) { int n = cap - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }可以看到这个函数对传入的cap参数做了一系列的无符号右移或操作。该方法的目的是计算出大于等于cap的最小的2的x次方的值。比如输入20，计算出n的值为31，31+1刚好是2的5次方。其实这个函数也很好理解，一个小于等于2的x次方的值，他的二进制的x-1位的值一定是1，n|n>>>1可以将x-2位也置为1，就这样一层一层类推，最后x位以后的所有数一定均为1。 到目前，我们大概会有两个疑问：1.构造函数中只初始化了两个变量，并未初始化任何的存储数据的容器，那容器在哪里初始化呢？2.为什么一定要2的x次方值呢？
接下来我们带着这两个问题再去看put操作。
/** * Associates the specified value with the specified key in this map. If the map * previously contained a mapping for the key, the old value is replaced. * * @param key key with which the specified value is to be associated * @param value value to be associated with the specified key * @return the previous value associated with <tt>key</tt>, or <tt>null</tt> if * there was no mapping for <tt>key</tt>. (A <tt>null</tt> return can * also indicate that the map previously associated <tt>null</tt> with * <tt>key</tt>.) */ public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } 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) //首先进行数组初始化 n = (tab = resize()).length; //数组长度和hash相与计算下标 if ((p = tab[i = (n - 1) & hash]) == null) //如果当前位置没有元素，就把该值放到当前位置 tab[i] = newNode(hash, key, value, null); else { Node<K, V> e; K k; //hash值相同，key相同，获取key的equals方法相等 //1.hash值一定相同吧？不一定，当数组长度为16时，可能是1111&101111，也可能是1111&111111 //2.直接k.equals(key)不就可以了吗？ 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); //binCount = 7，因为上边新插入一个， //所以当链表长度为8的时候，转换为二叉树 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) //存在相同的key，此时e就是相同的key所在的结点，直接跳出 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; }put方法比较长，我们先用流程图将上述方法流程理清，然后再逐层深入。
是 否 是 否 是 否 是 否 是 是 否 否 是 否 否 是 是 否 开始 容器是否为空 初始化容器 当前位置是否为空 插入键值对 是否与当前key相同 是否存在相同key 是否为树 寻找树中相同的key next是否为空 插入键值对 链表长度是否大于等于8 转化为树 是否与当前key相同 是否需要扩容 扩容 替换返回旧值 结束流程比较复杂，流程图看起来也不是很清晰，但其实如果我们抛开树的操作不谈，整个流程的核心步骤只有以下几步：
是否初始化数组寻找该key是否已经存在，存在则替换key不存在（当前数组为null也相当于不存在该key），新增结点是否需要扩容。只要我们把握住这几步，整个put方法就不再难懂了。接下来，我们分块儿解析put过程。 前边我们曾有个疑问：哪里初始化了数据容器（数组）？ 在put过程中，首先会查看数组是否为null，可以看到数组会在第一次调用put过程中初始化。那么具体初始化过程是怎样的呢？为了方便理解，我们只截取resize()中初始化的过程代码。
if ((tab = table) == null || (n = tab.length) == 0) //首先进行数组初始化 n = (tab = resize()).length; final Node<K, V>[] resize() { Node<K, V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; if (oldThr > 0) // initial capacity was placed in threshold //调用HashMap(int initialCapacity, float loadFactor)时会走到这里 //HashMap(int initialCapacity)本质上也是调用的上一个构造函数 newCap = oldThr; else { // zero initial threshold signifies using defaults //调用new HashMap()时会走到这里 newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } if (newThr == 0) { float ft = (float) newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ? (int) ft : Integer.MAX_VALUE); } threshold = newThr; @SuppressWarnings({ "rawtypes", "unchecked" }) Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap]; table = newTab; return newTab; }单独看整个初始化过程也很简单
根据旧的threshold值初始化数组长度（2的x次方）或者使用默认值（16）计算新的threshold值（loadFactor * table.length）new一个新的数组接下来是查询当前下标处是否存在相同的key值，我们仍然截取查询的代码块
判断当前结点key（头结点）与put传入的key是否相同判断是否是树结点，如果是树，以树的方式查找循环查找后边的结点，是否存在相同key的值 if ((p = tab[i = (n - 1) & hash]) == null) //... else{ Node<K, V> e; K k; //hash值相同，key相同，获取key的equals方法相等 //1.hash值一定相同吧？不一定，当数组长度为16时，可能是1111&101111，也可能是1111&111111 //2.直接k.equals(key)不就可以了吗？ 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.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; e = e.next;//删除其他代码后新增一行代码，否则无法向下查找 p = e; } } }这里有一个问题需要注意，第9行首先判断二者hash是否相同，这里可能有的人不太理解，我们增加链表结构不正是为了解决hash冲突吗？那hash值不是一定相同吗？ 其实不是的，注意hashMap计算下标的方法是len-1&hash所得，假设len=16，len-1的二进制表示为1111，所以我们处理hash冲突实际上主要处理的是hash值后四位（针对len=16的情况）是否冲突。这里也解释了我们在看代码前的第二个问题，为什么数组长度一定是2的x次幂，当数组长度是2的幂，len-1的值就相当于一个掩码，我们求下标操作实际上是hash%len的过程，当len=2x时，hash%len==(len-1)&hash，相与的操作效率更好。事实上，如果我们将数组长度设置为232，只要hash值是充分散列的，那很少会有冲突的情况，但这个长度的数组占用太大内存。
接下来，我们再看新增结点的过程：
if ((p = tab[i = (n - 1) & hash]) == null) //如果当前位置没有元素，就把该值放到当前位置 tab[i] = newNode(hash, key, value, null); else{ for (int binCount = 0;; ++binCount) { if ((e = p.next) == null) { //在链表最后插入 p.next = newNode(hash, key, value, null); //binCount = 7，因为上边新插入一个， //所以当链表长度为8的时候，转换为二叉树 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st //只有当tab.length>64才真正会将链表转化为树， //否则进行扩容操作 treeifyBin(tab, hash); break; } p = e; } }除去链表转换树的操作，其他的代码都很简单。这里有一个点要注意的是为什么要当链表长度为8的时候转换为树呢？更大或者更小的值可以吗？ 红黑树可以实现二分查找，当长度为8的时候，log（8）=3，而链表平均查找长度为8/2=4，此时转换为红黑树才有意义。当长度为6时，虽然log6<6/2，但红黑树的生成也需要时间，所以选择6并不理想。所以hashMap选择长度为8转换为红黑树，长度为6退化为链表，中间隔一个值，可以有效的避免map不停的插入删除元素，导致链表和红黑树不断变换而带来更高的消耗。
接下来，我们再看put过程的最后一部分，扩容：
if (oldCap > 0) { if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } // 如果新的容量<Integer.MAX_VALUE/2 且旧的容量>=16（默认容量） // 新的阈值变为原来的2倍 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node<K, V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; if (e.next == null) //扩容前该位置只有一个值 newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) ((TreeNode<K, V>) e).split(this, newTab, j, oldCap); else { // preserve order Node<K, V> loHead = null, loTail = null; Node<K, V> hiHead = null, hiTail = null; Node<K, V> next; do { next = e.next; //扩容需要将原来的链表结点分在新数组下标为n和n+oldCap两个位置 //假设原数组长度为16，原数组下标为1的链表要分到1和17两个位置。 //原来计算下标是1111&e.hash，扩容后计算是11111&e.hash //后四位相同，所以只需要判断10000&e.hash是否等于1即可分开两个链表 //可能出现的情况，扩容后原链表并未拆分。 if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); if (loTail != null) { //与原来的next断开链接 loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } }这样，我们就将整个put流程梳理完成了。当我们清楚各部分代码的功能时，我们再回过头去看整个put过程，是不是就很流畅了。反回来我们看到key.hash值是hash(key)生成的，而不是直接取key.hashCode()，那么hash方法里边具体是怎样的操作呢？
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }该方法称为扰动函数，通过hashCode低16位与高16位异或，能够进一步散列完全，这样在后边的计算下标相与的时候，hash值同时包含高位和低位的特性。更不容易产生碰撞。 以上，就是整个put的过程，当我们完全掌握了put的过程后，再去看get、remove等方法，发现其实都大同小异。也都变的很好理解了。
