数据结构

JDK1.7之前HashMap采用的数据结构为数组+链表，使用这种结构是为了解决哈希冲突（拉链法）。JDK1.8之后还引入了红黑树，当链表长度达到一个阈值时该链表就会转化为红黑树。

数组元素和链表结点

JDK1.7之前为Entry，JDK1.8为Node，两者只是名称不同。

Entry（或Node）中存放着键值对、键的哈希值，并且指向下一个结点。

/** 
 * Entry类实现了Map.Entry接口
 * 即 实现了getKey()、getValue()、equals(Object o)和hashCode()等方法
**/  
static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;  // 键
    V value;  // 值
    Entry<K,V> next; // 指向下一个节点 ，也是一个Entry对象，从而形成解决hash冲突的单链表
    int hash;  // hash值

    /** 
     * 构造方法，创建一个Entry 
     * 参数：哈希值h，键值k，值v、下一个节点n 
     */  
    Entry(int h, K k, V v, Entry<K,V> n) {  
        value = v;  
        next = n;  
        key = k;  
        hash = h;  
    }  

    // 返回 与 此项 对应的键
    public final K getKey() {  
        return key;  
    }  

    // 返回 与 此项 对应的值
    public final V getValue() {  
        return value;  
    }  

    public final V setValue(V newValue) {  
        V oldValue = value;  
        value = newValue;  
        return oldValue;  
    }  

   /** 
     * equals（）
     * 作用：判断2个Entry是否相等，必须key和value都相等，才返回true  
     */ 
      public final boolean equals(Object o) {  
        if (!(o instanceof Map.Entry))  
            return false;  
        Map.Entry e = (Map.Entry)o;  
        Object k1 = getKey();  
        Object k2 = e.getKey();  
        if (k1 == k2 || (k1 != null && k1.equals(k2))) {  
            Object v1 = getValue();  
            Object v2 = e.getValue();  
            if (v1 == v2 || (v1 != null && v1.equals(v2)))  
                return true;  
        }  
        return false;  
    }  

    /** 
     * hashCode（） 
     */ 
    public final int hashCode() { 
        return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());  
    }  

    public final String toString() {  
        return getKey() + "=" + getValue();  
    }  

    /** 
     * 当向HashMap中添加元素时，即调用put(k,v)时， 
     * 对已经在HashMap中k位置进行v的覆盖时，会调用此方法 
     * 此处没做任何处理 
     */  
    void recordAccess(HashMap<K,V> m) {  
    }  

    /** 
     * 当从HashMap中删除了一个Entry时，会调用该函数 
     * 此处没做任何处理 
     */  
    void recordRemoval(HashMap<K,V> m) {  
    } 

}

红黑树结点

HashMap中红黑树结点采用TreeNode类来实现：

