HashMap 源码分析

HashMap是非常常用的键值对类型。本文主要讲述了HashMap的思维以及其重要或者常用的put，get，remove以及resize函数。

首先Java定义了java.util.Map的接口，而常用的实现类型主要有HashMap、ConcurrentHashMap、LinkedHashMap和TreeMap。对于原来常用HashTable在不强调线程安全性时可以用HashMap替代（也就是说HashMap是线程不安全的），而在线程安全的情况下用ConcurrentHashMap替代。

总体结构

首先HashMap在Java1.8之后修改了其部分实现方式，将原来“数组+链表”的实现方式改为现在的“数组+链表+红黑树”的实现方式，采用红黑树的实现方式，增强了对于数据查找、删除、修改等性能，对于增加来说，应该是减慢了，但是个人觉得对于增加影响非常小。

红黑树，RBTree，平衡二叉查找树的一种，具有良好的查找性能。他有五点要求：1、任何一个节点都有颜色，黑色或者红色；2、根结点是黑色的；3、父子节点之间不能出现两个连续的红节点；4、任何一个节点向下遍历到其子孙的叶子节点，所经过的黑节点个数必须相等；5、空节点被认为是黑色的。其实现方式比较复杂，若有时间我看完其源码再做分析。

冲突的含义：是指当两个不同的键值对（key不相同）在put的时候hash(key)所得的值是相同的，他们会放到哈希桶数组的同一下标位置，形成链表或者红黑树，这种情况就是冲突。当然，在HashMap中我们要尽量的选取比较好的哈希函数来避免冲突，但是大多数情况冲突是不能完全避免的，所以要引入链表和红黑树来解决冲突。

节点

首先，HashMap类中包含了多个内部类，如Node、KeySet、Values、EntrySet等，在此就不一一列举。Node是HashMap中非常重要的类型，它代表每个节点，包含（hash，key，value，next）等属性，源码如下：

static class Node<K,V> implements Map.Entry<K,V> {
   final int hash;
   final K key;
   V value;
   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;
   }
}

先来说说Node每个属性的含义，1、hash：代表存储是的哈希值，一般由hash(key)函数得出；2、key；3、value：这两个就是键和值；4、next：是指指向下一个节点的指针。

HashMap重要字段

1、transient Node[] table; table表示哈希桶数组，transient表示其不参与序列化，即修饰的变量不是该对象持久化的部分。这个修饰符需要注意两点：1、只能修饰变量，本地变量不能被修饰（本地变量：局部变量）；2、静态变量（static修饰）不管有没有被修饰都不能序列化。

2、transient int size; size是指当前存储的键值对数目。

3、int threshold; threshold表示最大容纳的键值对个数，一般为threshold=length*loadFactor；length是指哈希桶数组长度，在当前键值对数目超过这个值时，哈希桶数组会扩容。

4、final float loadFactor; loadFactor，负载因子（默认或缺省为0.75）。

构造函数

HashMap有4个构造函数，其一示例如下：

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

其他几个构造函数是将loadFactor缺省或者将参数全部缺省，以及其拷贝构造函数。注意的是对于上述构造函数中将参数loadFactor赋值给负载因子，并将参数initialCapacity通过tableSizeFor函数操作后传给threshold，由上面所述，threshold是最大容纳的键值对个数，而initialCapacity理论上应该是初始化容量，即哈希桶数组初始化长度，而且这儿并没有初始化哈希桶数组长度，因此这儿赋值是跟其思维上不符合的，那么我们的threshold最终究竟是多少，以及在哪儿初始化了哈希桶数组长度呢？这一点，我会在后面分析put方法时讲到。

很好奇tableSizeFor函数是做了什么操作？他是在函数里面进行了一系列的移位操作，保证初始化容量为2的n次方。例如，我们new一个HashMap(11)传入的参数为11，按照之前的观点，初始化哈希桶长度应该是11，但是其进行一系列移位操作后，使得初始化容量为16。关于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;
}

get操作

