本文不介绍HashMap的相关API使用，重点分析一下HashMap底层原理及源码。对参考博客中写的好的地方直接搬运了过来，目的是加深记忆。

1、Map接口及实现类简介

JDK中的集合框架中存储k-v关系的根接口是java.util.Map，此接口主要有四个常用的实现类，分别是HashMap、Hashtable、LinkedHashMap和TreeMap，类继承关系如下图所示：

（1）HashMap
HashMap是平时开发中使用最多的k-v存储结构，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。HashMap最多只允许一条记录的key为null，允许多条记录的value为null。HashMap非线程安全的，可以使用ConcurrentHashMap线程安全的集合类。
（2）LinkedHashMap
LinkedHashMap是HashMap的一个子类，保存了记录的插入顺序，在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的，也可以在构造时带参数，按照访问次序排序。
（3）TreeMap
TreeMap实现SortedMap接口，能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器，当用Iterator遍历TreeMap时，得到的记录是排过序的。如果使用排序的k-v存储结构，建议使用TreeMap。在使用TreeMap时，key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator，否则会在运行时抛出java.lang.ClassCastException类型的异常。
（4）Hashtable
Hashtable是遗留类，很多映射的常用功能与HashMap类似，不同的是它承自Dictionary类，并且是线程安全的，任一时间只有一个线程能写Hashtable，并发性不如ConcurrentHashMap，因为ConcurrentHashMap引入了分段锁。Hashtable不建议在新代码中使用，不需要线程安全的场合可以用HashMap替换，需要线程安全的场合可以用ConcurrentHashMap替换。

2、HashMap源码浅析

2.1 底层数据结构

从数据结构上看，HashMap是由数组（又叫哈希桶数组） + 链表/红黑树实现的，JDK 1.8中引入了红黑树，当链表长度太长（默认超过8）时，链表就转换为红黑树，利用红黑树快速增删改查的特点提高HashMap的性能，HashMap底层数据结构如下图所示：

2.1.1 Node内部类

上图中不同颜色的圆点代表一个Node实例，数组中存放的对象也是Node实例，看一下Node内部类源码：

static class Node<K,V> implements Map.Entry<K,V> {
        // key经过hash算法得到的hash值，用来定位Node实例在数组中的索引
        final int hash;
        // 存储键值对中的key
        final K key;
        // 存储键值对中的value
        V value;
        // 为了解决哈希冲突引进的拉链法，指向链表中的下一个Node实例
        Node<K,V> next;
        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }
        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }
        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }
        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }

2.1.2 哈希冲突

2.1.1中的next指针是为了解决哈希冲突而设置的成员属性。哈希表为解决冲突，可以采用开放地址法和拉链法等来解决问题，JDK中HashMap采用了拉链法。拉链法简单来说就是数组加链表的结合，每个数组元素实际上都一个链表结构，当数据被Hash后，得到数组下标，把数据头插/尾插在对应下标元素的链表上，经过hash算法计算得到相同哈希值的key被挂在同一个链表上。
如果哈希桶数组很大，即使较差的Hash算法也会比较分散，如果哈希桶数组数组很小，即使好的Hash算法也会出现较多碰撞，所以就需要在空间成本和时间成本之间权衡，其实就是在根据实际情况确定哈希桶数组的大小，并在此基础上设计好的hash算法减少Hash碰撞。HashMap在哈希算法的设计上有自己的优化，详情见2.2节。

2.1.3 重要成员

这里介绍以下HashMap中一些重要的成员属性，在hash算法以及put\get等方法中这些成员属性都有体现：

// 哈希桶数组
transient Node<K,V>[] table;
// 当前HashMap集合中元素的个数
transient int size;
// 所能容纳的key-value对（Node实例）的最大个数
int threshold;
// 负载因子，默认为0.75
final float loadFactor;
// HashMap被修改的次数
int modCount;

• threshold是HashMap所能容纳的最大数据量的Node(键值对)最大个数，有公式：threshold = length * Load factor，当HashMap中Node实例的个数超过这个值时会进行扩容，扩容后的HashMap，threshold是之前的2倍；
• 默认的负载因子0.75是对空间和时间效率的一个平衡选择，建议大家不要修改；
• 要区分size、table的length和threshold：
  • size：当前HashMap集合中元素的个数；
  • length：哈希桶数组table的长度；
  • threshold：HashMap所能容纳的最大的Node实例个数。

