数据结构
- 1.数组+链表+红黑树
- 2.数组
transient Node<K,V>[] table;
- 3.链表,跟1.7挺像的，维护着下一个节点的引用，单向链表
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
//...........
}
- 4.红黑树，
TreeNode包含的属性有父节点，左子节点，右子节点，是否红色的标志，同时TreeNode还继承了链表Node，所以拥有链表的属性，所以TreeNode即是红黑树，又是双向链表
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
//父节点
TreeNode<K,V> parent; // red-black tree links
//左子节点
TreeNode<K,V> left;
//右子节点
TreeNode<K,V> right;
//上一个节点
TreeNode<K,V> prev; // needed to unlink next upon deletion
//节点是红色还是黑色
boolean red;
//..........
}
问题
-
- 1.7采用头插法，多线程并发有可能导致循环链表，1.8有没有改善，怎么改的？
-
- 1.8加入了红黑树，链表和红黑树是怎么互相转换的，有什么条件？
hash
- 1.8的
HashMap取hash没有像1.7那么复杂，只是简单的让高位参与到数组的定位，大概是因为1.8引入了链表，不用对hash进行太大的扰动
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
定位
根据hash定位到数组，也是跟1.7一样，根据hash &（length-1）
putVal
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//1.初始化数组，因为一开始数组是没有初始化的
//2.resize 后面看
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//1.i = (n - 1) & hash 定位到数组的位置 i是数组的位置
//2.如果i位置上没有元素，就直接新建一个节点放到 i 数组的位置
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
//i位置上的元素不为空
Node<K,V> e; K k;
//当有相同的key时候，e是用来记录相同key的节点，如果有直接替换
//下面有逻辑直接替换
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//如果节点是红黑树 TreeNode 就走红黑树的put逻辑
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//1.不是红黑树，走链表的逻辑
//2.遍历链表
for (int binCount = 0; ; ++binCount) {
//采用尾插法，防止出现循环链表
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//如果 binCount 大于等于 7 也就是当链表中已经有八个元素
//第九个元素加入到链表中，就会从链表转成红黑树，面试题会考
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//转化红黑树的逻辑
treeifyBin(tab, hash);
break;
}
//遍历链表的同时还会检查有没有相同的key，如果有就会走下面的覆盖value的逻辑
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//如果 e != null 说明有相同的key，需要取覆盖value
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//模板方法，子类实现，LinkedhashMap有实现
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//如果长度大于阈值，就会进行扩容
//这个条件跟1.7有点不一样，1.7的时候除了数组长度要大于阈值之外
//还需要数组的某个节点的元素不为空
//resize 上面初始化数组得时候也有调用到
//所以 resize 不止有扩容的作用还有初始化容器的作用
if (++size > threshold)
resize();
// 跟 afterNodeAccess 一样都是模板法方法，LinkedHashMap有实现
afterNodeInsertion(evict);
return null;
}
putVal 总结:
- 1.
new的时候没有初始化数组，在putVal的时候调用resize初始化数组 - 2.
hash取值跟1.7不一样，但是数组定位跟1.7一样 - 3.如果数组节点为空就直接在数组上放数据
- 4.如果数组节点不为空就会有三个
if - 5.第一个if：就会先判断是否头节点的
hash跟put的hash一样，如果一样就覆盖value - 6.第二个if：判断是红黑树，如果是红黑树就走
putTreeVal逻辑 - 7.第三个id：就是链表。会遍历链表，如果链表已经有8个，插入第九个会通过
treeifyBin转为红黑树。遍历链表的同时也会判断是否有hash一样的节点，如果有就会覆盖value - 8.当插入的逻辑走完，在最后就会判断是否需要扩容，条件就是容器大小大于阈值。这个点跟1.7不一样，1.7还去判断了数组位置上的节点是否为空
- 9.所以
putVal的逻辑还有：a.扩容和容器初始化方法resizeb.插入红黑树方法putTreeValc.红黑树转链表方法：treeifyBin
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) {
//如果旧容量大于Integer的最大值就不进行扩容
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 {
//如果是数组大小=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)
newTab[e.hash & (newCap - 1)] = e;
//如果是红黑树，走 split 逻辑
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else {
//走链表的逻辑
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
//1.因为 oldCap 的大小是二的幂次方，所以
//2.e.hash & oldCap 要么是零要么非零
//3.为零的放在 loHead 上组成链表，然后直接 放到新数组原来位置
//4.非零的都放在 hiHead 上组成链表，然后直接放到
//新数组原来位置+旧数组大小
//5.这个迁移就跟1.7完全不一样了
//6. 3跟4为什么会满足呢，因为oldCap跟newCap相差一位
//e.hash & oldCap) == 0 的结果取决于oldCap最高位跟hash&的结果
//如果hash在oldCap的最高位上是0说明在新数组的位置还是j
//如果hash在oldCap的最高位上是1说明在新数组的位置是j+oldCap
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;
}
resize 总结：
- 1.
resize既有扩容的作用，也有初始化数组的作用 - 2.扩容的时候数组大小是原来的两倍
- 3.扩容的时候会遍历整个数组，然后分三种情况
- 4.第一种：会先判断头节点的下一个节点是否为空，如果为空就直接将这个节点放到新的数组里去
- 5.第二种：如果节点是红黑树的话就走
split的逻辑 - 6.第三种，如果节点是链表的话，就通过
e.hash & oldCap) == 0来判断是要放到数组的j位还是j+oldCap，j是值原来数组的位置，oldCap是指旧数组的大小，这个跟1.7扩容的头插法不一样了。关键要理解这个表达式e.hash & oldCap) == 0，这个表达式的关键就是扩容是原来的两倍，在二进制上就是比原来多一位 - 7.所以这个扩容就剩下红黑树的扩容
split
红黑树扩容 todo
putTreeVal
插入红黑树 todo
treeifyBin
链表转红黑树
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//链表转红黑树，除了链表的长度已经有八个之外还需要数组长度大于等于 64
//如果数组长度小于64就需要对链表进行扩容，所以扩容除了
//数组大小达到阈值之外，链表要转红黑树的时候如果数组长度小于64也需要进行扩容
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
//获取头节点开始从链表转为红黑树
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
//Node 转化为 TreeNode 单纯的赋值key，value，hash
TreeNode<K,V> p = replacementTreeNode(e, null);
//第一次进来，tl == null
//tl相当于双向链表的尾节点
//hd相当于双向链表的头节点
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);
}
}
treeifyBin 总结：
- 1.进入
treeifyBin会先判断是否数组大小 小于 64 ，如果小于64说明需要扩容，所以扩容的情况不仅仅是数组大小大于阈值，还有可能是将要链表转为树的时候发现数组大小小于64 - 2.如果链表长度已经有八位了，而且数组长度大于等于64，就需要进行链表转为红黑树
- 3.转化的时候先遍历链表，将
node转化为TreeNode，之后通过treeify设置红黑树的属性
treeifyBin
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
//this 等于 双向链表的头节点，现在是要从双向链表转为红黑树
for (TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
//1.如果头节点是空就是第一次进入循环
//2.设置头节点的属性，比如头节点一定是黑色，父类是空
if (root == null) {
x.parent = null;
x.red = false;
root = x;
}
//非头节点
else {
K k = x.key;
int h = x.hash;
Class<?> kc = null;
//现在是要往从双向链表一个一个取出放到红黑树中
//所以外层遍历双向链表，里层遍历树，通过比较 hash 值来确定
//新树节点放到哪里
for (TreeNode<K,V> p = root;;) {
int dir, ph;
K pk = p.key;
//1.比较hash
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
//2.遇到hash相等于的 先判断有没有继承`Comparable`接口
//3.如果有继承 `Comparable `就用`Comparable#compareTo`比较
//4.如果 `Comparable#compareTo` 还是相等，就通过
//System.identityHashCode 获取的hash来比较
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
TreeNode<K,V> xp = p;
//1.dir 是比较的结果
//2.如果 dir <= 0 就需要走树的左边否则走树的右边，因为还要往
//左边或者右边比较大小，所以判断 比较节点p的左右节点是否为空
//如果为空就可以放实设置子节点，如果不为空就要再次循环下一个节点
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;
}
}
}
}
//将树重新放到头节点
moveRootToFront(tab, root);
}
treeify 总结：
- 1.
treeify其实是双向链表转树的过程 - 2.链表转树的过程有两层循环，一层获取链表的节点，第二次是插入树的时候需要通过比较
hash来判断插在哪里 - 3.怎么比较
hash，最简单的是直接比较hash大小，如果hash大小一样，就判断是否继承Compareable接口，如果继承就通过compareTo接口比较，如果还是相等就通过System.identityHashCode方法获取key的hash值，这个hash值不是用户重写的hashCode - 4.比较完就可以设置节点，是左节点还是右节点，设置完调用
balanceInsertion去重新平衡树 - 5.链表全部迁移到树之后通过
moveRootToFront去将树的root节点设置到数组的位置 - 6.所以链表转化成树还差
balanceInsertion平衡树
balanceInsertion 平衡红黑树
每次插入树之后都需要去平衡树，让红黑树满足条件
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
TreeNode<K,V> x) {
x.red = true;
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
//如果新增节点是头节点就不需要平衡了
//设置头节点颜色为黑色
if ((xp = x.parent) == null) {
x.red = false;
return x;
}
//1.xp是新增节点的父节点
//2.如果新增节点的父节点是黑色，或者新增节点的父节点是头节点就不需要平衡树了
else if (!xp.red || (xpp = xp.parent) == null)
return root;
//1.xpp是新增节点的祖父节点
//2.如果父节点是祖父节点的左子节点就走下面的逻辑
if (xp == (xppl = xpp.left)) {
//1.如果xppr是新增节点的叔父节点
//2.如果叔父节点也是红色
//3.就需要变色，将叔父节点和父节点变为黑色，祖父节点变为红色
//4.x=xpp，意思是说祖父节点变为红色，就要以祖父节点开始进行树的平衡
//祖父节点变为红色有可能导致上面的节点不符合红黑树规范
if ((xppr = xpp.right) != null && xppr.red) {
xppr.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
//下面有两种情况，要么叔父节点为空，要么叔父节点为黑色
//这两种情况都不是单单变色能够解决的，需要旋转
else {
//1.如果新增节点是右节点，需要将父节点左旋转
//2.rotateLeft 将父节点左旋，左旋的效果是
//父节点变为新增节点的左子节点,新增节点为祖父节点的左子节点
//3.重新设置子节点，父节点，祖父节点（x，xp，xpp）
//4.重新设置完子父两个个节点都是朝左边的
//5.现在的x节点其实是父节点，就当作是新增节点
if (x == xp.right) {
root = rotateLeft (root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
// 1.父节点不为空
//2.设置父节点为黑色
//3.如果祖父节点不为空，就设置祖父节点为红色，然后祖父节点
//右旋 rotateRight 右旋之后，祖父节点为父节点的右子节点
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true;
root = rotateRight(root, xpp);
}
}
}
}
//如果父节点是祖父节点的右节点，下面的逻辑跟上面大if的逻辑有点像
else {
//1.此时 xppl 是叔父节点，如果叔父节点跟父节点都是 红色
//2.叔父节点跟父节点都变色黑色
//3.祖父节点红色，x=xpp 以祖父节点进行树的平衡
if (xppl != null && xppl.red) {
xppl.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
else {
//1.叔父节点为空或者黑色
//2.新增节点是父节点的左子节点
//3.如果满足2 对父节点进行 rotateRight 右旋
//4.父节点右旋之后，父节点变为子节点的右子节点，父节点和子节点都在右边
if (x == xp.left) {
root = rotateRight(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
//5.到了这里 父节点跟子节点都在 右边了
//6.修改父节点（如果有走上一个子节点那就是新增节点）的颜色为黑色
//7.对祖父节点进行左旋转，左旋转之后祖父节点为父节点的左子节点
//8.修改父节点颜色为红色
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true;
root = rotateLeft(root, xpp);
}
}
}
}
}
}
balanceInsertion 总结：
未完待续……………….