HashMap原理和源码分析详解编程语言

HashMap、HashTable、LinkedHashMap、ConcurrentHashMap这四个数据结构都是比较重要的。

并且LinkedHashMap、ConcurrentHashMap都是基于HashMap扩展的，特别是ConcurrentHashMap内部机制复杂而且精巧，花了好几天才熟悉源码，虽然有部分细节依然没搞清楚。

接下来几篇文章记录下自己的学习成果和加深理解。

HashMap的特性

在JDK1.8之后，Hashmap有了一些变化，以下先讲诉HashMap的数据结构和特性

1. 数据结构

   HashMap采用了数组 + 链表 + 红黑树的数据结构：

   

   可以看到，左侧是一个数组，每个数组元素是一个hash桶，存储着一个链表或者一个红黑树，每个圆点就是HashMap的基本单位 Node<K,V>，内部有一个Key和Value。

   为什么会数组同一个位置会出现挂着多个结点呢？原因是哈希碰撞，不同的key产生不同的hash值，但是可能指向同一个数组的位置，例如上图，hash为7跟hash为1都是在数组的第二个位置，这就产生了哈希碰撞。

   什么时候采用链表？什么时候采用红黑树呢？在hashMap中，当链表长度超过阈值（8），就会转成红黑树，这样有利于查询插入删除效率。但是红黑树被删除结点，长度小于阈值（6）又会转换成链表。

2. 扩容
   HashMap 的默认初始容量是16，也可以初始化指定容量，但是即使随意指定容量，也会被扩展到2的指数大小的容量，比如说初始化10个实体，hashmap的容量是16。

   每次达到一定的条件会进行扩容，容量变成原来的两倍。这样就能保证容量永远是2的指数倍大小，这样做的原因是有利于HashMap内部的位运算，提升计算效率，例如可以用&代替取余等。

   扩容条件有两个，满足任意一个都会扩容：

   1. 当结点数量达到 临界数量，临界数量 = 容量 * 负载因子（默认是0.75），会进行扩容
   2. 当hash桶内部链表转化成红黑树时，若容量小于阈值（默认是64），会进行扩容

HashMap 源码分析

下面进行HashMap的部分比较重要的源码分析，如果可以的话，可以边翻着源码边对着下面解释作为参考，能够帮助理解上面的特性，还有后续的ConcurrentHashMap。

1. 比较重要的参数、数据结构

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;   
//默认初始化容量  16 
	 
static final int MAXIMUM_CAPACITY = 1 << 30;  
//最大初始化容量 
 
static final int TREEIFY_THRESHOLD = 8;  
// 当链表长度超过>8时候，会从链表转为树存储 
	 
static final int UNTREEIFY_THRESHOLD = 6;  
// 在哈希表扩容时，当链表长度超过<6时候，会从树转链表存储 
 
static final int MIN_TREEIFY_CAPACITY = 64;  
// 当链表转化为树时，要求的最小容量，如果容量 < MIN_TREEIFY_CAPACITY，发生一次resize()扩容 
	 

下面是重要的数据结构

Node<K,V>[] table; // 数组存储 
 
Set<Map.Entry<K,V>> entrySet; // 实体集合，方便遍历 
 
int size;//  结点的总数 
 
int modCount; // HashMap结构修改的次数，例如put、remove、clear等 
 
int threshold; // 临界值 = capacity * load factor 
 
final float loadFactor; // 默认是0.75，到达需要扩容的比例 
 
// 结点 
static class Node<K,V> implements Map.Entry<K,V> {
    
        final int hash; // key的hash值 
        final K key;  
        V value; 
        Node<K,V> next; // 树或者链表的下一节点 
 	... 
 } 

HashMap常用到的方法

// hash计算的规则：取高的16位和低的16位亦或，减少碰撞 
static final int hash(Object key) {
    
    int h; 
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); 
} 

上面是HashMap hash值的计算规则，那怎么算出对应的hash桶的位置呢？

n = table.length;
index = （n-1） & hash;
等价于 hash % n-1，因为n是2的指数，位运算效率更高
index就是hash桶的位置，就是table数组的下标

// 获取table要扩容的容量：比给定的cap大且最接近的2次方整数 
 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; 
    } 
//上面的作用就是把二进制 第一个1开始的后续数字变成1，然后再 + 1 
// 如 000100011110 -> 000111111111 + 1 -> 00100000000 

这部分可以参考，讲得特别好：IT虾米网

2. 主要方法

构造函数：

// 指定了初始容量和负载因子 
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); 
} 

上面有一点开始蛮疑惑的，this.threshold = tableSizeFor(initialCapacity);
按个人的想法应该是：this.threshold = initialCapacity * loadFactor;

后面理解了，假设 initialCapacity为16，threshold设定2，那后续再装入16个结点的时候就会发生一次扩容。
既然我们呢知道了初始容量，干脆就设定 this.threshold = tableSizeFor(initialCapacity) 不必产生一次不必要的扩容。

第二个构造函数:

// HashMap 
 
public HashMap(Map<? extends K, ? extends V> m) {
    
    this.loadFactor = DEFAULT_LOAD_FACTOR; 
    putMapEntries(m, false); 
} 
 
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    
    int s = m.size(); 
    if (s > 0) {
    
        if (table == null) {
    // table为空，先初始化设置threshold 
         	  // 除以 扩容的比例，往上多取一个 
            float ft = ((float)s / loadFactor) + 1.0F;         
            int t = ((ft < (float)MAXIMUM_CAPACITY) ? 
                    (int)ft : MAXIMUM_CAPACITY); 
            if (t > threshold) 
                threshold = tableSizeFor(t);// 取2的次数方 
        } 
        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); 
    } 
} 