在HashMap中，哈希桶数组table的长度length大小必须为2的n次方(一定是合数)，这是一种非常规的设计，常规的设计是把桶的大小设计为素数。相对来说素数导致冲突的概率要小于合数，具体证明可以参考http://blog.csdn.net/liuqiyao_01/article/details/14475159，Hashtable初始化桶大小为11，就是桶大小设计为素数的应用（Hashtable扩容后不能保证还是素数）。HashMap采用这种非常规设计，主要是为了在取模和扩容时做优化，同时为了减少冲突，HashMap定位哈希桶索引位置时，也加入了高位参与运算的过程，详细见2.2节。

2.2 hash方法

不管增加、删除、查找键值对，定位到哈希桶数组的位置都是第一步。前面说过HashMap的数据结构是数组和链表的结合，所以我们当然希望这个HashMap里面的元素位置尽量分布均匀些，尽量使得每个位置上的元素数量只有一个，那么当我们用hash算法求得这个位置的时候，马上就可以知道对应位置的元素就是我们要的，不用遍历链表，大大优化了查询的效率。HashMap定位数组索引位置，直接决定了hash方法的离散性能。JDK 1.7和JDK 1.8中源码如下：

// jdk1.8
static final int hash(Object key) {   
     int h;
     // h = key.hashCode() 为第一步 取hashCode值
     // h ^ (h >>> 16)  为第二步，让高位参与运算
     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// jdk1.7的源码，jdk1.8没有这个方法，但是在putVal方法中也有类似的逻辑
static int indexFor(int h, int length) {  
     // 第三步 取模运算
     return h & (length-1);  
}

总结一下HashMap中hash算法的步骤：

1. 取key的hashCode；
2. 高位运算；
3. 取模运算。

这里重点说明一下第二步和第三步。

2.2.1 高位运算

高位运算是将第一步得到的key的hashCode的高位能参与到hash算法中来，尤其针对哈希桶数组长度不大的情况。在JDK 1.7和JDK 1.8中都有高位运算的操作，这里主要介绍JDK 1.8中的高位运算。过程是通过hashCode()的高16位异或低16位实现的（(h = k.hashCode()) ^ (h >>> 16)），这么做可以在数组table的length比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中。
举例说明下，n为table的长度：

从图中可以看出，在最后一步（n-1) & hash中，当哈希桶长度n不大时，n-1的高位基本都是0，这样按位与操作的话，通过hash算法得到的值的高位不管是多少，与0按位与都是0，即hash算法得到的值的高位没有参与到最终计算下标的算法中来。因此才有了无符号右移16位，让高16位能与低16位在hash算法中按位异或计算hash，最终目的是让高16位也能参与到计算key在哈希桶中下标的算法中来。

2.2.2 length为什么是2的n次方

JDK 1.8中，哈希同数组的长度为2的n次方，且每次扩容也是2倍，这么设计的原因有两个：

• 定位哈希桶下标时尽可能减少哈希碰撞，提高查询效率；
• 提升哈希桶数组的空间利用率。

再回顾一下计算哈希桶下标的公式：index = （length-1）& hash，
举例，hash值分别为4、5，length长度分别为15、16，index值见下表：

上面的表格可以看出，当length不是2的n次方（15）时，hash值为4、5进行下标计算的结果都是0100，即发生了哈希碰撞，这样的后果是hash值为4、5的key对应的Node都会挂在同一个链表上，这样做get操作或者put操作的过程中会遍历链表，链表上挂的Node越多查询效率越低。而如果length的长度是2的n次方，这样的话length-1的低位就都是1了，避免了当length-1的低位是0时，hash对应的位无论是0还是1，按位与的结果都是0，导致index一样，造成哈希冲突。
为什么会提升哈希桶数组的空间利用率呢？回到上面的例子，当length为15时，无论hash值取多少，index的最后一位都是0，就会导致哈希桶中0001，0011，0101，1001，1011，0111，1101这几个位置（index最后一位是0）永远都不能挂链表了，空间浪费相当大。

2.2.3 取模运算