/**
 * 红黑树节点 实现类：继承自LinkedHashMap.Entry<K,V>类
 */
 static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {  

   // 属性 = 父节点、左子树、右子树、删除辅助节点 + 颜色
   TreeNode<K,V> parent;  
   TreeNode<K,V> left;   
   TreeNode<K,V> right;
   TreeNode<K,V> prev;   
   boolean red;   

   // 构造函数
   TreeNode(int hash, K key, V val, Node<K,V> next) {  
       super(hash, key, val, next);  
   }  

   // 返回当前节点的根节点  
   final TreeNode<K,V> root() {  
       for (TreeNode<K,V> r = this, p;;) {  
           if ((p = r.parent) == null)  
               return r;  
           r = p;  
       }  
   } 

重要字段

容量（capacity）

容量指的是HashMap中数组的长度，它的值必须是2的N次幂。初始容量为16，最大不可超过2的30次方。

// 默认初始容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;

加载因子（factor）

加载因子决定了HashMap在自动增加时能达到多大载量，它与容量一起决定每次扩容的阈值。

// 实际加载因子
final float loadFactor;
// 默认加载因子 = 0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;

加载因子越大，到达扩容阈值时哈希表填满的元素越多，空间利用率越高，但是哈希冲突也更多，使得链表长度更长，HashMap的查找效率变低。反之查找效率变高，但是空间利用率变低了。如下图：

扩容阈值（threshold）

当哈希表所存放的元素数量≥扩容阈值时，就会触发哈希表的resize操作进行扩容。扩容阈值等于容量乘以加载因子。

// 扩容阈值 = 容量 x 加载因子
int threshold;

红黑树相关

// 1. 树化阈值，即链表转成红黑树的阈值，在存储数据时，当链表长度 > 该值时，则将链表转换成红黑树
static final int TREEIFY_THRESHOLD = 8; 
// 2. 桶的链表还原阈值：即 红黑树转为链表的阈值，当在扩容（resize（））时（此时HashMap的数据存储位置会重新计算），在重新计算存储位置后，当原有的红黑树内数量 < 6时，则将 红黑树转换成链表
static final int UNTREEIFY_THRESHOLD = 6;
// 3. 最小树形化容量阈值：即 当哈希表中的容量 > 该值时，才允许树形化链表
// 否则，若桶内元素太多时，则直接扩容，而不是树形化
// 为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD
static final int MIN_TREEIFY_CAPACITY = 64;

JDK1.8与JDK1.7的差异

构造方法

HashMap提供了四个构造方法，需要注意的是，这四个方法中都没有进行哈希表的初始化，哈希表的初始化工作实际是在第一次put元素时才会进行。这里仅贴出可自定义初始容量和加载因子的构造：

/**
 * Constructs an empty <tt>HashMap</tt> with the specified initial
 * capacity and load factor.
 *
 * @param  initialCapacity the initial capacity
 * @param  loadFactor      the load factor
 * @throws IllegalArgumentException if the initial capacity is negative
 *         or the load factor is nonpositive
 */
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);
}

tableSizeFor()方法类似于JDK1.7中inflateTable()里的roundUpToPowerOf2(toSize)，会根据传入的cap值返回大于cap的最小2的n次幂。源码如下：

/**
 \* Returns a power of two size for the given target capacity.
 */
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;
}

注意此处的扩容阈值threshold并不是真正要用的阈值，最终的阈值在putVal方法中计算。这里将扩容阈值计算好，后面直接可以替换初始容量。

添加元素

对比：

JDK1.8与1.7最主要的差别就是每次向HashMap中添加元素都要额外考虑红黑树的情况。

计算hash值

先调用Key对象本身的hashCode()方法计算出hash值，再进行hash扰动。

 // JDK 1.7实现：将 键key 转换成 哈希码（hash值）操作  = 使用hashCode() + 4次位运算 + 5次异或运算（9次扰动）
 static final int hash(int h) {
   h ^= k.hashCode(); 
   h ^= (h >>> 20) ^ (h >>> 12);
   return h ^ (h >>> 7) ^ (h >>> 4);
}

 // JDK 1.8实现：将 键key 转换成 哈希码（hash值）操作 = 使用hashCode() + 1次位运算 + 1次异或运算（2次扰动）
 // 1. 取hashCode值： h = key.hashCode() 
 // 2. 高位参与低位的运算：h ^ (h >>> 16)  
 static final int hash(Object key) {
      int h;
       return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
       // a. 当key = null时，hash值 = 0，所以HashMap的key 可为null      
       // 注：对比HashTable，HashTable对key直接hashCode（），若key为null时，会抛出异常，所以HashTable的key不可为null
       // b. 当key ≠ null时，则通过先计算出 key的 hashCode()（记为h），然后 对哈希码进行 扰动处理： 按位 异或（^） 哈希码自身右移16位后的二进制
}