这儿的思路是非常简单的，就是通过hash(key)&(table.length-1)得到对应的哈希桶数组位置，再去对应的位置查找，当然现在对应的位置可能是链表类型，也可能是RBTree类型，对于Java1.7时，是只有链表类型，因此遍历链表类型可以查找出对于的字段；而对于Java1.8添加了红黑树结构之后，就需要判断当前对应的table[j]的node是不是TreeNode，如果是则通过红黑树去查找，不是则通过链表查找。

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) {
       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 {
               if (e.hash == hash &&
                   ((k = e.key) == key || (key != null && key.equals(k))))
                   return e;
           } while ((e = e.next) != null);
       }
   }
   return null;
}

put操作

这部分相对于get操作就复杂了许多，需要注意的一点是put操作会有返回值，当该key有对应的值时，put操作会返回原来的值（至于覆盖与否，我接下来分析putVal函数参数时会讲到），当对应key不存在时则返回null。接下来，我们分为几种情况讨论put操作：

1、table为空或者table.length为0的时候。这种情况会出现在两个时候，分别是刚刚new了一个HashMap和前面操作将table删掉的情况（删除操作在后面的章节会做另外的讨论）。我们前面构造函数部分提到过，在构造的时候只是初始化了负载因子loadFactor，和将初始化哈希桶长度赋值给了最大容纳的键值对个数threshold。并没有对于哈希桶数组table做初始化，因此在这儿table是空NULL，就触发了扩容，在扩容的时候就会将threshold赋值给table的长度length，而真正的threshold在这儿赋值成length*loadFactor。这里解决了我们之前对于table在哪儿赋值以及threshold最终值的疑问。

2、一般情况。就是将key转换成对应的哈希值从而找到对应的数组下标位置，再判断该位置是否存储有数据，该数据的key是否就是我们需要put的数据的key，存储的是链表还是红黑树，将数据插入就好，当然这儿就有一个情况——当插入之后，该链表的长度（即节点数）刚好超过8，那么根据我们一般的猜想就是转换为红黑树RBTree，其实不然。这儿分为两种情况，第一种（也是最特殊的一种），当链表长度超过8的时候，但是总的哈希表容量size并没有达到MIN_TREEIFY_CAPACITY=64，这时候会出发扩容的情况（扩容一般上会降低同一点的冲突，具体情况我会在扩容一章resize的时候讲到；第二种情况就是size达到或超过64，大家众所周知的转为红黑树。

既然有链表转化为红黑树的操作，那么想必有红黑树转化为链表的操作，这个函数就是untreeify，他会在红黑树的节点数减少到6的时候（即小于等于6）将红黑树转化为链表。

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

注意putVal函数中后面有两个参数onlyIfAbsent和evict。onlyIfAbsent为ture的时候表示仅当该key缺省（即不存在）时才将该键值对加入HashMap。evict表示是否覆盖旧值，一般情况下evict是ture，表示你在后面put一个跟原来key一样的值时会覆盖掉原来的值，而如果是false时，则保留原来的值，也就是不覆盖，相当于put相同key的值没效果吧。

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    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);
    }
}

这儿有个instanceof函数表示判断前者是否是后者的一个实例。例如，Result = object instanceof class; 判断object是不是class的一个实例，如果是则返回ture。

TreeNode，树节点，他是继承自Node节点的，也就是说TreeNode形成的实例既有Node的key，value等属性，重要的是他有next属性指向下一个节点，而有有TreeNode的parent，left，rigth等属性，这儿在TreeNode里面增加了pre属性来指向前一个节点，只能够在红黑树中使用。在查找HashMap中是否包含某个value的时候将所有都当作链表节点来使用，将父类与本身的属性发挥的非常不错，比如在ContainsValue函数中就没有区分是否是红黑树去查找而是直接使用其父类的next函数查找下一个依次遍历。

