1. 云图网首页
  2. 技术专区
  3. 编程笔记

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

• 编程笔记

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

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

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

HashMap的特性

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

  1. 数据结构

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

    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虾米网

原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/19398.html

赞 (0)
0
上一篇 2021年7月19日
下一篇 2021年7月19日

相关推荐

发表回复

登录后才能评论