深入理解 Java 之 HashMap 源码解析

// table 数组即 Entry 数组的初始容量
static final int DEFAULT_INITIAL_CAPACITY = 16;
// 最大的容量，左移即 2 的 30 次方
static final int MAXIMUM_CAPACITY = 1 << 30;
// 负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 储存 key-value 键值对的数组，一个键值对对象映射一个Entry对象
transient Entry[] table;
// 键值对的数目
transient int size;
// 调整 HashMap 大小门槛，该变量包含了HashMap 能容纳的 key-value 对的极限，它的值等于 HashMap 的容量乘以负载因子
int threshold;
// 加载因子
final float loadFactor;
// HashMap 结构修改次数,防止在遍历时，有其他的线程在进行修改
transient volatile int modCount;

public HashMap(int initialCapacity, float loadFactor) {
	// 初始大小为 0 即抛出异常
if (initialCapacity < 0)
		throw new IllegalArgumentException("Illegal initial capacity: "
				+ initialCapacity);
	// 初始大小超过指定的最大值，则容量为指定的最大值
	if (initialCapacity > MAXIMUM_CAPACITY)
		initialCapacity = MAXIMUM_CAPACITY;
	// 负载因子也不能为 0
	if (loadFactor <= 0 || Float.isNaN(loadFactor))
		throw new IllegalArgumentException("Illegal load factor: "
				+ loadFactor);
	// Find a power of 2 >= initialCapacity
	int capacity = 1;
	// 使得capacity 的大小为2的幂
	while (capacity < initialCapacity)
		capacity <<= 1;
	this.loadFactor = loadFactor;
	// size 超过这个数值就会扩容,即其为阈值
	threshold = (int) (capacity * loadFactor);
	table = new Entry[capacity];
	init();
}

public V get(Object key) {
  	// key 为 null 的情况
    if (key == null)
        return getForNullKey();
  	// key ！= null 的情况
    int hash = hash(key.hashCode());
    // 遍历 table 
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
          	// 相等则返回 e.value
            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
                return e.value;
    }
    return null;
}

private V getForNullKey() {
 // 遍历 table[0] 的链表
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
         if (e.key == null)
           return e.value;
   }
  return null;
}

public V put(K key, V value) {
	// 即上图的 Entry 数组为空，则初始化
    if (table == EMPTY_TABLE) {
            inflateTable(threshold);
    }
	// put 进去的 key 为空的话,去 putForNullKey(value)这个方法存放
    if (key == null)
        return putForNullKey(value);
	// key 不为空，计算 hashkey
    int hash = hash(key);
	// 根据 hashkey 找到在 Entry 数组中的位置
    int i = indexFor(hash, table.length);
	// 每个位置都是一个链表，循环直到找到有位置，当前 Entry 数组位置 e 存在
	// 每个节点都有一个 next 索引 指向 链的下一个节点
  	// 这种情况是 Entry 数组上已经插入了元素。
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
          Object k;
          // 找到指定 key 与需要放入的 key 相等（hash 值相同  
     	  // 通过 equals 比较放回 true）
       	  if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
				// 返回原来这个位置上的值
                return oldValue;
            }
        }
    // 表示更改了一次底层数据结构
    modCount++;
	// 此时进行元素的插入，添加至索引 i 处
    addEntry(hash, key, value, i);
    return null;
}
// addEntry 方法中会检查当前 table 是否需要 resize
void addEntry(int hash, K key, V value, int bucketIndex) {
		// Entry 桶位不为空，就是已经插入了值，并且 size 大于 一定的量了
        if ((size >= threshold) && (null != table[bucketIndex])) {
		// 当前 map 中的 size 如果大于 threshole 的阈值，则 resize 将 table 的 length 扩大2倍。
            resize(2 * table.length); 
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }
		//增加数组的长度
        createEntry(hash, key, value, bucketIndex);
}

