Java集合框架 —— HashMap

声明：本文使用JDK1.8

HashMap 是我们平时开发过程中使用最多的 Java 集合框架之一，它继承 AbstractMap，实现 Map 接口，是一种 key-value，并允许使用空值和空键。

1 2	public class HashMap<K，V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {

从结构实现来讲，HashMap 是 数组+链表+红黑树（JDK1.8增加了红黑树部分）实现的，相比于Java7，Node可以被扩展成TreeNode。

HashMap类加载

//初始容量为16的大小
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//最大容量(1073741824)
static final int MAXIMUM_CAPACITY = 1 << 30;
//哈希表在其容量自动增加之前可以达到多满的一种尺度
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//链表中数据的临界值，如果达到8，就进行resize扩展，如果数组大于64则转换为树.
static final int TREEIFY_THRESHOLD = 8;
//如果链表的数据小于6，则从树转换为链表.
static final int UNTREEIFY_THRESHOLD = 6;
//如果数组的size大于64，则把链表进行转化为树
static final int MIN_TREEIFY_CAPACITY = 64;
transient Node<K,V>[] table;
//通过key计算hash值
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

对于HashMap初始化的容量是16的原因，可以看这里：漫画：什么是HashMap？,
感觉讲的还是挺详细的。之所以选择 16 这个数字，是服务于从 key 映射到 index 的算法。index = HashCode(Key) & (length - 1)，如果 length 是2的幂的话，则 length - 1 就是全是 1的二进制数，比如 16 - 1 = 1111，这样相当于是坐落在长度为 length 的 hashMap 上的位置只和 HashCode 的后四位有关，这只要给出的 HashCode 算法本身分布均匀，算出的index就是分布均匀的。

可以了解下漫画：高并发下的HashMap，不过这里的代码比较老。HashMap 在高并发下出现死锁，主要发生在 rehash 时，链表出现环链了。不过在Java8 中，对于链表超过8时，转化为红黑树，这有效的防止这个问题。

tableSizeFor

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

这个方法被调用的地方：

public HashMap(int initialCapacity, float loadFactor) {
    /**省略此处代码...**/
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

当实例化 HashMap 实例时，如果给定了初始容量initialCapacity，由于 HashMap 的 capacity 都是 2 的幂，因此这个方法用于找到大于等于 initialCapacity 的最小的2的幂。

Node

Java8中相对之前的版本增加了Node，从代码中可以看出，是一个哈希桶数组，实现Map.Entry接口，是一个键值对。

key 和 index

在 HashMap 中，下标的选择是计算key的hash值，具体公式是：(n - 1 ) & hash 。其中 n 是 hashmap table[] 数组的长度，hash 是当前key的hash值。& 是与运算，两个数都转为二进制，然后从高位开始比较，如果两个数都为1则为1，否则为0。详细的可以看之前的那篇链接。

hasCode 和 equals

HashMap 重写了 hasCode 和 equals，源码如下：

public final int hashCode() {
    return Objects.hashCode(key) ^ Objects.hashCod(value);
}
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;
}

hash

HashMap 的 hash 计算方法。key的hash值高16位不变，低16位与高16位异或作为key的最终hash值。h>>>16 无符号右移16位，高位补0，任何数跟0异或都是其本身，因此key的hash值高16位不变。异或位运算(0 ^ 1 得 1、1 ^ 1 得 0、0 ^ 0 得 0、1 ^ 0 得 1)

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

初始化

HashMap提供三种初始化HashMap：

//默认初始化16，加载因子0.75
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
//给定容量，加载因子0.75
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//使用与指定的Map相同的映射构造一个新的HashMap
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

get相关

get方法

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;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {//(n-1)&hash 位置不为null
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)//遍历红黑树，得到节点值
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {//遍历链表，得到节点值，通过hash和equals(key)确认所查找元素。
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

contains

public boolean containsKey(Object key) {
    return getNode(hash(key), key) != null;
}

public boolean containsValue(Object value) {
    Node<K,V>[] tab; V v;
    if ((tab = table) != null && size > 0) {
        for (int i = 0; i < tab.length; ++i) {
            for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                if ((v = e.value) == value ||
                    (value != null && value.equals(v)))
                    return true;
            }
        }
    }
    return false;
}

put

put函数是想HashMap中添加键值。

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;
    //table空||length为0
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;// 分配空间，初始化
    //hash所在位置(第i个桶)为null，直接put
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {//tab[i]有元素，则需要遍历结点后再添加
        Node<K,V> e; K k;
        // hash、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) {//死循环，直到break
                if ((e = p.next) == null) {//表尾仍没有key相同节点,新建节点
                    p.next = newNode(hash, key, value, null);
                    //若链表数量大于阀值8【9个】，则调用treeifyBin方法，仅当tab.length大于64才将链表改为红黑树
                    // 如果tab.length<64或table=null，则重构一下链表
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        treeifyBin(tab, hash);//binCount>=9则链表转树
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;// hash、key均相等，说明此时的节点==待插入节点，更新
                p = e;//更新p指向下一个节点
            }
        }
        //当前节点e = p.next不为null，即链表中原本存在了相同key，则返回oldValue
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            //onlyIfAbsent值为false，参数主要决定当该键已经存在时，是否执行替换
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);//调用linkedHashMap,move node to last
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)//++size后再检测是否到了阀值
        resize();
    afterNodeInsertion(evict);//调用linkedHashMap,true则possibly remove eldest
    return null;// 原hashMap中不存在相同key的键值对，则在插入键值对后，返回null。
}

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    //当tab长度小于64的时候，只是扩容，而不是转化成红黑树
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

