根据代码可以总结插入逻辑如下:

1. 先调用 hash() 方法计算哈希值
2. 然后调用 putVal() 方法中根据哈希值进行相关操作
3. 如果当前 哈希表内容为空，新建一个哈希表
4. 如果要插入的桶中没有元素，新建个节点并放进去
5. 否则从桶中第一个元素开始查找哈希值对应位置
   
   1. 如果桶中第一个元素的哈希值和要添加的一样，替换，结束查找
   2. 如果第一个元素不一样，而且当前采用的还是 JDK 8 以后的树形节点，调用 putTreeVal() 进行插入
   3. 否则还是从传统的链表数组中查找、替换，结束查找
   4. 当这个桶内链表个数大于等于 8，就要调用 treeifyBin() 方法进行树形化
6. 最后检查是否需要扩容

插入过程中涉及到几个其他关键的方法 ：

• hash():计算对应的位置
• resize():扩容
• putTreeVal():树形节点的插入
• treeifyBin():树形化容器

HashMap 在 JDK1.8 新增树形化相关的内容比较多，下一篇介绍，接下来先介绍传统的 HashMap 相关内容。

4.HashMap 中的哈希函数 hash() **

HashMap 中通过将传入键的 hashCode 进行无符号右移 16 位，然后进行按位异或，得到这个键的哈希值。

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

看看源码里的注释怎么说的：

Computes key.hashCode() and spreads (XORs) higher bits of hash to lower. Because the table uses power-of-two masking, sets of hashes that vary only in bits above the current mask will always collide. (Among known examples are sets of Float keys holding consecutive whole numbers in small tables.) So we apply a transform that spreads the impact of higher bits downward. There is a tradeoff between speed, utility, and quality of bit-spreading. Because many common sets of hashes are already reasonably distributed (so don’t benefit from spreading), and because we use trees to handle large sets of collisions in bins, we just XOR some shifted bits in the cheapest possible way to reduce systematic lossage, as well as to incorporate impact of the highest bits that would otherwise never be used in index calculations because of table bounds.

大概意思就是：

由于哈希表的容量都是 2 的 N 次方，在当前，元素的 hashCode() 在很多时候下低位是相同的，这将导致冲突（碰撞），因此 1.8 以后做了个移位操作：将元素的 hashCode() 和自己右移 16 位后的结果求异或。

由于 int 只有 32 位，无符号右移 16 位相当于把高位的一半移到低位：

举个栗子：

（图片来自 http://yikun.github.io/2015/04/01/Java-HashMap%E5%B7%A5%E4%BD%9C%E5%8E%9F%E7%90%86%E5%8F%8A%E5%AE%9E%E7%8E%B0/）

这样可以避免只靠低位数据来计算哈希时导致的冲突，计算结果由高低位结合决定，可以避免哈希值分布不均匀。

而且，采用位运算效率更高。

5.HashMap 中的初始化/扩容方法 resize() **

每次添加时会比较当前元素个数和阈值：

    //如果超出阈值，就得扩容
    if (++size > threshold)
        resize();