通常不考虑性能，最直观的做法是：index = hash mod length，index为key在哈希桶数组中的下标。但HashMap对取模运算也做了优化，也是取模运算用按位与运算代替的优化思想，具体为：X % 2^n = X & (2^n – 1)，下面就说说这个等式为什么成立。
假设n为3，则X & （2^3-1）就相当于取X的二进制的最后三位数。从二进制角度看，X / 8相当于X >> 3，即把X向右移3位，此时得到是X / 8的商，而被移掉的部分（后三位）就是余数，即X % 8。因此X % 2^n就等价于计算X的二进制的最后n位，这也正是X & (2^n – 1)计算得到的，因此上面等式成立。整个过程如下图所示：

由于位运算直接对内存数据进行操作，不需要转成十进制，因此处理速度比取余操作快得多。

2.3 put方法

JDK 1.8中put方法的整体流程如下：

过程总结如下：

1. 判断键值对数组table是否为空或为null，否则执行resize()进行扩容；
2. 根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向6，如果table[i]不为空，转向3；
3. 判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向4，这里的相同指的是hashCode以及equals；
4. 判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向5；
5. 遍历table[i]对应的链表，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；
6. 插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。

JDK 1.8中put方法源码如下：

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;
    // 步骤1：tab为空则扩容resize()
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 步骤2：计算index，如果tab[index]==null，则直接新建节点添加 
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 步骤3：链表头节点的key与put的key一致，直接覆盖value
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            // 步骤4：判断该链为红黑树，走红黑树的插入
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // 步骤5：该链为链表，遍历链表
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 链表长度大于8转换为红黑树进行处理
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // 遍历链表过程中如果找到key已经存在直接覆盖value
                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;
    // 步骤6：超过最大容量 就扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

2.4 扩容机制

由于HashMap底层是数组，不断往HashMap里put元素总有数组满的时候，此时就需要像ArrayList一样对数组动态扩容。

2.4.1 JDK 1.7

JDK 1.7没有引进红黑树，代码相对好理解一些，扩容对应的resize()方法源码如下：

// newCapacity为要扩容的新容量
void resize(int newCapacity) {
    // 引用扩容前的老数组
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        // 如果扩容前的数组大小已经达到最大(2^30)了，
        // 修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了
        threshold = Integer.MAX_VALUE;
        return;
    }
    // 初始化一个新的Entry数组
    Entry[] newTable = new Entry[newCapacity];
    // 调用transfer函数将数据转移到新的Entry数组里
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    // HashMap的table引用指向新的Entry数组
    table = newTable;
    // 修改阈值，table数组的length就是newCapacity
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

transfer源码如下：

void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    // 遍历老的数组table
    for (Entry<K,V> e : table) {
        // 遍历数组中每个元素对应的链表
        while(null != e) {
            Entry<K,V> next = e.next;
            // 如果需要重新hash，则重新调用hash算法对key进行rehash
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            // 根据hash/rehash后计算的hash值计算e在新的数组中的下标
            int i = indexFor(e.hash, newCapacity);
            // 将e头插在newTable[i]上
            e.next = newTable[i];
            newTable[i] = e;
            // 指向老链表中的下一个Node继续遍历老链表
            e = next;
        }
    }
}

举个例子，假设我们的hash算法就是简单的用key mod 一下哈希桶数组的大小，其中的哈希桶数组table的size=2， key = 3、7、5，put顺序依次为 5、7、3。在mod 2以后都冲突在table[1]这里了。这里假设负载因子 loadFactor=1，即当键值对的实际大小size大于table的实际大小时进行扩容。接下来的三个步骤是哈希桶数组长度由2 resize 成4，然后所有的Node重新rehash的过程。

2.4.2 JDK 1.8

JDK 1.8相比JDK 1.7在rehash这一步骤上做了优化。具体地在扩容过程中，JDK 1.8不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话扩容后的哈希桶数组中的索引没变，是1的话索引变成“原索引+oldCapacity”。这样可以把之前的哈希冲突的Node分散到新的bucket了。
下图可以明白这句话的意思，n为table的长度，图（a）表示扩容前的key1和key2两种key确定索引位置的示例，图（b）表示扩容后key1和key2两种key确定索引位置的示例，其中hash1是key1对应的哈希与高位运算结果：

元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：

2.5 get方法

JDK 1.8中get方法源码如下：

