1、一些常量的定义
这里针对MIN_TREEIFY_CAPACITY 这个值进行解释一下。
java8里面，HashMap 的数据结构是数组 + （链表或者红黑树），每个数组节点下可能会存在链表和红黑树之间的转换，当同一个索引下面的节点超过8个时，首先会看当前数组长度，如果大于64，则会发生链表向红黑树的 转换，否则不会转换，而是扩容。
// 默认的初始化长度 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 默认的最大容量 2^30
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认的扩容因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 链表转为树的阈值
static final int TREEIFY_THRESHOLD = 8;
// 树转为链表的阈值
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;
// map已存节点的数量
transient int size;
// 修改次数
transient int modCount;
// 扩容阈值 当size达到这个值的时候，hashmap开始扩容
int threshold;
// 加载因子 threshold = 容量 * loadFactor
final float loadFactor;2、构造器
HashMap提供了三个构造器。
// 无参构造器，使用默认加载因子 0.75
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
// 只传入初始化容量，也会使用默认加载因子 0.75
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
// 同时传入初始化容量和加载因子 （初始化容量要大于0，且不能超过最大容量）
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;
// 初始化的容量先赋值给了threshold 暂存。
this.threshold = tableSizeFor(initialCapacity);
}注意看，使用带参构造器 会调用 tableSizeFor(initialCapacity); 这个方法是干嘛的呢？其实就是为了计算初始化容量。HashMap规定，其容量必须是2的N次方
- 不传初始化容量，就取默认值16
- 传了初始化容量，则初始化容量设置为大于等于该数值的 一个最小的2的N次方
- 比如传入了7，不是2的N次方，那么取比他大的最小的2的N次方，就是8
- 比如传入了8，刚好是2的N次方，那就取8
- 比如传入了9，不是2的N次方，那么取比他大的最小的2的N次方，就是16
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;
}或等于操作 a |= b ，其实就是 a = a | b。
无符号右移操作：a >>> b 就表示将a向右移动b位，左边空出来的用0补充，右边的被丢弃
那么 n |= n >>> 1 操作得到的结果就是，最高位和次高位的结果为1；--- > n 的前两位为1
n |= n >>> 2 操作之后 --- > n的前四位为1
.... 一通操作之后，得到的值是一个低位全是1的值。然后返回的时候+1，得到的值就是一个比n大的2的N次方。而开头的 int n = cap - 1 是为了解决本身就是2的N次方的场景。
3、插入操作
3.1、插入操作的具体流程
- 插入前首先判断数组是否为空，如果为空就进行初始化
- 计算key的hash值，然后和数组长度-1 进行 & 运算，获取在数组中的索引位置
- 当前位置不存在元素，就直接创建新节点放在当前索引位置
- 当前位置元素存在，就走后续的逻辑
- 判断当前坐标下头节点的hash值是否和 key的hash相等，如果相等就进行替换（还要判断一个控参 onlyIfAbsent，这个为false的时候才会替换，最常用的put操作这个值就是false ）
- 如果不相等，判断当前是链表还是红黑树
- 如果是链表，遍历链表节点，并统计节点个数：
- 如果找到了相同的key，就进行覆盖操作，
- 如果没有找到相同key，就将节点添加到链表最后面，并判断是否超过8个节点，如果大于等于8，就要链表转红黑树操作。
- 如果是红黑树：找到红黑树根节点，从根节点开始遍历：
- 找到相同的key，就进行替换
- 找不到相同的key，就放到相应的位置，然后进行红黑树插入平衡调整
- 插入完成之后，判断当前节点数目是否超过扩容阈值，如果超过，就进行扩容。
public V put(K key, V value) {
/**
* 首先计算出了key的hash 值
*/
return putVal(hash(key), key, value, false, true);
}
final V putVal ( int hash, K key, V value,boolean onlyIfAbsent, boolean evict){
HashMap.Node<K, V>[] tab;
HashMap.Node<K, V> p;
int n, i;
/**
* 判断数组是否为空，为空则进行数组初始化
* ---> tab = resize() 然后获取数组的长度
*/
if ((tab = table) == null || (n = tab.length) == 0) {
n = (tab = resize()).length;
}
/**
* 计算当前节点要插入数组的索引的位置 ---> (n - 1) & hash
* 如果索引处不存在节点，就新创建节点放到索引的位置
*/
if ((p = tab[i = (n - 1) & hash]) == null) {
tab[i] = newNode(hash, key, value, null);
}
/**
* 如果索引处存在节点，走这个逻辑
*/
else {
HashMap.Node<K, V> e;
K k;
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) {
/**
* 进入这个分支，说明要插入的节点和头节点的key相同
*/
e = p;
} else if (p instanceof HashMap.TreeNode) {
/**
* 说明头节点是红黑树了，要把这个新节点插入到红黑树中，涉及到新节点的插入，红黑树的平衡调整等
*/
e = ((HashMap.TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
} else {
/**
* 说明头节点是链表节点，遍历链表
*/
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
/**
* 遍历到最后了，创建新节点插入到尾端
* 还要判断节点是否超过8个，超过了要转化为红黑树
*/
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
{
treeifyBin(tab, hash);
}
break;
}
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
/**
* 找到了相同key的value
*/
break;
}
p = e;
}
}
/**
* e不为空，说明有key相同的情况，替换成新的value，然后直接返回旧的节点
* 因为节点数目不存在变化，因此不需要进行扩容判断
*/
if (e != null) { // existing mapping for key
V oldValue = e.value;
// onlyIfAbsent的判断
if (!onlyIfAbsent || oldValue == null) {
e.value = value;
}
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
/**
* 如果当前节点超过了扩容阈值，就进行扩容，然后返回null
*/
if (++size > threshold) {
resize();
}
afterNodeInsertion(evict);
return null;
}3.2、 key的hash值是怎么计算的？为什么要这么计算？
- 如果key为空，就直接返回0
- 不为空将 key的hashcode 和 hashcode左移16位进行& 运算
- ---- 左移16位主要就是为了将hash的高位也参与到hash计算中，减少hash冲突。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}3.3、resize扩容流程介绍
- 首先会对老数组进行一系列的校验，大致分为：
- 老数组为空，就设置一下数组长度和扩容阈值，新建数组，然后返回
- 老数组不为空，校验老数组长度，如果长度超过上限，扩容阈值修改为int最大值，返回
- 否则：容量、扩容阈值变为原来的2倍
- 接着开始遍历老数组
- 当前坐标下没有节点，就继续遍历
- 当前坐标只有一个节点，计算hash值，然后放到新数组对应位置
- 当前坐标是链表，走链表逻辑：
- 遍历链表节点，计算 e.hash & oldCap ，这个值如果是0，说明扩容后，在新数组的坐标和老数组一样，如果为1 ，说明扩容后在新数组的坐标应该是 老数组坐标 + 扩容长度，因此通过计算这个值，可以将链表节点分为高位节点和低位节点
- 定义高位和低位两个链表，不断将链表节点放在这两个新链表尾端
- 然后低位链表放在新数组的i 坐标位置，高位链表放在新数组i+oldcap的位置
- 当前坐标是红黑树，走红黑树的逻辑
- 因为维护红黑树的时候也维护了一个双向链表，因此通过 e.prev e.next就可以遍历整个树 （也就是说遍历链表就等于遍历树）
- 同样是将元素分别放在低位链表和高位链表中，并计算每个链表的长度
- 低位链表的头节点放在新数组的i坐标位置，然后维护链表的红黑树结构（维护前会判断高位链表是否有值，如果为空，说明树结构没有被破坏而是直接迁移到新数组中了，这个时候就可以不用重新维护树结构了）
- 高位链表头节点放在新数组i+oldcap的位置，维护树结构，同3
注意：jdk1.8中，hashmap的扩容，链表节点处理只遍历了一次，而ConcurrentHashMap中遍历了两次。
final HashMap.Node<K, V>[] resize() {
HashMap.Node<K, V>[] oldTab = table;
// 临时存储老的数组长度和老的扩容阈值
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
// 定义新的数组长度和新的扩容阈值
int newCap, newThr = 0;
// oldCap > 0 说明数组已经初始化了
if (oldCap > 0) {
// 当前数组长度已经大于等于最大数组长度了，就把扩容阈值设置为int最大值返回，不需要扩容了
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 否则，长度变为原来2倍
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);
}
// hashmap 初始化的时候，是将数组初始化长度赋值给了threshold，这里开始才是变成扩容阈值。
threshold = newThr;
// 创建新的数组，并将新数组赋值给table
HashMap.Node<K, V>[] newTab = (HashMap.Node<K, V>[]) new HashMap.Node[newCap];
table = newTab;
// 老数组不为空，就走扩容逻辑，否则就直接返回新创建的数组了
if (oldTab != null) {
// 对老数组开始遍历
for (int j = 0; j < oldCap; ++j) {
HashMap.Node<K, V> e;
// 数组的坐标节点为空说明没数据，直接遍历下个坐标
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
// 只有个节点，直接取出该节点，计算hash值，放到新数组中
if (e.next == null) {
newTab[e.hash & (newCap - 1)] = e;
}
// 当前是红黑树，执行红黑树扩容逻辑
else if (e instanceof HashMap.TreeNode) {
((HashMap.TreeNode<K, V>) e).split(this, newTab, j, oldCap);
}
// 当前是链表，执行链表扩容逻辑
else { // preserve order
// 定义高位链表和低位链表
HashMap.Node<K, V> loHead = null, loTail = null;
HashMap.Node<K, V> hiHead = null, hiTail = null;
HashMap.Node<K, V> next;
// 遍历链表
do {
next = e.next;
// e.hash & oldCap 可以计算出当前节点应该放在高位还是低位
if ((e.hash & oldCap) == 0) {
// 将遍历到的节点放在loTail尾部
// loHead指向低位节点的头节点
if (loTail == null) {
loHead = e;
} else {
loTail.next = e;
}
loTail = e;
} else {
// 将遍历到的节点放在hiTail尾部
// hiHead指向高位节点的头节点
if (hiTail == null) {
hiHead = e;
} else {
hiTail.next = e;
}
hiTail = e;
}
} while ((e = next) != null);
// 低位链表的头节点放在 新数组的原index中
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 高位链表的头节点放在 新数组的原index + oldCap 中
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
final void split(HashMap<K, V> map, HashMap.Node<K, V>[] tab, int index, int bit) {
// ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); 这个this 就是数组中取出来的第一个元素，也就是树的头节点
HashMap.TreeNode<K, V> b = this;
// 设置低位首节点和低位尾节点,高位首节点和高位尾节点
HashMap.TreeNode<K, V> loHead = null, loTail = null;
HashMap.TreeNode<K, V> hiHead = null, hiTail = null;
// 这两个值用于记录低位坐标和高位坐标节点的数目
int lc = 0, hc = 0;
// 从根节点开始，对整个树进行遍历，我们介绍了，红黑树其实也维护了双向链表，因此通过 e.prev e.next就可以遍历整个树
for (HashMap.TreeNode<K, V> e = b, next; e != null; e = next) {
next = (HashMap.TreeNode<K, V>) e.next;
e.next = null;
// bit传入的就是oldCap,也就是旧数组的长度，通过hash & 运算，就可以判断是放在新数组的低位坐标还是高位坐标
if ((e.hash & bit) == 0) {
if ((e.prev = loTail) == null) {
loHead = e;
} else {
loTail.next = e;
}
loTail = e;
++lc;
} else {
if ((e.prev = hiTail) == null) {
hiHead = e;
} else {
hiTail.next = e;
}
hiTail = e;
++hc;
}
}
// 低位坐标处理逻辑
if (loHead != null) {
// 低位节点数目小于等于6，就转为链表
if (lc <= UNTREEIFY_THRESHOLD) {
tab[index] = loHead.untreeify(map);
}
// 否则，还是红黑树结构
else {
// 链表头节点赋值给 tab[index]
tab[index] = loHead;
if (hiHead != null)
// 对低位的链表维护红黑树结构
// 为什么加一个hiHead != null 判断呢？因为如果原来的元素全部都分到了低位节点，那说明树结构没有被破坏，就不需要维护了
{
loHead.treeify(tab);
}
}
}
// 高位和低位的处理一样
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD) {
tab[index + bit] = hiHead.untreeify(map);
} else {
tab[index + bit] = hiHead;
if (loHead != null) {
hiHead.treeify(tab);
}
}
}
}3.4 链表转红黑树
final void treeifyBin(HashMap.Node<K, V>[] tab, int hash) {
int n, index;
HashMap.Node<K, V> e;
// 如果数组为空，或者数组长度小于64，就先尝试扩容，因为链表转树的消耗太大了
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) {
resize();
}
// 先拿到当前坐标下的头节点 ，赋值给 e
else if ((e = tab[index = (n - 1) & hash]) != null) {
// 定义头节点和尾节点
HashMap.TreeNode<K, V> hd = null, tl = null;
// 遍历链表
do {
// 将链表节点转化为红黑树节点
HashMap.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);
// 截止到目前，把链表中所有的node对象转变为了红黑树节点，单向链表变成了双向链表
// 把转换后的双向链表，替换原来位置上的单向链表
if ((tab[index] = hd) != null) {
// 树化操作
hd.treeify(tab);
}
}
}
final void treeify(HashMap.Node<K, V>[] tab) {
HashMap.TreeNode<K, V> root = null;
// 因为是调用的hd.treeify(tab)，因此，这里的this就是双向链表的头节点，这里先赋值给了临时变量x
// 开始循环这个双向链表了，x就是循环的元素，next就是下一个节点元素
for (HashMap.TreeNode<K, V> x = this, next; x != null; x = next) {
next = (HashMap.TreeNode<K, V>) x.next;
// 当前节点左右孩子都设置为空
x.left = x.right = null;
if (root == null) {
// 第一次进来，根节点肯定是空，将头节点设置为根节点，染色黑
x.parent = null;
x.red = false;
root = x;
}
// 第一次以后的循环都走下面的分支了
else {
// 定义当前节点的key 和 hash
K k = x.key;
int h = x.hash;
Class<?> kc = null;
// 开始遍历树结构了
for (HashMap.TreeNode<K, V> p = root; ; ) {
// ph 和 pk 定义当前树节点的 hash 和 key ,通过hash判断当前节点要放在树的左边还是右边
// dir代表 往树左边放还是右边放
int dir, ph;
K pk = p.key;
if ((ph = p.hash) > h) {
dir = -1;
} else if (ph < h) {
dir = 1;
}
// hash相等的时候，继续一系列的判断，最终得到dir
else if ((kc == null && (kc = comparableClassFor(k)) == null)
|| (dir = compareComparables(kc, k, pk)) == 0) {
dir = tieBreakOrder(k, pk);
}
HashMap.TreeNode<K, V> xp = p;
// dir <= 0 说明是在左侧，否则是在右侧
// 只有保证当前树节点没有对应的左孩子或者右孩子的时候，才会将当前节点挂上去，否则继续循环遍历树结构
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir <= 0) {
xp.left = x;
} else {
xp.right = x;
}
// 红黑树平衡操作
root = balanceInsertion(root, x);
// 当前节点已经插入红黑树中了，可以跳出当前循环，遍历链表的下一个节点
break;
}
}
}
}
// 把root节点放在当前坐标位置
moveRootToFront(tab, root);
}
/**
* 我们要明确，红黑树节点不但维护了树结构，还维护了双向链表的结构
* 这个方法的作用就是：
* 1、将树的根节点，赋值给tab[i]
* 2、将这个节点，变成双向链表的头节点
*/
static <K, V> void moveRootToFront(HashMap.Node<K, V>[] tab, HashMap.TreeNode<K, V> root) {
int n;
if (root != null && tab != null && (n = tab.length) > 0) {
// 通过根节点 hash计算在数组中的索引位置
int index = (n - 1) & root.hash;
// 取到当前索引的第一个节点
HashMap.TreeNode<K, V> first = (HashMap.TreeNode<K, V>) tab[index];
// 如果root节点和 当前索引位置第一个节点不一样，就把root节点放在当前坐标位置
// 同时要维护双向链表，将root节点变成双向链表的第一个节点。
if (root != first) {
HashMap.Node<K, V> rn;
tab[index] = root;
// 将root节点变成双向链表的第一个节点。
HashMap.TreeNode<K, V> rp = root.prev;
if ((rn = root.next) != null) {
((HashMap.TreeNode<K, V>) rn).prev = rp;
}
if (rp != null) {
rp.next = rn;
}
if (first != null) {
first.prev = root;
}
root.next = first;
root.prev = null;
}
assert checkInvariants(root);
}
}4、删除操作
- 数组没有初始化，或者对应下标节点为空，说明没有该元素，直接返回null
- 查找node，（红黑树或者链表结构）
- 删除node，（红黑树或者链表结构） --- 删除节点的时候即便树的元素小于等于6也不会转为链表，在代码里面没看到，只在扩容的时候会有转换操作。
/**
* 删除方法，主要介绍以下两个参数
* @param matchValue true：只有值也相同的时候才删除
* @param movable true：删除后移动节点，树结构的时候会用到，一般为true
*/
final HashMap.Node<K, V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) {
HashMap.Node<K, V>[] tab;
HashMap.Node<K, V> p;
int n, index;
// 组数没有初始化，或者对应坐标下面没有元素，直接返回null了
if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) {
// node记录要删除的元素
HashMap.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 HashMap.TreeNode) {
// 从树中查找节点
node = ((HashMap.TreeNode<K, V>) p).getTreeNode(hash, key);
} else {
// 从链表中查找节点 ，链表结构时，p是node的前置节点
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)))) {
// node不为空的时候，删除节点
if (node instanceof HashMap.TreeNode) {
((HashMap.TreeNode<K, V>) node).removeTreeNode(this, tab, movable);
} else if (node == p) {
tab[index] = node.next;
} else {
p.next = node.next;
}
// 修改次数加1，size减一，返回删除的node
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