3、putMapEntries这个函数就是将，一个Map的所有值加入当前Map，当然需要指定evict参数。

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    int s = m.size();
    if (s > 0) {
        if (table == null) { // pre-size
            float ft = ((float)s / loadFactor) + 1.0F;
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                     (int)ft : MAXIMUM_CAPACITY);
            if (t > threshold)
                threshold = tableSizeFor(t);
        }
        else if (s > threshold)
            resize();
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            putVal(hash(key), key, value, false, evict);
        }
    }
}

类似的有putAll函数，他就是引用了一下putMapEntries函数，区别就是默认了evict为true而已。

public void putAll(Map<? extends K, ? extends V> m) {
    putMapEntries(m, true);
}

resize函数

这部分非常重要，时HashMap重要思维的体现之处之一。首先扩容会在两种情况发生，第一种，在链表转化为红黑树的时候阐述过链表长度大于8且哈希桶数组的长度size<64时会出发扩容；第二种，size>threshold的时候会触发扩容（threshold=length*loadFactor）。

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; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        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) {
        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;
                        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;
}

从代码中可以看出resize函数是返回一个新的哈希桶数组，那么为什么要返回一个新的哈希桶数组呢？这点要从数组讲起，众所周知数组的长度是固定的，不能变长，那么我们怎么在HashMap中产生一个是原来长度两倍的数组呢？这儿就只能够创建一个新的数组来代替老的数组，需要将原来数组里面的变量一一填充到新的数组里面来。在Java1.7以及之前是一次将原来HashMap中的所有节点通过hash算法依次定位到新的Map中来。在Java1.8中对于老的数组同意位置的链表或红黑树中的节点填充到新的Map中做了很大的优化，使得扩容的速度快了许多。当然虽然优化了很多，但是这也是非常消耗时间成本的，因此我们在创建HashMap的时候就需要提前估计其能达到的最大容量，尽量一次性分配足够的空间，减少扩容情况。

在Java1.8中对于HashMap扩容时数据转移做了很大的优化，这儿需要讲到hash获取数组下标的方法(n-1)&hash(key)。对于hash(key)方法我不做过多阐述，想要学习的看看源码再自己测试一下就明白了。而对于按位与&这儿需要说明一下，比如我们的数组长度n=4，那么呢n-1就是二进制的0011，举个例子当hash(key)为2和6的二进制分别时0010和0110，（前面的一些0就不做过多书写了），他们对于n-1的&后得到的0011是相同的，也就是产生冲突，就会形成链表或者红黑树。而扩容之后，n’为8，n’-1二进制为0111，hash(key)进行&操作后就是0010和0110，刚好是原来下标位置和原位置下标加上原来数组长度后作为下标的位置。这儿就可以直接用原来数组长度n的二进制0100与两个hash(key)进行&操作，来判断是否需要将下标位置加上n了，如果是1则加。这样就不需要对于每个节点依次去进行一次重新定位操作。

remove函数

当然，跟之前的分析一样，我们都需要关注返回值，这儿返回的是value或者null，那么value是哪个value呢？就是原来我们移除的那个节点的value，当无这个节点时，那么返回null。其实这儿跟put函数一样，都是对于其基础函数的封装，这里remove函数是对于removeNode
函数的封装。

public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        else if ((e = p.next) != null) {
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)
                tab[index] = node.next;
            else
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

从上面removeNode函数可以看出其返回的是一个Node类型，即返回移除的节点，除了没有对应节点时返回null，这儿有两个比较特殊的参数matchValue和movable，matchValue表示是否匹配value的值，而moveable表示是否可以移除，对于这点我有点想不太明白。在remove函数中这部分都是和value一起以默认值传出。在removeNode函数里面又有判断当为红黑树时的removeTreeNode函数，对于这个函数我不作过多分析，需要的可以自己去看一下源码。

附

对于其他函数等操作等，我就不具体分析，比如contains一系列，clear函数以及一系列Set等，以及其迭代器iterator等。这些如果需要学习可以仔细看一下其源码分析。最后推荐下美团点评技术团队的《Java 8系列之重新认识HashMap》。