扩容

先了解一些字段含义：

// HashMap的阈值，用于判断是否需要调整HashMap的容量（threshold = 容量*加载因子）
int threshold;
// 加载因子实际大小
final float loadFactor;
int size;                 //实际存在的键值对数量
transient volatile int modCount; // HashMap被改变的次数

看下源码里面扩容的代码：

final Node<K,V>[] resize() {
     Node<K,V>[] oldTab = table; //赋值老的Node
     int oldCap = (oldTab == null) ? 0 : oldTab.length;//老的Node的大小
     int oldThr = threshold;  //旧阀值
     int newCap, newThr = 0; // 新容量，新阀值
     if (oldCap > 0) {
         //扩容前的数组大小如果已经达到最大(2^30)了
         if (oldCap >= MAXIMUM_CAPACITY) {
           ///修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了
             threshold = Integer.MAX_VALUE;
             return oldTab;
         }
         //大于初始容量，旧容量2倍小于最大容量
         else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                  oldCap >= DEFAULT_INITIAL_CAPACITY)
             newThr = oldThr << 1; //2倍
     }// oldCap=0 ,oldThr>0，threshold(新的扩容resize临界值)
     else if (oldThr > 0)
         newCap = oldThr;//新容量=旧阀值（扩容临界值）
     else { // oldCap=0 ,oldThr=0，调用默认值来初始化
         newCap = DEFAULT_INITIAL_CAPACITY;//16
         newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//0.75*16
     }
     if (newThr == 0) {//新阀值为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;
     // table初始化,bucket copy到新bucket，分链表和红黑树
     if (oldTab != null) { // 不为空则挨个copy，影响效率！！
         for (int j = 0; j < oldCap; ++j) {
             Node<K,V> e;
             if ((e = oldTab[j]) != null) {//先赋值再判断
                 oldTab[j] = null;//置null，主动GC
                 if (e.next == null)
                 //1.6 的indexFor，计算key；tableSizeFor性能优化
                     newTab[e.hash & (newCap - 1)] = e;//hash&(length-1)
                 else if (e instanceof TreeNode) // 红黑树
                     ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                 else { //链表，preserve order保持顺序
                   //一个桶中有多个元素，遍历将它们移到新的bucket或原bucket
                     Node<K,V> loHead = null, loTail = null;//lo原bucket的链表指针
                     Node<K,V> hiHead = null, hiTail = null;//hi新bucket的链表指针
                     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) {//原bucket位置的尾指针不为空(即还有node)
                         loTail.next = null;//链表最后得有个null
                         newTab[j] = loHead;//链表头指针放在新桶的相同下标(j)处
                     }
                     if (hiTail != null) { 
                         hiTail.next = null;
                         newTab[j + oldCap] = hiHead;
                     }
                 }
             }
         }
     }
     return newTab;
 }

put(K key, V value)的逻辑：

①.判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容；

②.根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向⑥，如果table[i]不为空，转向③；

③.判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向④，这里的相同指的是hashCode以及equals；

④.判断table[i] 是否为TreeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤；

⑤.遍历table[i]，判断链表长度是否大于8，大于8的话，同时需要判断 table 数组大小是否大于64，如果只满足前一个条件，只进行扩容；若果两个条件都满足，把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；

⑥.插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。

JDK7和JDK8之后，HashMap 的区别？

1.7中采用数组+链表，1.8采用的是数组+链表/红黑树，即在1.7中链表长度超过一定长度后就改成红黑树存储。
1.7扩容时需要重新计算哈希值和索引位置，1.8并不重新计算哈希值，巧妙地采用和扩容后容量进行&操作来计算新的索引位置。
1.7是采用表头插入法插入链表，1.8采用的是尾部插入法。

在1.7中采用表头插入法，在扩容时会改变链表中元素原本的顺序，以至于在并发场景下导致链表成环的问题；在1.8中采用尾部插入法，在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题了。

蒋先森のBlog