void resize(int newCapacity) {
	// 将旧数组元素输出
    Entry[] oldTable = table;
	// 将旧数组容量输出保存
   	int oldCapacity = oldTable.length;
	// 如果说旧容量已经达到最大的容量了
   	if (oldCapacity == MAXIMUM_CAPACITY) {
		// 这里表示整形能够表示的最大数值，在前面 ArrayList 中应该也有
        threshold = Integer.MAX_VALUE;
        return;
     }
    // 构造一个新的 table 数组
    Entry[] newTable = new Entry[newCapacity];
	// 转移 数据
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    table = newTable;
	// 计算新表的 负载极限
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
	}
	// 将当前 table 的 Entry 转移到新的 table 中
void transfer(Entry[] newTable, boolean rehash) {
	// 新 table 的容量
    int newCapacity = newTable.length;
	// 将原 table 中数据迭代输出
    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;
            }
      }
}

static int hash(int h) {  
    h ^= (h >>> 20) ^ (h >>> 12);  
    return h ^ (h >>> 7) ^ (h >>> 4);  
}

static int indexFor(int h, int length) {  
    return h & (length-1);  
}

HashIterator() {
    expectedModCount = modCount;
    if (size > 0) { // advance to first entry
    Entry[] t = table;
    while (index < t.length && (next = t[index++]) == null)
        //...
   }
}

final Entry<K,V> nextEntry() {     
    if (modCount != expectedModCount)     
        throw new ConcurrentModificationException();

// HashMap结构修改次数,防止在遍历时，有其他的线程在进行修改  
transient volatile int modCount;

// 最开始的容量，必须是 2 的次方，这里即 2 的 4 次方
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// 负载
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// list to tree 的临界值
static final int TREEIFY_THRESHOLD = 8;
// 删除冲突节点后，hash相同的节点数目小于这个数，红黑树就恢复成链表
static final int UNTREEIFY_THRESHOLD = 6;
// 扩容的临界值
static final int MIN_TREEIFY_CAPACITY = 64;
// 存储元素的数组
transient Node<k,v>[] table;

// 继承自 Map.Entry<K,V>
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; }
		// 返回 Hash 值
        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }
		// 重写 equals() 
        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;
        }
}

public HashMap(int initialCapacity, float loadFactor) {
       // 同上 jdk 1.7
        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);
    }

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

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;    // needed to unlink next upon deletion
        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;
       }

public V put(K key, V value) {
    // 调用 putVal() 函数 
   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;
		// tab 没有分配初始的空间或者为空，就 resize 一次
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
		// 指定 hash 值节点为空则直接在tab表中插入，注意这里 (n - 1) & hash 才是真正的 hash 值
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
		// 不为空
        else {
            Node<K,V> e; K k;
			// 计算当前节点的 key.hash 与要插入的 key.hash
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
				// 相同则覆盖
                e = p; 
			// 若不同的话，并且当前节点已经在 TreeNode 上了
            else if (p instanceof TreeNode)
				// 创建新的树节点
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
			// key.hash 不同并且也不再 TreeNode 上，在链表上找到 p.next==null
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
						// 表示在表尾插入
                        p.next = newNode(hash, key, value, null);
						// 新增节点后如果节点个数到达阈值，则进入 treeifyBin() 进行再次判断
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
							// 这里有可能还会跟64比较，判断是否需要对 table 进行扩容
                            treeifyBin(tab, hash);
                        break;
                    }
					// 如果找到了同hash、key的节点，那么直接退出循环
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
					// 更新 p 指向下一节点
                    p = e;
                }
            }
			// 退出循环后的操作，hash 和 key 都相同，则覆盖更新
            if (e != null) { 
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // table 已经初始化，长度大于 0，根据 hash 寻找 table 中的项也不为空
    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;
}

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    // 对 newCap 的取值
    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);
        }
    	//...
                  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;
    }

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
	// table 为空或者 table 的桶位还没达到 64，进行 table 扩容，而不是红黑调整
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
    // >=64,进行红黑树转化
       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);
    }
}