public V get(Object key) {
    Node<K,V> e;
    // 底层还是调用getNode方法来获取对应的Node，返回的是Node的value属性
    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;
    // 如果哈希桶数组不为空，且数组长度大于0，且哈希同数组对应index链表头节点不为空
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 如果key就是链表的头节点，直接返回头节点
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 如果key不是链表头节点，且头节点下一个节点不为null，则继续遍历链表
        if ((e = first.next) != null) {
            // 如果是红黑树，则走红黑树的查找
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            // 否则通过do-while循环遍历链表
            do {
                // 如果命中直接返回
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    // 都没命中直接返null
    return null;
}

相比put方法get方法的源码还是相对简单的。

3、HashMap为什么是线程不安全的

都知道HashMap是线程不安全的，如果需要使用线程安全的k-v存储结构建议使用ConcurrentHashMap，但HashMap为什么是线程不安全的呢？JDK 1.7和JDK 1.8中HashMap线程不安全的原因是不同的，具体为：

• JDK 1.7：
  • 表现：会造成链表死循环、数据丢失；
  • 原因：扩容时的transfer函数是线程不安全的，在将Node重新挂到新链表时会出现环形链表；
• JDK 1.8：
  • 表现：会造成数据覆盖；
  • 原因：put操作判断是否出现哈希碰撞时不是线程安全的，会出现哈希碰撞的Node覆盖的问题。

    3.1 JDK 1.7

    假设现在有两个线程A、B同时对下面这个HashMap进行扩容操作：
    
    正常扩容后的结果是下面这样的：
    
    当线程A执行到transfer函数的第11行代码时，CPU时间片耗尽，线程A被挂起。如下图中位置所示：

    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;
           }
       }
    }

    此时在线程A中，结合上面transfer函数中的代码，此时e没有头插在数组index为3的Node上，e=3，e.next=null，next=7，7和5还是相连着，如下图所示：
    
    线程A的时间片耗尽后，CPU开始执行线程B，并在线程B中成功的完成了数据迁移，如下图所示：
    
    结合JVM的内存模型（主内存和每个线程维护的工作内存），此时主内存中的newTable和table都是最新的（线程B更新的），也就是说：7.next=3、3.next=null。
    随后线程A获得CPU时间片继续执行newTable[i] = e，将3头插到新数组对应的位置，执行完此轮循环后线程A的情况如下：
    
    接着继续执行下一轮循环，此时e=7，从主内存中读取e.next时发现主内存中7.next=3，于是乎next=3，并将7采用头插法的方式放入新数组中，并继续执行完此轮循环，将e更新为next的值3，如下：
    
    执行下一次循环可以发现，next=e.next=3.next=null，所以此轮循环将会是最后一轮循环。接下来当执行完e.next=newTable[i]即3.next=7后，3和7之间就相互连接了（链表的死循环就这么形成了），当执行完newTable[i]=e后，3被头插法重新插入到链表中，执行结果如下图所示：
    
    至此transfer函数结束（while(null != e)循环不满足条件，跳出），线程A、B的扩容操作完成，很明显当线程A执行完后，HashMap中出现了环形结构，以后对该HashMap进行操作（需要遍历链表）时会出现死循环。并且从上图可以发现，元素5在扩容期间被莫名的丢失了，这就发生了数据丢失的问题。

    3.2 JDK 1.8

    JDK 1.7中的transfer函数在JDK 1.8中已经没有了，具体的数据迁移工作在JDK 1.8中的resize函数完成了，JDK 1.8中HashMap线程不安全表现在会出现数据覆盖的问题，原因是在put方法中，JDK 1.8的put源码如下：

    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;
    // 线程不安全的原因就是在这
    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);
                   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))))
                   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;
    }

    上面源码中的第七行if ((p = tab[i = (n - 1) & hash]) == null)是判断在put过程中，待put的key是否出现hash碰撞。假设两个线程A、B都在进行put操作，并且hash函数计算出的插入哈希桶的下标是相同的，当线程A执行完第七行代码后由于时间片耗尽导致被挂起，而线程B得到时间片后判断没有出现哈希碰撞，在该下标处插入了元素，完成了正常的插入；然后线程A获得时间片，由于之前已经进行了hash碰撞的判断没有哈希冲突，因此线程A直接进行插入，这就导致了线程B插入的数据被线程A覆盖了，从而线程不安全。

    参考

    Java 8系列之重新认识HashMap
    JDK1.7和JDK1.8中HashMap为什么是线程不安全的？
    为什么可以使用位运算(&)来实现取模运算(%)呢？
    一个非常巧妙的 hashcode 算法 return h & (length-1);
    Java 面试题（1）——java基础