全网最硬核的源码分析之——HashMap源码分析上
HashMap源码分析
创造不易，希望大家可关注一下，点个赞再走，感谢您的阅读。
基于JDK1.8
一 数据结构
HashMap 底层的数据结构主要是：数组 + 链表 + 红黑树。其中当链表的长度大于等于 8 时（且数组的长度达到一定的长度）后，链表会转化成红黑 树，当红黑树的大小小于等于 6 时，红黑树会转化成链表
1.1 重要变量
//初始容量为 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//负载因子默认值
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//桶上的链表长度大于等于8时，链表转化成红黑树
static final int TREEIFY_THRESHOLD = 8;
//桶上的红黑树大小小于等于6时，红黑树转化成链表
static final int UNTREEIFY_THRESHOLD = 6;
//当数组容量大于 64 时，链表才会转化成红黑树
static final int MIN_TREEIFY_CAPACITY = 64;
//记录迭代过程中 HashMap 结构是否发生变化，如果有变化，迭代时会 fail-fast
transient int modCount;
//HashMap 的实际大小，可能不准(因为当你拿到这个值的时候，可能又发生了变化)
transient int size;
//存放数据的数组
transient Node<K,V>[] table;
// 扩容的门槛，有两种情况
// 如果初始化时，给定数组大小的话，通过 tableSizeFor 方法计算，数组大小永远接近于 2 的幂次方，比如你给定初始化大小 19，实际上初始化大小
为 32，为 2 的 5 次方。
// 如果是通过 resize 方法进行扩容，大小 = 数组容量 * 0.75
int threshold;
//链表的节点
static class Node<K,V> implements Map.Entry<K,V> {
//红黑树的节点
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V>
注意事项
（1）容量
容量为数组的长度，亦即桶的个数，默认为16，最大为2的30次方，当容量达到64时才可以树化。
（2）装载因子
装载因子用来计算容量达到多少时才进行扩容，默认装载因子为0.75。
（3）树化
树化，当容量达到64且链表的长度达到8时进行树化，当链表的长度小于6时反树化。
二.源码分析
2.1 HashMap类注释解析
-
允许 null 值，不同于 HashTable ，是线程不安全的； -
load factor（影响因子） 默认值是 0.75， 是均衡了时间和空间损耗算出来的值，较高的值会减少空间开销（扩 容减少，数组大小增长速度变慢），但增加了查找成本（hash 冲突增加，链表长度变长），不扩容的条件：数 组容量 > 需要的数组大小 /load factor； -
如果大量数据需要储存到 HashMap 中，建议 HashMap 的容量一开始就设置成足够的大小，这样可以防止在 其过程中不断的扩容，影响性能； -
HashMap 是非线程安全的，我们可以自己在外部加锁，或者通过 Collections#synchronizedMap 来实现线程安 全，Collections#synchronizedMap 的实现是在每个方法上加上了 synchronized 锁； -
在迭代过程中，如果 HashMap 的结构被修改，会快速失败。
2.2 内部类
2.2.1 Node
Node是一个单链表节点，其中，hash用来存储key计算得来的hash值。
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
2.2.2 TreeNode内部类
继承自LinkedHashMap中的Entry类
TreeNode是一个树型节点，其中，prev是链表中的节点，用于在删除元素的时候可以快速找到它的前置节点。
// 位于HashMap中
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; // 用于在删除元素的时候可以快速找到它的前置节点。
boolean red;
}
// 位于LinkedHashMap中，双向链表节点
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
2.3 HashMap()构造方法
2.3.1 空参构造方法，全部使用默认值。
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
2.3.2 HashMap(int initialCapacity)构造方法
调用HashMap(int initialCapacity, float loadFactor)构造方法，传入默认装载因子。
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
2.3.3 HashMap(int initialCapacity, float loadFactor)构造方法
判断传入的初始容量和装载因子是否合法，并计算扩容门槛，扩容门槛为传入的初始容量往上取最近的2的n次方。
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);
}
static final int tableSizeFor(int cap) {
// 扩容门槛为传入的初始容量往上取最近的2的n次方
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;
}
推荐阅读
如果感觉对您有帮助，希望大家可关注一下，点个赞再走，感谢您的阅读。后续会有更多原创文章