上面的构造函数引出了 putVal 操作，来看一下

putVal
根据key插入或修改值，其实put操作也是调用了putVal方法

public V put(K key, V value) {
    
    return putVal(hash(key), key, value, false, true); 
} 
 
// onlyIfAbsent表示存在对应的key时，是否修改value值 
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 
    if ((tab = table) == null || (n = tab.length) == 0) 
       n = (tab = resize()).length; 
     
    // (n-1)& hash == hash % (n-1) 计算出hash桶的位置 
    if ((p = tab[i = (n - 1) & hash]) == null) 
    	 // hash桶为空 
        tab[i] = newNode(hash, key, value, null); 
    else {
    
    	 // 出现hash碰撞 
        Node<K,V> e; K k; 
        // p是首个结点 
        if (p.hash == hash && 
           ((k = p.key) == key || (key != null && key.equals(k)))) 
            e = p; 
        else if (p instanceof TreeNode) // 红黑树 
        // 添加树节点，若不存在则插入，若存在返回对应的节点e 
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); 
        else {
    // 链表，添加链表结点 
             for (int binCount = 0; ; ++binCount) {
    
                 if ((e = p.next) == null) {
     
                 //key不在链表，到达最后链表尾部，插入新节点 
                     p.next = newNode(hash, key, value, null); 
                     if (binCount >= TREEIFY_THRESHOLD - 1) // 达到转化成树的临界值 
                        treeifyBin(tab, hash);//转化成红黑树 
                     break; 
                 } 
                 // 该key存在链表中 
                 if (e.hash == hash && 
                    ((k = e.key) == key || (key != null && key.equals(k)))) 
                    break; 
                p = e; 
            } 
        } 
        if (e != null) {
   // e不为空，对应的key的节点 
            V oldValue = e.value; 
            if (!onlyIfAbsent || oldValue == null) 
                e.value = value; 
            // 修改了节点，都会调用afterNodeAccess 
            // 在hashmap是空实现，在LinkedHashMap是一个重要的方法 
            afterNodeAccess(e); 
            return oldValue; 
        } 
    } 
    ++modCount;//到这里说明插入了新节点，操作数+1 
    if (++size > threshold) 
        resize(); 
    // 插入节点后会调用afterNodeInsertion() 
    afterNodeInsertion(evict); 
    return null; 
} 

其实上面代码逻辑也不难，插入节点分成两种情况：

1. 空hash桶或者不存在对应的key值：直接当成首节点，或者根据是链表或红黑树，插入节点
2. 存在对应的key值：再根据onlyIfAbsent决定是否修改value

getVal
根据key获取value

 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 == hash % (n-1) 计算出hash桶的位置 
        if (first.hash == hash && // 检查首节点，hash相同且key相同 
            ((k = first.key) == key || (key != null && key.equals(k)))) 
            return first; 
        if ((e = first.next) != null) {
    
            if (first instanceof TreeNode)// 红黑树 getTreeNode 
                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; 
 } 

getNode的逻辑也是比较简单，看上面的注释应该就可以明白。

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; 
        // 获取要删除的节点node 
        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;//操作数+1 
           --size;//size-1 
           // 跟上面的方法afterNodeInsertion一样，hashmap是空实现 
           afterNodeRemoval(node); 
           return node; 
        } 
   } 
   return null; 
} 

3. 扩容源码分析

这部分其实并不难，但是后面的ConcurrentHashMap的扩容迁移部分，也是基于以下方法扩展的。

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; // 设置threshold为原来两倍 
    } 
    else if (oldThr > 0)  // threshold不为0，初始化 
        newCap = oldThr;// 设置容量为threshold临界值 
    else {
    //threshold、容量为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) {
    
    	 // 迁移工作 
        for (int j = 0; j < oldCap; ++j) {
    
            Node<K,V> e; 
            if ((e = oldTab[j]) != null) {
    
               oldTab[j] = null; 
               if (e.next == null)// 该桶只有一个值 
               // e.hash & (newCap - 1)算出新的位置 
                   newTab[e.hash & (newCap - 1)] = e; 
               else if (e instanceof TreeNode) 
               // 调用红黑树，跟下面链表一样切分两份 
                   ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); 
               else {
    // preserve order 
               // 根据e.hash & oldCap是否等于0，切分两个链表， 
               // 分别放在i位置和i+ oldCap位置，不理解可以看后续的解释 
                   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; 
} 
 

小结

扩容工作：

1. 扩大容量：扩大为原来2倍
2. 迁移节点

上面有一个根据e.hash & oldCap是否等于0，切分两个链表，分别放在i位置和i+ oldCap位置。
e.hash & oldCap != 0 说明e.hash < oldCap，那么e保持原来位置不动
e.hash & oldCap == 0 说明e.hash > oldCap，那么e要搬移位置，迁移到 i + oldCap

举个例子：
例如原容量oldCap为4，第二个hash桶有1、5、9，扩容之后为8，那么
1 & 4 == 1; // 不需要迁移位置，保持在原位置1
5 & 4 == 0; // 迁移到位置5
9 & 4 == 0; // 迁移到位置5

这部分迁移在concurrentHashMap也是类似的

参考：
IT虾米网