hashMap是基于hash表（散列表），实现Map接口得双列集合，数据结构是--链表散列 也就是 数组+链表，key唯一得value可以重复，允许储存null 键 null值，元素是无序的。
哈希表
数组：
一段连续的控件储存数据，指定下标的查找，时间复杂度O（1），通过给定值查找，需要遍历数组，自己对比复杂度O（n）,二分查找插值查找，复杂度O（logn）.
线性链表：
增删仅处理结点，时间复杂度O（1）查找需要遍历也就是O（n）
二叉树：
对一颗相对平衡的有序二叉树，对其进行插入，查找，删除，平均复杂度O(logn)
哈希表：
哈希表中添加，删除，查询等操作很，性能十分的高，不考虑hash冲突的情况下，仅一次定位就可以完成，时间复杂度O（1）哈希表的主干就是数组
hash冲突：
当有数据插入的时候 会先给值用hash函数计算一个内存地址，再放入对应的数组上边，而有时候也不能保证hash值不重复，这就是hash碰撞，也叫hash冲突。
当hash冲突的时候，有几种解决办法 比如 开放地址 再散列函数 而hashMap采用的是 链地址法 也就是 数组加链表的形式。
链表主要解决的是hash冲突，如果定位的中不含有链表，那么对于链表，对于添加操作 性能很高，直接定位，如果定位的有链表，要遍历链表，有此值 直接覆盖，否则新增，对于查找来讲，要根据equals方法注意对比，所以链表越少效率越高。
hash容量必须是2的n次方
因为在hash计算中让值更分布均匀，减少hash碰撞，提高储存效率。
hashmap 属性
static final int DEFAULT_INITIAL_CAPACITY = 16; // 默认容量
static final int MAXIMUM_CAPACITY = 1073741824;//集合最大容量
static final float DEFAULT_LOAD_FACTOR = 0.75F;//默认负载因子
static final int TREEIFY_THRESHOLD = 8;//转换树的阈值
static final int UNTREEIFY_THRESHOLD = 6;
当Map里面的数量超过这个值时，表中的桶才能进行树形化 ，否则桶内元素太多时会扩容，而不是树形化 为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD
static final int MIN_TREEIFY_CAPACITY = 64; // 树最大容量
transient HashMap.Node<K, V>[] table; // 初始化数组
transient Set<Entry<K, V>> entrySet; // 存放缓存的
transient 关键字 是 不序列化的意思
int threshold;; // 用来调整大小下一个容量的值计算方式为(容量*负载因子)
final float loadFactor;//哈希表的加载因子
常用属性
1.table在JDK1.8中我们了解到HashMap是由数组加链表加红黑树来组成的结构其中table就是HashMap中的数组
2.size为HashMap中K-V的实时数量
3.loadFactor加载因子，是用来衡量 HashMap 满的程度，计算HashMap的实时加载因子的方法为：size/capacity，而不是占用桶的数量去除以capacity。capacity 是桶的数量，也就是 table 的长度length。
4.threshold计算公式：capacity * loadFactor。这个值是当前已占用数组长度的最大值。过这个数目就重新resize(扩容)，扩容后的 HashMap 容量是之前容量的两倍
构造方法
// 构造一个空的 HashMap具有指定的初始容量和默认负载因子（0.75）。
public HashMap() {
this.loadFactor = 0.75F;
}
//构造一个空的 HashMap具有指定的初始容量和负载因子
public HashMap(int var1, float var2) {
// 判断容量是否大于0，否则抛出异常
if (var1 < 0) {
throw new IllegalArgumentException("Illegal initial capacity: " + var1);
} else {
// 查看容量是否大于最大值 如果大 赋值最大值
if (var1 > 1073741824) {
var1 = 1073741824;
}
// 负载因子 大于0 并且是一个数值
if (var2 > 0.0F && !Float.isNaN(var2)) {
this.loadFactor = var2;
this.threshold = tableSizeFor(var1);
} else {
throw new IllegalArgumentException("Illegal load factor: " + var2);
}
}
}
// 构造一个指定容量大小的
public HashMap(int var1) {
this(var1, 0.75F);
}
// 构建一个map形式的map
public HashMap(Map<? extends K, ? extends V> var1) {
this.loadFactor = 0.75F;
this.putMapEntries(var1, false);
}
put方法
// 调用的是putval方法 和hash方法
public V put(K var1, V var2) {
return this.putVal(hash(var1), var1, var2, false, true);
}
// hash方法 可以看出 如果key为空 hash方法会返回0 所以可以存储 null 值 也是hashtable的不用
// 它通过 hash & (table.length -1)来得到该对象的保存位，前面说过 HashMap 底层数组的长度总是2的n次方，
//这是HashMap在速度上的优化。当 length 总是2的n次方时，hash & (length-1)运算等价于对 length 取模，
//也就是 hash%length，但是&比%具有更高的效率。比如 n % 32 = n & (32 -1)。
static final int hash(Object var0) {
int var1;
return var0 == null ? 0 : (var1 = var0.hashCode()) ^ var1 >>> 16;
}
putval 方法 很关键的方法
Node<K,V>[] tab;
Node<K,V> p;
int n, i;
// 判断数字长度如果为0 进行初始化
if ((tab = table) == null || (n = tab.length) == 0)
//数组长度初始长度
n = (tab = resize()).length;
// i 的取模运算 也就是key值的确定 如果key 为null，数组新增一个元素newNode 关联的是本地方法
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
// tab[i]不为空代表代表有值， 直接替换对应的值
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 如果p值对象 是否为红黑树
else if (p instanceof 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);
// 判断是否为8 也就是 树形节点的阈值 大于就转换成红黑树
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))))
break;
p = e;
}
}
// 如果在链表中有值们直接替换
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
// 记录修改次数
++modCount;
// 如果次数 大于threshold阈值 扩容
if (++size > threshold)
resize();
// 如果继承hashmap 可以是实现它
afterNodeInsertion(evict);
return null;
从上面代码可以看到putVal()方法的流程：
- 判断哈希表是否为空，如果为空，调用resize()方法进行创建哈希表
- 根据hash值得到哈希表中桶的头节点，如果为null，说明是第一个节点，直接调用newNode()方法添加节点即可
- 如果发生了哈希冲突，那么首先会得到头节点，比较是否相同，如果相同，则进行节点值的替换返回
- 如果头节点不相同，但是头节点已经是TreeNode了，说明该桶处已经是红黑树了，那么调用putTreeVal()方法将该结点加入到红黑树中
- 如果头节点不是TreeNode，说明仍然是链表阶段，那么就需要从头开始遍历，一旦找到了相同的节点就跳出循环或者直到了链表尾部，那么将该节点插入到链表尾部
- 如果插入到链表尾部后，链表个数达到了阈值8，那么将会将该链表转换成红黑树，调用treeifyBin()方法
- 如果是新加一个数据，那么将size+1，此时如果size超过了阈值，那么需要调用resize()方法进行扩容
resize()方法
首先是resize()方法，resize()在哈希表为null时将会初始化，但是在已经初始化后就会进行容量扩展
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; // double threshold
}
// 初始容量设置为阈值
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
// 初始阈值为零表示使用默认值 使用默认的容量16和阈值16*0.75=12
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 如果阈值等于0 赋值
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;
// 旧数组 tab 不是null 遍历旧表
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
// 把旧表设置null 帮助gc
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// 如果为红黑树 仍为红黑树
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// 否则为链表
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
通过e.hash & oldCap将链表分为两队，参考知乎上的一段解释
/**
* 把链表上的键值对按hash值分成lo和hi两串，lo串的新索引位置与原先相同[原先位
* j]，hi串的新索引位置为[原先位置j+oldCap]；
* 链表的键值对加入lo还是hi串取决于 判断条件if ((e.hash & oldCap) == 0)，因为* capacity是2的幂，所以oldCap为10...0的二进制形式，若判断条件为真，意味着
* oldCap为1的那位对应的hash位为0，对新索引的计算没有影响（新索引
* =hash&(newCap-*1)，newCap=oldCap<<2）；若判断条件为假，则 oldCap为1的那位* 对应的hash位为1，
* 即新索引=hash&( newCap-1 )= hash&( (oldCap<<2) - 1)，相当于多了10...0，
* 即 oldCap
* 例子：
* 旧容量=16，二进制10000；新容量=32，二进制100000
* 旧索引的计算：
* hash = xxxx xxxx xxxy xxxx
* 旧容量-1 1111
* &运算 xxxx
* 新索引的计算：
* hash = xxxx xxxx xxxy xxxx
* 新容量-1 1 1111
* &运算 y xxxx
* 新索引 = 旧索引 + y0000，若判断条件为真，则y=0(lo串索引不变)，否则y=1(hi串
* 索引=旧索引+旧容量10000)
*/
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;
}
从上面可以看到，resize()首先获取新容量以及新阈值，然后根据新容量创建新表。如果是扩容操作，则需要进行rehash操作，通过e.hash&oldCap将链表分为两列，更好地均匀分布在新表中。
split方法 把旧的红黑树 赋值到新表中
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;
// Relink into lo and hi lists, preserving order 重新链接到lo和hi列表，保持顺序
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;
// 遍历
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next;
e.next = null;
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] = loHead;
if (hiHead != null) // (else is already treeified else已经被树形化了)
loHead.treeify(tab);
}
}
// 如果存在低端
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)
// 如果小于6的阈值 把红黑树 转成 链表
tab[index + bit] = hiHead.untreeify(map);
else {
// 否则将链表转成红黑树
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
}
TreeNode的split方法首先将头节点从头开始遍历，区分出两条单链表，再根据如果节点数小于等于6，那么将单链表的每个TreeNode转换成Node节点；否则将单链表转换成红黑树结构。
至此，resize()方法结束。需要注意的是rehash时，由于容量扩大一倍，本来一条链表有可能会分成两条链表，而如果将红黑树结构复制到新表时，有可能需要完成红黑树到单链表的转换。
treeifyBin()方法 将链表转成 红黑树
final void treeifyBin(Node<K,V>[] tab, int hash) {
// 定义数组大小，下标，node 对象 表示当前节点
int n, index; Node<K,V> e;
// 如果表的大小 小于64 直接扩容，不进行树形化
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
// 如果不为null 取出链表的节点
else if ((e = tab[index = (n - 1) & hash]) != null) {
//定义头节点hd 和 尾节点tl
TreeNode<K,V> hd = null, tl = null;
do {
//该循环主要是将原单向链表转化为双向链表
TreeNode<K,V> p = replacementTreeNode(e, null);
//如果尾节点为null 表示 第一次创建 此时 头节点 等于 p
if (tl == null)
hd = p;
//此时 根节点 已经有了tl尾节点指向上次创建过的树形节点
else {
// 此时p上次创建的后继元 本次的新节点 产生一个prev 链
p.prev = tl;
//产生的前驱元与当前节点的next链
tl.next = p;
}
// 尾节点指向当前节点
tl = p;
} while ((e = e.next) != null);
//如果当前节点等于头节点 并部位null 调用treeify将该TreeNode结构的单链表转换成红黑树
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
treeify( ) 链表 转 红黑树
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;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
final void treeify(Node<K,V>[] tab) {//将链表转换成红黑树
TreeNode<K,V> root = null;
for (TreeNode<K,V> x = this, next; x != null; x = next) {//遍历链表中的每一个TreeNode，当前结点为x
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
if (root == null) { //对于第一个树结点，当前红黑树的root == null，所以第一个结点是树的根，设置为黑色
x.parent = null;
x.red = false;
root = x;
}
else { //对于余下的结点：
K k = x.key;
int h = x.hash;
Class<?> kc = null;
for (TreeNode<K,V> p = root; ; ) {//从根结点开始遍历，寻找当前结点x的插入位置
int dir, ph;
K pk = p.key;
if ((ph = p.hash) > h) //如果当前结点的hash值小于根结点的hash值，方向dir = -1；
dir = -1;
else if (ph < h) //如果当前结点的hash值大于根结点的hash值，方向dir = 1；
dir = 1;
else if ((kc == null && //如果x结点的key没有实现comparable接口，或者其key和根结点的key相等（k.compareTo(x) == 0）仲裁插入规则
(kc = comparableClassFor(k)) == null) || //只有k的类型K直接实现了Comparable<K>接口，才返回K的class，否则返回null，间接实现也不行。
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk); //仲裁插入规则
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) { //如果p的左右结点都不为null，继续for循环，否则执行插入
x.parent = xp;
if (dir <= 0) //dir <= 0，插入到左儿子
xp.left = x;
else //否则插入到右结点
xp.right = x;
root = balanceInsertion(root, x); //插入后进行树的调整，使之符合红黑树的性质
break;
}
}
}
}
moveRootToFront(tab, root); //Ensures that the given root is the first node of its bin.
}
}
/**
* Tie-breaking utility for ordering insertions when equal
* hashCodes and non-comparable. We don't require a total
* order, just a consistent insertion rule to maintain
* equivalence across rebalancings. Tie-breaking further than
* necessary simplifies testing a bit.
*/
static int tieBreakOrder(Object a, Object b) {
int d;
if (a == null || b == null ||
(d = a.getClass().getName().
compareTo(b.getClass().getName())) == 0)
d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
-1 : 1);
return d;
}
红黑树概述
红黑树是一种特殊的二叉查找树，和平衡二叉树都是二叉树的变体，而平衡二叉树 AVL树是严格维持平衡的，红黑树是黑平衡的，维持平衡需要额外的操作，这就加大了数据结构的时间复杂度，所以红黑树可以看作是二叉搜索树和AVL树的一个折中，维持平衡的同时也不需要花太多时间维护数据结构的性质。红黑树在很多地方都有应用。
红黑树特性
每个结点是黑色或者红色。
根结点是黑色。
每个叶子结点（NIL）是黑色。 [注意：这里叶子结点，是指为空(NIL或NULL)的叶子结点！]
如果一个结点是红色的，则它的子结点必须是黑色的。
每个结点到叶子结点NIL所经过的黑色结点的个数一样的。[确保没有一条路径会比其他路径长出俩倍，所以红黑树是相对接近平衡的二叉树的！]
所有hashmap中balanceInsertion这个方法进行旋转和变色，可以使这颗树重新成为红黑树调整，不然就不是红黑树了。
左旋：以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，其左子结点保持不变
右旋：以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，其右子结点保持不变。
更多红黑树数据结构可以自己查询。
balanceInsertion平衡算法解析
static <K, V> TreeNode<K, V> balanceInsertion(TreeNode<K, V> root, TreeNode<K, V> x)
{
// 正如开头所说，新加入树节点默认都是红色的，不会破坏树的结构。
x.red = true;
// 这些变量名不是作者随便定义的都是有意义的。
// xp：x parent，代表x的父节点。
// xpp：x parent parent，代表x的祖父节点
// xppl：x parent parent left，代表x的祖父的左节点。
// xppr：x parent parent right，代表x的祖父的右节点。
for (TreeNode<K, V> xp, xpp, xppl, xppr;;)
{
// 如果x的父节点为null说明只有一个节点，该节点为根节点，根节点为黑色，red = false。
if ((xp = x.parent) == null)
{
x.red = false;
return x;
}
// 进入else说明不是根节点。
// 如果父节点是黑色，那么大吉大利（今晚吃鸡），红色的x节点可以直接添加到黑色节点后面，返回根就行了不需要任何多余的操作。
// 如果父节点是红色的，但祖父节点为空的话也可以直接返回根此时父节点就是根节点，因为根必须是黑色的，添加在后面没有任何问题。
else if (!xp.red || (xpp = xp.parent) == null)
return root;
// 一旦我们进入到这里就说明了两件是情
// 1.x的父节点xp是红色的，这样就遇到两个红色节点相连的问题，所以必须经过旋转变换。
// 2.x的祖父节点xpp不为空。
// 判断如果父节点是否是祖父节点的左节点
if (xp == (xppl = xpp.left))
{
// 父节点xp是祖父的左节点xppr
// 判断祖父节点的右节点不为空并且是否是红色的
// 此时xpp的左右节点都是红的，所以直接进行上面所说的第三种变换，将两个子节点变成黑色，将xpp变成红色，然后将红色节点x顺利的添加到了xp的后面。
// 这里大家有疑问为什么将x = xpp？
// 这是由于将xpp变成红色以后可能与xpp的父节点发生两个相连红色节点的冲突，这就又构成了第二种旋转变换，所以必须从底向上的进行变换，直到根。
// 所以令x = xpp，然后进行下下一层循环，接着往上走。
if ((xppr = xpp.right) != null && xppr.red)
{
xppr.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
// 进入到这个else里面说明。
// 父节点xp是祖父的左节点xppr。
// 祖父节点xpp的右节点xppr是黑色节点或者为空，默认规定空节点也是黑色的。
// 下面要判断x是xp的左节点还是右节点。
else
{
// x是xp的右节点，此时的结构是：xpp左->xp右->x。这明显是第二中变换需要进行两次旋转，这里先进行一次旋转。
// 下面是第一次旋转。
if (x == xp.right)
{
root = rotateLeft(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
// 针对本身就是xpp左->xp左->x的结构或者由于上面的旋转造成的这种结构进行一次旋转。
if (xp != null)
{
xp.red = false;
if (xpp != null)
{
xpp.red = true;
root = rotateRight(root, xpp);
}
}
}
}
// 这里的分析方式和前面的相对称只不过全部在右测不再重复分析。
else
{
if (xppl != null && xppl.red)
{
xppl.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
} else
{
if (x == xp.left)
{
root = rotateRight(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null)
{
xp.red = false;
if (xpp != null)
{
xpp.red = true;
root = rotateLeft(root, xpp);
}
}
}
}
}
}
什么时候进行旋转？
判断树的结构是否满足h <= log2(n+1)，如果不满足则需要进行旋转，如果满足只需要重新进行着色即可。
如何确定左旋还是右旋？
个人理解，如果原来的树曲曲折折，需要先掰直了下面部分，如果是直线的树了 再把上面部分掰弯，形成一个倒V型。这个只是方面理解，真正的原因是，如果不采用上面的步骤进行旋转，旋转顺序换掉，都会得到一种结果那就是，整个二叉树不成立了，失去了二叉树的意义了。当然我们也可以一步到位，以空间换时间，这是没有问题的，从复杂度来讲左旋和右旋是最精炼的，最基础的，可以完美适配的。
rotateLeft（左旋）
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root, TreeNode<K,V> p) {
TreeNode<K,V> r, pp, rl;
if (p != null && (r = p.right) != null) {
if ((rl = p.right = r.left) != null)
rl.parent = p;
if ((pp = r.parent = p.parent) == null)
// 只有当p 已经探到了树的底部的时候，左旋，会改变根的指向，所以这里需要修改掉root 的指向
(root = r).red = false;
else if (pp.left == p)
pp.left = r;
else
pp.right = r;
r.left = p;
p.parent = r;
}
return root;
}
rotateRight（右旋）
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root, TreeNode<K,V> p) {
TreeNode<K,V> l, pp, lr;
if (p != null && (l = p.left) != null) {
if ((lr = p.left = l.right) != null)
lr.parent = p;
if ((pp = l.parent = p.parent) == null)
// 只有当p 已经探到了树的底部的时候，左旋，会改变根的指向，所以这里需要修改掉root 的指向
(root = l).red = false;
else if (pp.right == p)
pp.right = l;
else
pp.left = l;
l.right = p;
p.parent = l;
}
return root;
}
putTreeVal 红黑树 插入实现
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
TreeNode<K,V> root = (parent != null) ? root() : this;
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk;
// 比较要插入值 与 节点的 hash值等属性 的大小
// 确定大小之后然后选择 左右子树 循环继续比较
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
if (!searched) {
TreeNode<K,V> q, ch;
searched = true;
if (((ch = p.left) != null &&
(q = ch.find(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.find(h, k, kc)) != null))
return q;
}
dir = tieBreakOrder(k, pk);
}
TreeNode<K,V> xp = p;
// 只有确认了 要插入的位置的 左子树 或者 右子树为空，即找到了要插入节点的位置
if ((p = (dir <= 0) ? p.left : p.right) == null) {
Node<K,V> xpn = xp.next;
// 创建新的 树的叶子节点
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
// 插入到指定的 分支上
if (dir <= 0)
xp.left = x;
else
xp.right = x;
xp.next = x;
x.parent = x.prev = xp;
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x;
// 这里需要注意了 这有执行了两步操作，
// balanceInsertion这一步涉及到了 红黑树的平衡算法，我们只看它
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
removeTreeNode
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
boolean movable) {
// section 1：通过prev和next删除当前节点
int n;
if (tab == null || (n = tab.length) == 0)
return;
int index = (n - 1) & hash;
TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
if (pred == null)
tab[index] = first = succ;
else
pred.next = succ;
if (succ != null)
succ.prev = pred;
if (first == null)
return;
// section 2：当节点数量小于7时转换成链栈的形式存储
if (root.parent != null)
root = root.root();
if (root == null || root.right == null ||
(rl = root.left) == null || rl.left == null) {
tab[index] = first.untreeify(map); // too small
return;
}
// section 3：判断当前树节点情况
TreeNode<K,V> p = this, pl = left, pr = right, replacement;
if (pl != null && pr != null) {
TreeNode<K,V> s = pr, sl;
while ((sl = s.left) != null) // find successor
s = sl;
boolean c = s.red; s.red = p.red; p.red = c; // swap colors
TreeNode<K,V> sr = s.right;
TreeNode<K,V> pp = p.parent;
if (s == pr) { // p was s's direct parent
p.parent = s;
s.right = p;
}
else {
TreeNode<K,V> sp = s.parent;
if ((p.parent = sp) != null) {
if (s == sp.left)
sp.left = p;
else
sp.right = p;
}
if ((s.right = pr) != null)
pr.parent = s;
}
p.left = null;
if ((p.right = sr) != null)
sr.parent = p;
if ((s.left = pl) != null)
pl.parent = s;
if ((s.parent = pp) == null)
root = s;
else if (p == pp.left)
pp.left = s;
else
pp.right = s;
if (sr != null)
replacement = sr;
else
replacement = p;
}
else if (pl != null)
replacement = pl;
else if (pr != null)
replacement = pr;
else
replacement = p;
// section 4：实现删除树节点逻辑
if (replacement != p) {
TreeNode<K,V> pp = replacement.parent = p.parent;
if (pp == null)
root = replacement;
else if (p == pp.left)
pp.left = replacement;
else
pp.right = replacement;
p.left = p.right = p.parent = null;
}
TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);
if (replacement == p) { // detach
TreeNode<K,V> pp = p.parent;
p.parent = null;
if (pp != null) {
if (p == pp.left)
pp.left = null;
else if (p == pp.right)
pp.right = null;
}
}
if (movable)
moveRootToFront(tab, r);
}
方法实现，链栈 + 树实现删除当前节点
链栈：prev、next
树：parent、left、right
具体步骤为，
- 先通过prev和next实现删除逻辑
- 由节点数判断当前存储形式
- 若为树则追加实现parent、left、right
- 由根节点的left.left节点作为判断当前存储状态的核心，链栈的节点数最多为6个
- 删除树节点的方法，删除时使其满足节点位于单链上(操作简便)
balanceDeletion
static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
TreeNode<K,V> x) {
for (TreeNode<K,V> xp, xpl, xpr;;) {
//结束循环条件1，平衡节点 == root
if (x == null || x == root)
return root;
else if ((xp = x.parent) == null) {
x.red = false;
return x;
}
//循环结束条件2，平衡节点为红色
else if (x.red) {
x.red = false;
return root;
}
//向上平衡
//平衡节点位于左节点
else if ((xpl = xp.left) == x) {
if ((xpr = xp.right) != null && xpr.red) {
xpr.red = false;
xp.red = true;
root = rotateLeft(root, xp);
xpr = (xp = x.parent) == null ? null : xp.right;
}
if (xpr == null)
x = xp;
else {
TreeNode<K,V> sl = xpr.left, sr = xpr.right;
if ((sr == null || !sr.red) &&
(sl == null || !sl.red)) {
xpr.red = true;
x = xp;
}
else {
if (sr == null || !sr.red) {
if (sl != null)
sl.red = false;
xpr.red = true;
root = rotateRight(root, xpr);
xpr = (xp = x.parent) == null ?
null : xp.right;
}
if (xpr != null) {
xpr.red = (xp == null) ? false : xp.red;
if ((sr = xpr.right) != null)
sr.red = false;
}
if (xp != null) {
xp.red = false;
root = rotateLeft(root, xp);
}
x = root;
}
}
}
//平衡节点位于右节点
else { // symmetric
if (xpl != null && xpl.red) {
xpl.red = false;
xp.red = true;
root = rotateRight(root, xp);
xpl = (xp = x.parent) == null ? null : xp.left;
}
if (xpl == null)
x = xp;
else {
TreeNode<K,V> sl = xpl.left, sr = xpl.right;
if ((sl == null || !sl.red) &&
(sr == null || !sr.red)) {
xpl.red = true;
x = xp;
}
else {
if (sl == null || !sl.red) {
if (sr != null)
sr.red = false;
xpl.red = true;
root = rotateLeft(root, xpl);
xpl = (xp = x.parent) == null ?
null : xp.left;
}
if (xpl != null) {
xpl.red = (xp == null) ? false : xp.red;
if ((sl = xpl.left) != null)
sl.red = false;
}
if (xp != null) {
xp.red = false;
root = rotateRight(root, xp);
}
x = root;
}
}
}
}
}
方法实现，由结束判断 + 向上平衡两部分实现
结束判断，平衡节点为root或red，颜色变更结束平衡
-
结束判断，平衡节点为root或red，颜色变更结束平衡
-
向上平衡(平衡节点 = xp)，循环实现从删除节点开始向父节点逐步平衡，每次平衡需要判断兄弟节点和兄弟节点的内侧子节点的颜色，红色则需要通过树旋转来实现平衡
-
平衡树有可能导致根节点发生改变，每次平衡树后都应该在table数组中重置新节点。
split
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;
// Relink into lo and hi lists, preserving order
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;
for (TreeNode<K,V> e = b, next; e != null; e = next) {
//剥离节点
next = (TreeNode<K,V>)e.next;
e.next = null;
//链接可保留在原数组位置的节点
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) {
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
if (hiHead != null) // (else is already treeified)
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);
}
}
}
//补充：
/**
* The bin count threshold for untreeifying a (split) bin during a
* resize operation. Should be less than TREEIFY_THRESHOLD, and at
* most 6 to mesh with shrinkage detection under removal.
*/
static final int UNTREEIFY_THRESHOLD = 6;
get方法
public V get(Object key) {
// 当key为null, 这里不讨论，后面统一讲
if (key == null)
return getForNullKey();
// 根据key得到key对应的Entry
Entry<K,V> entry = getEntry(key);
//
return null == entry ? null : entry.getValue();
}
final Entry<K,V> getEntry(Object key) {
// 根据key算出hash
int hash = (key == null) ? 0 : hash(key);
// 先算出hash在table中存储的index，然后遍历table中下标为index的单向链表
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
// 如果hash和key都相同，则把Entry返回
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
先根据key算出hash，然后根据hash得到在table上的index，再遍历talbe[index]的单向链表，这时候需要看要删除的元素是否就是单向链表的表头，如果是，则直接让table[index]=next，即删除了需要删除的元素；如果不是单向链表的头，那表示有前面的结点，则让pre.next = next，也删除了需要删除的元素。
线程安全问题
由前面HashMap的put和get方法分析可得，put和get方法真实操作的都是Entry[] table这个数组，而所有操作都没有进行同步处理，所以HashMap是线程不安全的。如果想要实现线程安全，推荐使用ConcurrentHashMap。
几种Map实现类的特性对比
1.hashMap 是一个散列表 最常用，无序，线程不安全的
2.hashTable 是一个散列表 ，无序，线程安全的
3.LinkHashMap 有序（插入顺），线程不安全，通过双向链表 使用插入顺序让键值有序。也由于维护元素的插入顺序，所以性能比hashMap差些。
4.treeMap 红黑树 有序 线程不安全的 是通过实现 sortMap 接口实现的 来保持key排序，从而保证实现comparable接口，所以key必须都是一个类型 自定类需要重写equest 方法 和 hashcode 方法 。
5.IdentityHashMap使用==（对比的引用）来判断key是否相等，HashMap使用equals来判断key是否相等。因此IdentityHashMap可以存放相同的key值。
6.WeakHashMap key采用“弱引用”方式，只要WeakHashMap中的key不再被外部引用，它就有可能被GC回收。而HashMap中的key采用“强引用”方式，当HashMap中的key没有被外部引用时，只有这个key从HashMap中删除后，才能被GC回收。
map 遍历方式
对于Map的遍历，建议使用entrySet迭代器方式，在进行大量级数据时，效率会高很多。
网友评论