插入元素

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 若哈希表为空，则通过resize()方法创建 
    // 所以哈希表的初始化其实是在resize()方法中完成的
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;

    // 注意这里tab数组下表计算为i = (n - 1) & hash，在jdk1.7中是个单独的函数indexFor()完成的
    // 如果数组中该下表为空，则表示没有哈希冲突，直接新建一个数组元素存入
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        // 如果存在哈希冲突
        Node<K,V> e; K k;
        // 判断是否存在Key值相同，相同则覆盖
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // Key值不相同，判断需要插入的数据结构是否是红黑树
        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;
            }
        }
        // key已存在，新value替换旧value
        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;
}

扩容机制

上面我们提到了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)
            newThr = oldThr << 1; // 扩充阈值也翻倍
    }
    // 若旧数组长度等于0，表示哈希表还未初始化，则将扩充阈值赋给新数组容量
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               
        // 扩充阈值为不大于0则直接使用默认值
        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;
    if (oldTab != null) {
        // 遍历旧数组，把每个bucket都移动到新的buckets中
        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 {
                        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;
}

JDK1.8扩容时，数据存储位置重新计算的方式如图所示：

数组位置转换示意：

获取数据

get()函数的原理与put()基本相同，先获取扰动后的hash值，然后计算数组下标，接着依次从数组、红黑树、链表中读取数据，然后返回数据。

/**
   * 函数原型
   * 作用：根据键key，向HashMap获取对应的值
   */ 
   map.get(key)；


 /**
   * 源码分析
   */ 
   public V get(Object key) {
    Node<K,V> e;
    // 1. 计算需获取数据的hash值
    // 2. 通过getNode（）获取所查询的数据 ->>分析1
    // 3. 获取后，判断数据是否为空
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

/**
   * 分析1：getNode(hash(key), key))
   */ 
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;

    // 1. 计算存放在数组table中的位置
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {

        // 4. 通过该函数，依次在数组、红黑树、链表中查找（通过equals（）判断）
        // a. 先在数组中找，若存在，则直接返回
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;

        // b. 若数组中没有，则到红黑树中寻找
        if ((e = first.next) != null) {
            // 在树中get
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);

            // c. 若红黑树中也没有，则通过遍历，到链表中寻找
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

重点及细节Q&A

HashMap如何解决哈希冲突？

HashMap采用拉链法解决哈希冲突，配合哈希扰动以及扩容机制，使得数据在数组中分布得更加均匀，数据结构上采用数组、链表和红黑树优化哈希冲突。

为什么哈希数组的长度必须为2的N次幂？

为什么采用哈希码&数组长度（h&（n - 1））的方式计算存储数组下标？

这两个问题是类似的。如果在设计时要提升HashMap性能，那么我们就需要减少哈希冲突，让数据优先存满数组，再依次加入链表中。那么可以采用哈希码除以数组长度再取余的方式计算存储数组下标，也就是 index = hash % n，但是这种方式计算下标效率太低（每次计算都要大量除法操作再取余）。

后来设计师想到可以采用与运算，若一个每一位都为1的二进制数（数组长度-1）与另一个数（哈希码）相与，和取余操作得到的结果是相同的，但是位运算效率自然更高。要保证这个二进制数始终每位为1，那就必须使数组长度始终为2的N次幂（再减一）。

为什么HashMap具备下述特点：键-值（key-value）都允许为空、线程不安全、不保证有序、存储位置随时间变化

为什么 HashMap 中 String、Integer 这样的包装类适合作为 key 键

由于默认的hashCode()方法（Object中）是根据地址值进行计算的，若两个Key值相等，但是地址不同的话，使用默认的hashCode()方法会出现相同Key不同hash值的情况。除此之外，默认的equals()方法也是直接比较对象地址，所以也需要重写。而String和Integer中都重写了hashCode()和equals()方法，保证了hash值的准确定，并且都为final类，保证了key的不可更改性。

因此，若是用自定义类作为HashMap的键的话，必须重写hashCoe()和equals()方法，并且最好用final修饰。

参考

JDK1.8 - HashMap.java

JDK1.7 - HashMap.java

Java源码分析：HashMap 1.8 相对于1.7 到底更新了什么？