扩容：

   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 (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        //新的容量为旧的两倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            //如果旧容量小于等于 16，新的阈值就是旧阈值的两倍
            newThr = oldThr << 1; // double threshold
    }
    //如果旧容量为 0 ，并且旧阈值>0，说明之前创建了哈希表但没有添加元素，初始化容量等于阈值
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        //旧容量、旧阈值都是0，说明还没创建哈希表，容量为默认容量，阈值为 容量*加载因子
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    //如果新的阈值为 0 ，就得用 新容量*加载因子 重计算一次
    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;
    //接下来就得遍历复制了
    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 { //保留旧哈希表桶中链表的顺序
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    //do-while 循环赋值给新哈希表
                    do {
                        next = e.next;
                        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) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

扩容过程中几个关键的点：

• 新初始化哈希表时，容量为默认容量，阈值为 容量*加载因子
• 已有哈希表扩容时，容量、阈值均翻倍
• 如果之前这个桶的节点类型是树，需要把新哈希表里当前桶也变成树形结构
• 复制给新哈希表中需要重新索引（rehash），这里采用的计算方法是
  
  • e.hash & (newCap - 1)，等价于 e.hash % newCap

结合扩容源码可以发现扩容的确开销很大，需要迭代所有的元素，rehash、赋值，还得保留原来的数据结构。

所以在使用的时候，最好在初始化的时候就指定好 HashMap 的长度，尽量避免频繁 resize()。

6.HashMap 的获取方法 get() **

HashMap 另外一个经常使用的方法就是 get(key)，返回键对应的值:

如果 HashMap 中包含一个键值对 k-v 满足：

(key == null ? k == null : key.equals(k))

就返回值 v，否则返回 null;

public V get(Object key) {
    Node<K,V> e;
    //还是先计算 哈希值
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    //tab 指向哈希表，n 为哈希表的长度，first 为 (n - 1) & hash 位置处的桶中的头一个节点
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        //如果桶里第一个元素就相等，直接返回
        if (first.hash == hash &&
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        //否则就得慢慢遍历找
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                //如果是树形节点，就调用树形节点的 get 方法
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                //do-while 遍历链表的所有节点
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

查找 方法比较简单:

• 先计算哈希值;
• 然后再用 (n - 1) & hash 计算出桶的位置;
• 在桶里的链表进行遍历查找。

时间复杂度一般跟链表长度有关，因此哈希算法越好，元素分布越均匀，get() 方法就越快，不然遍历一条长链表，太慢了。

不过在 JDK 1.8 以后 HashMap 新增了红黑树节点，优化这种极端情况下的性能问题。

总结

1.HashMap 有那么多优点（见文首），也有个缺点：不是同步的。

当多线程并发访问一个 哈希表时，需要在外部进行同步操作，否则会引发数据不同步问题。

你可以选择加锁，也可以考虑用 Collections.synchronizedMap 包一层，变成个线程安全的 Map：

Map m = Collections.synchronizedMap(new HashMap(...));

最好在初始化时就这么做。

2.HashMap 三个视图返回的迭代器都是 fail-fast 的：如果在迭代时使用非迭代器方法修改了 map 的内容、结构，迭代器就会报 ConcurrentModificationException 的错。

3.当 HashMap 中有大量的元素都存放到同一个桶中时，这时候哈希表里只有一个桶，这个桶下有一条长长的链表，这个时候 HashMap 就相当于一个单链表，假如单链表有 n 个元素，遍历的时间复杂度就是 O(n)，完全失去了它的优势。

针对这种情况，JDK 1.8 中引用了 红黑树（时间复杂度为 O(logn)） 优化这个问题。

4.为什么哈希表的容量一定要是 2的整数次幂?

首先，capacity 为 2的整数次幂的话，计算桶的位置 h&(length-1) 就相当于对 length 取模，提升了计算效率；

其次，capacity 为 2 的整数次幂的话，为偶数，这样 capacity-1 为奇数，奇数的最后一位是 1，这样便保证了 h&(capacity-1) 的最后一位可能为 0，也可能为 1（这取决于h的值），即与后的结果可能为偶数，也可能为奇数，这样便可以保证散列的均匀性；

而如果 capacity 为奇数的话，很明显 capacity-1 为偶数，它的最后一位是 0，这样 h&(capacity-1) 的最后一位肯定为 0，即只能为偶数，这样任何 hash 值都只会被散列到数组的偶数下标位置上，这便浪费了近一半的空间。

摘自： https://github.com/GeniusVJR/LearningNotes/blob/master/Part2/JavaSE/HashMap%E6%BA%90%E7%A0%81%E5%89%96%E6%9E%90.md

因此，哈希表容量取 2 的整数次幂，有以下 2 点好处：

1. 使用减法替代取模，提升计算效率；
2. 为了使不同 hash 值发生碰撞的概率更小，尽可能促使元素在哈希表中均匀地散列。

5.HashMap 允许 key, value 为 null，同时他们都保存在第一个桶中。

看代码，添加时先调用 hash()：

public V put(K key, V value) {
    //先调用 hash() 方法计算位置
    return putVal(hash(key), key, value, false, true);
}

而在计算哈希值时，如果为 null 就直接返回 0 ，说明了这一点：

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

6.HashMap 中 equals() 和 hashCode() 有什么作用？

HashMap 的添加、获取时需要通过 key 的 hashCode() 进行 hash()，然后计算下标 ( n-1 & hash)，从而获得要找的同的位置。

当发生冲突（碰撞）时，利用 key.equals() 方法去链表或树中去查找对应的节点。

7.你知道 hash 的实现吗？为什么要这样实现？

在 JDK 1.8 的实现中，是通过 hashCode() 的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)。

主要是从速度、功效、质量 来考虑的，这么做可以在桶的 n 比较小的时候，保证高低 bit 都参与到 hash 的计算中，同时位运算不会有太大的开销。

摘自：http://yikun.github.io/2015/04/01/Java-HashMap%E5%B7%A5%E4%BD%9C%E5%8E%9F%E7%90%86%E5%8F%8A%E5%AE%9E%E7%8E%B0/

下篇文章介绍 HashMap 在 JDK 1.8 新增的红黑树结构，点击查看

Thanks

https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html

http://blog.csdn.net/eson_15/article/details/51158865

http://blog.csdn.net/q291611265/article/details/46763053

http://yikun.github.io/2015/04/01/Java-HashMap%E5%B7%A5%E4%BD%9C%E5%8E%9F%E7%90%86%E5%8F%8A%E5%AE%9E%E7%8E%B0/

https://github.com/GeniusVJR/LearningNotes/blob/master/Part2/JavaSE/HashMap%E6%BA%90%E7%A0%81%E5%89%96%E6%9E%90.md

http://www.nowamagic.net/librarys/veda/detail/1273