java集合之HashMap源码分析
李羽秋
2023年03月23日 · 阅读 1,670
java集合之HashMap源码分析
1. 存储结构
从结构实现来看，自jdk1.8以后，HashMap是数组+链表+红黑树实现的，如图
自jdk1.8后，当图中数组的某个链表长度超过8时，链表将会自动转为红黑树。之所以引入红黑树，当多个hash碰撞的时候，链表查询的时间复杂度为O(n),因此引入了红黑树来提高查找、插入和删除的效率，时间复杂度为O(logn)。
2. 源码分析
2.1 构造方法
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);
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
构造方法一共重载四个，主要初始化了三个参数:
- initialCapital 初始容量：hashMap底层由数组实现+链表（或红黑树）实现，但是还是从数组开始，所以当储存的数据越来越多的时候，就必须进行扩容操作，如果在知道需要储存数据大小的情况下，指定合适的初始容量，可以避免不必要的扩容操作，提升效率。
- threshold阈值：hashMap所能容纳的最大价值对数量，如果超过则需要扩容，计算方式：threshold=initialCapacity*loadFactor（构造方法中直接通过tableSizeFor(initialCapacity)方法进行了赋值，主要原因是在构造方法中，数组table并没有初始化，put方法中进行初始化，同时put方法中也会对threshold进行重新赋值，这个会在后面的源码中进行分析）。
- loadFactor 加载因子（默认0.75）：当负载因子较大时，去给table数组扩容的可能性就会少，所以相对占用内存较少（空间上较少），但是每条entry链上的元素会相对较多，查询的时间也会增长（时间上较多）。反之就是，负载因子较少的时候，给table数组扩容的可能性就高，那么内存空间占用就多，但是entry链上的元素就会相对较少，查出的时间也会减少。所以才有了负载因子是时间和空间上的一种折中的说法。所以设置负载因子的时候要考虑自己追求的是时间还是空间上的少。（一般情况下不需要设置，系统给的默认值已经比较适合了）。
2.2 Put方法
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)
//如果table尚未初始化，则此处进行初始化数组，并赋值初始容量，重新计算阈值
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
//通过hash找到下标，如果hash值指定的位置数据为空，则直接将数据存放进去
tab[i] = newNode(hash, key, value, null);
else {
//如果通过hash找到的位置有数据，发生碰撞
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//如果需要插入的key和当前hash值指定下标的key一样，先将e数组中已有的数据
e = p;
else if (p instanceof TreeNode)
//如果此时桶中数据类型为 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;
}
//如果链表中有新插入的节点位置数据不为空，则此时e 赋值为节点的值，跳出循环
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//经过上面的循环后，如果e不为空，则说明上面插入的值已经存在于当前的hashMap中，那么更新指定位置的键值对
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//如果此时hashMap size大于阈值，则进行扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
从代码看，put方法分为三种情况：
- table尚未初始化，对数据进行初始化
- table已经初始化，且通过hash算法找到下标所在的位置数据为空,直接将数据存放到指定位置
- table已经初始化，且通过hash算法找到下标所在的位置数据不为空，发生hash冲突（碰撞），发生碰撞后，会执行以下操作：
- 判断插入的key如果等于当前位置的key的话，将 e 指向该键值对
- 如果此时桶中数据类型为 treeNode，使用红黑树进行插入
- 如果是链表，则进行循环判断， 如果链表中包含该节点，跳出循环，如果链表中不包含该节点，则把该节点插入到链表末尾，同时，如果链表长度超过树化阈值（TREEIFY_THRESHOLD）且table容量超过最小树化容量（MIN_TREEIFY_CAPACITY），则进行链表转红黑树（由于table容量越小，越容易发生hash冲突，因此在table容量<MIN_TREEIFY_CAPACITY 的时候，如果链表长度>TREEIFY_THRESHOLD,会优先选择扩容，否则会进行链表转红黑树操作）
2.3 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) {
//1、根据hash算法找到对应位置的第一个数据，如果是指定的key，则直接返回
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;
}
get方法相对于put来说，逻辑实在是简单太多了
- 根据hash值查找到指定位置的数据
- 校验指定位置第一个节点的数据是key是否为传入的key，如果是直接返回第一个节点，否则继续查找第二个节点
- 如果数据是TreeNode（红黑树结构），直接通过红黑树查找节点数据并返回
- 如果是链表结构，循环查找所有节点，返回数据
- 如果没有找到符合要求的节点，返回null
在这个方法里面，需要注意的有两个地方：hash（key）和hash的取模运算 (n - 1) & hash
2.4 取模运算(n-1)&hash
first = tab[(n - 1) & hash])
hash算法中，为了使元素分布的更加均匀，很多都会使用取模运算，在hashMap中并没有使用hash%n这样进行取模运算，而是使用(n - 1) & hash进行代替，原因是在计算机中，&的效率要远高于%；需要注意的是，只有容量为2的n次幂的时候，(n - 1) & hash 才能等效hash%n，这也是hashMap 初始化初始容量时，无论传入任何值，都会通过tableSizeFor(int cap) 方法转化成2的n次幂的原因。
2.5 remove方法
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;
//根据key和key的hash值，查找到对应的元素
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);
}
}
//如果查找的了元素node，移除即可
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
//如果是TreeNode，通过树进行移除
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
//如果是第一个节点，移除第一个节点，将index下标的位置指向第二个节点
else if (node == p)
tab[index] = node.next;
else
//如果不是链表的第一个节点，则移除该节点
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
3.总结
HashMap 底层数据结构在JDK1.7之前是由数组+链表组成的，1.8之后又加入了红黑树；链表长度小于8的时候，发生Hash冲突后会增加链表的长度，当链表长度大于8的时候，会先判读数组的容量，如果容量小于64会先扩容（原因是数组容量越小，越容易发生碰撞，因此当容量过小的时候，首先要考虑的是扩容），如果容量大于64，则会将链表转化成红黑树以提升效率
hashMap 的容量是2的n次幂，无论在初始化的时候传入的初始容量是多少，最终都会转化成2的n次幂，这样做的原因是为了在取模运算的时候可以使用&运算符，而不是%取余，可以极大的提上效率，同时也降低hash冲突
HashMap是非线程安全的，在多线程的操作下会存在异常情况（如形成闭环（1.7），1.8已修复闭环问题，但仍不安全），可以使用HashTable或者ConcurrentHashMap进行代替
分类:
Java
标签:
无