java基础源码

article/2025/9/19 9:32:10

HashMap

第一部分 基础入门

1. 数组的优势、劣势

内存地址连续，可以通过下标常数时间复杂度O(1)获取元素，但是增加和删除元素时间复杂度为O(n)。

数组长度大小固定，如果需要扩容，需要重新申请一个数组，将原数组元素拷贝到新数组中，不够灵活

2. 链表的优势、劣势

内存地址不连续，增加和删除元素时间复杂度为O(1)，链表没有index，查询元素只能沿着链表一个一个往下找，时间复杂度为O(n)。

链表长度大小不固定，可以动态增加和减小链表的长度，比较灵活

3. 散列表

结构：数组+链表

整合了数组的快速索引，又整合了链表可以动态扩容

4. 散列表有什么特点？

5. 什么是hash？

核心理论：Hash也称散列、哈希，对应的英文都是Hash。基本原理就是把任意长度的输入，通过Hash算法变成固定长度的输出。

这个映射的规则就是对应的Hash算法，而原始数据映射后的二进制串就是哈希值。

Hash的特点：

1.从hash值不可以反向推导出原始的数据

2.输入数据的微小变化会得到完全不同的hash值，相同的数据会得到相同的值

3.哈希算法的执行效率要高效，长的文本也能快速地计算出哈希值

4.hash算法的冲突概率要小

由于hash的原理是将输入空间的值映射成hash空间内，而hash值的空间远小于输入的空间。

根据抽屉原理，一定会存在不同的输入被映射成相同输出的情况。

抽屉原理：桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，我们会发现至少会有一个抽屉里面放不少于两个苹果。

这一现象就是我们所说的“抽屉原理”。

第二部分 HashMap原理

1. HashMap的继承体系是什么样的？

2. Node数据结构分析

    static class Node<K,V> implements Map.Entry<K,V> {final int hash;final K key;V value;Node<K,V> next;Node(int hash, K key, V value, Node<K,V> next) {this.hash = hash;this.key = key;this.value = value;this.next = next;}public final K getKey()        { return key; }public final V getValue()      { return value; }public final String toString() { return key + "=" + value; }public final int hashCode() {return Objects.hashCode(key) ^ Objects.hashCode(value);}public final V setValue(V newValue) {V oldValue = value;value = newValue;return oldValue;}public final boolean equals(Object o) {if (o == this)return true;if (o instanceof Map.Entry) {Map.Entry<?,?> e = (Map.Entry<?,?>)o;if (Objects.equals(key, e.getKey()) &&Objects.equals(value, e.getValue()))return true;}return false;}}

Node节点实现了Map中的Entry接口

节点中包含hash，key，value，next指针四个属性

3. 底层存储结构介绍

HashMap底层数据结构为 数组+链表+红黑树

链表长度超过8，并且当前结构里面元素达到64的时候，链表结构会升级为红黑树

4. put数据原理分析

5. 什么是Hash碰撞

我们常把数组中的每一个节点称为一个桶。

当向桶中添加一个键值对时，首先计算键值对中key的hash值，以此确定插入数组中的位置，但是可能存在同一hash值的元素已经被放在数组同一位置了，这种现象称为Hash碰撞

6. 什么是链化

发生Hash碰撞后，按照尾插法(jdk1.7及以前为头插法)的方式添加key-value到同一hash值的元素的后面，链表就这样形成了。当链表长度超过8(TREEIFY_THRESHOLD)时，链表就转换为红黑树。

7. jdk8为什么引入红黑树

为了解决链化问题，提高查找效率

链表如果很长，那么查找效率会很低，链表查找元素的时间复杂度为O(n)

红黑树是一棵自平衡的二叉查找树，红黑树查找元素的时间复杂度为Olog(n)

8. HashMap扩容机制

扩容是为了提高查找效率，以空间换时间

第三部分 源码分析

1.HashMap核心属性分析（threshold, loadFactory, size, modCount）

常量（共6个）

//table数组默认初始化容量大小，必须为2的幂次方
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//table数组最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认负载因子 0.75f
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;

属性（此处5个）

//哈希表中的数组
transient Node<K,V>[] table;
//当前哈希表中元素个数
transient int size;
//当前哈希表结构修改次数
transient int modCount;
//扩容阈值。当你的哈希表中的元素个数超过阈值时，触发扩容
int threshold;
//负载因子，用来计算 threshold = loadFactor * capacity
final float loadFactor;

2.构造方法分析（4个）

    public HashMap(int initialCapacity, float loadFactor) {//其实就是做了一些校验//capacity必须是大于0.最大值也就是MAXIMUM_CAPACITYif (initialCapacity < 0)throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY;//loadFactor必须大于0if (loadFactor <= 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Illegal load factor: " +loadFactor);this.loadFactor = loadFactor;this.threshold = tableSizeFor(initialCapacity);}//作用，返回一个大于等于当前值cap的一个数字，并且这个数字一定是2的次方数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;}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);}

3.HashMap put 方法分析 => putVal方法分析

    public V put(K key, V value) {return putVal(hash(key), key, value, false, true);}//作用：让key的hash值的高16位也参与路由运算static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {//tab：引用当前hashMap的散列表//p：表示当前散列表的元素//n：表示散列表元素的长度//i：表示路由寻址结果、地址，下标Node<K,V>[] tab; Node<K,V> p; int n, i;//延迟初始化逻辑，第一次调用putVal方法时，会初始化hashMap对象中的最耗费内存的散列表if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;//最简单的一种情况：寻址找到的桶位 刚好是null，这个时候，直接将当前k-v=>node 扔进去就可以了if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);else {//e：不为null的话，找到了一个与当前要插入的k-v一致的key的元素//k：表示临时的一个keyNode<K,V> e; K k;//表示桶位中的该元素，与你当前插入的元素的key完全一致，表示后续需要进行替换操作if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;//红黑树的情况，而且红黑树的头元素与我们要插入的key不一致else if (p instanceof TreeNode)e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);//链表的情况，而且链表的头元素与我们要插入的key不一致else {for (int binCount = 0; ; ++binCount) {//条件成立的话，说明迭代到最后一个元素了，也没有找到一个与你要插入的key一致的node//说明需要加入到当前链表的末尾if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);//条件成立的话，说明当前链表的长度，达到树化标准了，需要进行树化if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st//树化操作treeifyBin(tab, hash);break;}//条件成立的话，说明找到了相同key的node元素，需要进行替换操作if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}//e不等于null，条件成立说明，找到了一个与你插入元素key完全一致的数据，需要进行替换if (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}//modCount：表示散列表结构被修改的次数，替换node元素的value不计数++modCount;//插入新元素，size自增，如果自增后的值，大于扩容阈值，则触发扩容if (++size > threshold)resize();afterNodeInsertion(evict);return null;}

4.HashMap resize 扩容方法分析(核心)

//为什么需要扩容？
//为了解决哈希冲突导致的链化影响查询效率的问题，扩容会缓解该问题。
final Node<K,V>[] resize() {//oldTab：引用扩容前的哈希表Node<K,V>[] oldTab = table;//oldCap：表示扩容之前table数组的长度int oldCap = (oldTab == null) ? 0 : oldTab.length;//oldThr：表示扩容之前的扩容阈值，触发本次扩容的阈值int oldThr = threshold;//newCap：扩容之后table数组的大小//newThr：扩容之后，下次再次触发扩容的条件int newCap, newThr = 0;//条件如果成立说明 hashMap中的散列表已经初始化过了，这是一次正常扩容if (oldCap > 0) {//扩容之前的table数组大小已经达到 最大阈值后，则不扩容，且设置扩容条件为 int 最大值。if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}//oldCap左移一位实现数值翻倍，并且赋值给newCap， newCap 小于数组最大值限制 且 扩容之前的阈值 >= 16//这种情况下，则 下一次扩容的阈值 等于当前阈值翻倍else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // double threshold}//oldCap == 0,说明hashMap中的散列表是null//1.new HashMap(initCap, loadFactor);//2.new HashMap(initCap);//3.new HashMap(map); 并且这个map有数据else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;//oldCap == 0，oldThr == 0//new HashMap();else {               // zero initial threshold signifies using defaultsnewCap = DEFAULT_INITIAL_CAPACITY;//16newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//12}//newThr为零时，通过newCap和loadFactor计算出一个newThrif (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;//说明，hashMap本次扩容之前，table不为nullif (oldTab != null) {for (int j = 0; j < oldCap; ++j) {//当前node节点Node<K,V> e;//说明当前桶位中有数据，但是数据具体是 单个数据，还是链表 还是 红黑树 并不知道if ((e = oldTab[j]) != null) {//方便JVM GC时回收内存oldTab[j] = null;//第一种情况：当前桶位只有一个元素，从未发生过碰撞，这情况 直接计算出当前元素应存放在 新数组中的位置，然后//扔进去就可以了if (e.next == null)newTab[e.hash & (newCap - 1)] = e;//第二种情况：当前节点已经树化，本期先不讲，下一期讲，红黑树。QQ群：865-373-238else 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;do {next = e.next;//hash-> .... 1 1111//hash-> .... 0 1111// 0b 10000if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}else {if (hiTail == null)hiHead = e;elsehiTail.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;
}

5.HashMap 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) {//tab：引用当前hashMap的散列表//first：桶位中的头元素//e：临时node元素//n：table数组长度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) {//第一种情况：定位出来的桶位元素 即为咱们要get的数据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;
}

6.HashMap 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) {//tab：引用当前hashMap中的散列表//p：当前node元素//n：表示散列表数组长度//index：表示寻址结果Node<K,V>[] tab; Node<K,V> p; int n, index;if ((tab = table) != null && (n = tab.length) > 0 &&(p = tab[index = (n - 1) & hash]) != null) {//说明路由的桶位是有数据的，需要进行查找操作，并且删除//node：查找到的结果//e：当前Node的下一个元素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不为空的话，说明按照key查找到需要删除的数据了if (node != null && (!matchValue || (v = node.value) == value ||(value != null && value.equals(v)))) {//第一种情况：node是树节点，说明需要进行树节点移除操作if (node instanceof TreeNode)((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);//第二种情况：桶位元素即为查找结果，则将该元素的下一个元素放至桶位中else if (node == p)tab[index] = node.next;else//第三种情况：将当前元素p的下一个元素 设置成 要删除元素的 下一个元素。p.next = node.next;++modCount;--size;afterNodeRemoval(node);return node;}}return null;
}

7.HashMap replace 方法分析

    @Overridepublic boolean replace(K key, V oldValue, V newValue) {Node<K,V> e; V v;if ((e = getNode(hash(key), key)) != null &&((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {e.value = newValue;afterNodeAccess(e);return true;}return false;}@Overridepublic V replace(K key, V value) {Node<K,V> e;if ((e = getNode(hash(key), key)) != null) {V oldValue = e.value;e.value = value;afterNodeAccess(e);return oldValue;}return null;}

红黑树

红黑树原理

红黑树的性质：

红黑树的性质

红黑树示例图

性质1：每个节点要么是黑色，要么是红色。

性质2：根节点是黑色。

性质3：每个叶子节点（NIL）是黑色。

性质4：每个红色节点的两个子节点一定都是黑色。

不能有两个红色节点相连。

性质5：任意一节点到每个叶子节点的路径都包含数量相同的黑结点。俗称：黑高！

从性质5又可以推出：

性质5.1：如果一个节点存在黑子节点，那么该结点肯定有两个子节点

红黑树并不是一个完美平衡二叉查找树，从图上可以看到，根结点P的左子树显然比右子树高，

但左子树和右子树的黑结点的层数是相等的，也即任意一个结点到到每个叶子结点的路径都包含数量相同的黑结点(性质5)。

所以我们叫红黑树这种平衡为黑色完美平衡。

红黑树的性质讲完了，只要这棵树满足以上性质，这棵树就是趋近与平衡状态的，

不要问为什么，发明红黑树的科学家就是这么牛逼！

前面讲到红黑树能自平衡，它靠的是什么？三种操作：左旋、右旋和变色。

1.变色：结点的颜色由红变黑或由黑变红。

2.左旋：以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。

3.右旋：以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变

左旋图示

0

右旋图示

0

红黑树查找：

0

红黑树插入：

插入操作包括两部分工作：

1.查找插入的位置

2.插入后自平衡

注意：插入节点，必须为红色，理由很简单，红色在父节点（如果存在）为黑色节点时，红黑树的黑色平衡没被破坏，不需要做自平衡操作。

但如果插入结点是黑色，那么插入位置所在的子树黑色结点总是多1，必须做自平衡。

在开始每个情景的讲解前，我们还是先来约定下:

0

红黑树插入节点情景分析

情景1：红黑树为空树

最简单的一种情景，直接把插入结点作为根结点就行

注意：根据红黑树性质2：根节点是黑色。还需要把插入结点设为黑色。

情景2：插入结点的Key已存在

处理：更新当前节点的值，为插入节点的值

0

情景3：插入结点的父结点为黑结点

由于插入的结点是红色的，当插入结点的黑色时，并不会影响红黑树的平衡，直接插入即可，无需做自平衡。

0

情景4：插入节点的父节点为红色

再次回想下红黑树的性质2：根结点是黑色。如果插入节点的父结点为红结点，那么该父结点不可能为根结点，所以插入结点总是存在祖父结点。

这一点很关键，因为后续的旋转操作肯定需要祖父结点的参与。

0

插入情景4.1：叔叔结点存在并且为红结点

依据红黑树性质4可知，红色节点不能相连 ==> 祖父结点肯定为黑结点；

因为不可以同时存在两个相连的红结点。那么此时该插入子树的红黑层数的情况是：黑红红。显然最简单的处理方式是把其改为：红黑红

处理：

1.将P和U节点改为黑色

2.将PP改为红色

3.将PP设置为当前节点，进行后续处理

0

可以看到，我们把PP结点设为红色了，如果PP的父结点是黑色，那么无需再做任何处理；

但如果PP的父结点是红色，则违反红黑树性质了。所以需要将PP设置为当前节点，继续做插入操作自平衡处理，直到平衡为止。

插入情景4.2：叔叔结点不存在或为黑结点，并且插入结点的父亲结点是祖父结点的左子结点

注意：单纯从插入前来看，叔叔节点非红即空（NIL节点），否则的话破坏了红黑树性质5，此路径会比其它路径多一个黑色节点。

0

插入情景4.2.1：新插入节点，为其父节点的左子节点（LL红色情况）

0

处理：

1.变颜色：将P设置为黑色，将PP设置为红色

2.对PP节点进行右旋

0

插入情景4.2.2：新插入节点，为其父节点的右子节点（LR红色情况）

0

处理：

1.对P进行左旋

2.将P设置为当前节点，得到LL红色情况

3.按照LL红色情况处理（1.变颜色 2.右旋PP）

0

插入情景4.3：叔叔结点不存在或为黑结点，并且插入结点的父亲结点是祖父结点的右子结点

该情景对应情景4.2，只是方向反转，直接看图。

0

插入情景4.3.1：新插入节点，为其父节点的右子节点（RR红色情况）

0

处理：

1.变颜色：将P设置为黑色，将PP设置为红色

2.对PP节点进行左旋

0

插入情景4.3.2：新插入节点，为其父节点的左子节点（RL红色情况）

0

处理：

1.对P进行右旋

2.将P设置为当前节点，得到RR红色情况

3.按照RR红色情况处理（1.变颜色 2.左旋PP）

0

hashMap中红黑树源码

平衡插入（balanceInsertion）

主要有四种情况

情况1，如果新节点X的父节点XP为null，则不需要调整
情况2，如果父节点为黑色，或者祖父节点XPP为空，则不需要调整
情况3，父节点XP为祖父节点XPP的左节点（父节点XP为红色）
情况4，父节点XP为祖父节点XPP的右节点（父节点XP为红色）
//进行平衡的调整，X为新节点
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;;) {//情况1，如果新节点X的父节点XP为null，则不需要调整if ((xp = x.parent) == null) {x.red = false;return x;}//情况2，如果父节点为黑色，或者祖父节点XPP为空，则不需要调整else if (!xp.red || (xpp = xp.parent) == null)return root;//情况3，父节点XP为祖父节点XPP的左节点（父节点XP为红色）if (xp == (xppl = xpp.left)) {//右叔叔节点不为null，且右叔叔节点为红色if ((xppr = xpp.right) != null && xppr.red) {xppr.red = false;xp.red = false;xpp.red = true;x = xpp;}//右叔叔节点为null，或右叔叔节点为黑色，右旋else {//如果新节点X为父节点的右节点，需要先进行左旋if (x == xp.right) {root = rotateLeft(root, x = xp);xpp = (xp = x.parent) == null ? null : xp.parent;}if (xp != null) {xp.red = false;if (xpp != null) {xpp.red = true;root = rotateRight(root, xpp);}}}}//情况4，父节点XP为祖父节点XPP的右节点（父节点XP为红色）else {//左叔叔节点不为null，且左叔叔节点为红色if (xppl != null && xppl.red) {xppl.red = false;xp.red = false;xpp.red = true;x = xpp;}//左叔叔节点为null，或者左叔叔节点为黑色，左旋else {//如果新节点X为父节点的左节点，需要先进行右旋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);}}}}}
}

 左旋

//P为旋转的中心节点
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,TreeNode<K,V> p) {TreeNode<K,V> r, pp, rl;//P不为空，且P的右节点R不为空，才能进行左旋if (p != null && (r = p.right) != null) {if ((rl = p.right = r.left) != null)rl.parent = p;if ((pp = r.parent = p.parent) == null)(root = r).red = false;else if (pp.left == p)pp.left = r;elsepp.right = r;r.left = p;p.parent = r;}return root;
}

右旋

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)(root = l).red = false;else if (pp.right == p)pp.right = l;elsepp.left = l;l.right = p;p.parent = l;}return root;
}

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 orderTreeNode<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;elseloTail.next = e;loTail = e;++lc;}else {if ((e.prev = hiTail) == null)hiHead = e;elsehiTail.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);}}
}

put

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;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;elsexp.right = x;xp.next = x;x.parent = x.prev = xp;if (xpn != null)((TreeNode<K,V>)xpn).prev = x;moveRootToFront(tab, balanceInsertion(root, x));return null;}}
}
final void treeify(Node<K,V>[] tab) {TreeNode<K,V> root = null;for (TreeNode<K,V> x = this, next; x != null; x = next) {next = (TreeNode<K,V>)x.next;x.left = x.right = null;if (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;;) {int dir, ph;K pk = p.key;if ((ph = p.hash) > h)dir = -1;else if (ph < h)dir = 1;else if ((kc == null &&(kc = comparableClassFor(k)) == 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) {x.parent = xp;if (dir <= 0)xp.left = x;elsexp.right = x;root = balanceInsertion(root, x);break;}}}}moveRootToFront(tab, root);
}

FutureTask

实现RunnableFuture接口，通过submit（）方法去提交到线程池中的任务，在被执行之前，这些Runnable或者Callable都会被封装成FutureTask提交到线程池里面，线程池中的线程会去执行你所提交的任务

FutureTask中的属性

//--------表示当前task状态---------
private volatile int state;
//当前任务尚未执行
private static final int NEW          = 0;
//当前任务正在结束，还没有完全结束，一种临界状态
private static final int COMPLETING   = 1;
//当前任务正常结束
private static final int NORMAL       = 2;
//当前任务执行过程中，发生了异常。内部封装的callable.run()向上抛出异常
private static final int EXCEPTIONAL  = 3;
//当前任务被取消
private static final int CANCELLED    = 4;
//当前任务中断中
private static final int INTERRUPTING = 5;
//当前任务已中断
private static final int INTERRUPTED  = 6;//submit(runnable/callable)  runnable 使用 装饰者模式 伪装成 callable了
private Callable<V> callable;
//正常情况下：任务正常执行结束，outcome保存执行结果。保存callable的返回值
//非正常情况：callable向上抛出异常，outcome保存异常
private Object outcome;
//当前任务被线程执行期间，保存当前执行任务的线程对象引用
private volatile Thread runner;
//因为会有很多线程去get当前线程的结果。所以这里使用了一种数据结构 stack 头插 头取 一个队列
private volatile WaitNode waiters;
static final class WaitNode {volatile Thread thread;volatile FutureTask.WaitNode next;WaitNode() { thread = Thread.currentThread(); }
}// Unsafe mechanicsprivate static final sun.misc.Unsafe UNSAFE;private static final long stateOffset;private static final long runnerOffset;private static final long waitersOffset;static {try {UNSAFE = sun.misc.Unsafe.getUnsafe();Class<?> k = FutureTask.class;stateOffset = UNSAFE.objectFieldOffset(k.getDeclaredField("state"));runnerOffset = UNSAFE.objectFieldOffset(k.getDeclaredField("runner"));waitersOffset = UNSAFE.objectFieldOffset(k.getDeclaredField("waiters"));} catch (Exception e) {throw new Error(e);}}

FutureTask中的构造器

共有两个构造器，分别是传入callable和runnable，如果传入runnable，会将其转换成callable

public class FutureTask<V> implements RunnableFuture<V> {//传入callablepublic FutureTask(Callable<V> callable) {if (callable == null)throw new NullPointerException();//callable就是程序员自己实现的业务类this.callable = callable;//设置当前任务状态为NEWthis.state = NEW;}//传入Runnable，将其转换成callable，装饰者模式public FutureTask(Runnable runnable, V result) {//使用装饰者模式将runnable转换成了callable接口，外部线程通过get获取//当前任务执行结果时，结果可能为null，也可能为传进来的值this.callable = Executors.callable(runnable, result);//设置当前任务状态为NEWthis.state = NEW;}
}public class Executors {public static <T> Callable<T> callable(Runnable task, T result) {if (task == null)throw new NullPointerException();return new Executors.RunnableAdapter<T>(task, result);}static final class RunnableAdapter<T> implements Callable<T> {final Runnable task;final T result;RunnableAdapter(Runnable task, T result) {this.task = task;this.result = result;}public T call() {task.run();return result;}}
}
FutureTask中的run方法，任务执行的入口
public class FutureTask<V> implements RunnableFuture<V> {//任务执行入口public void run() {//条件一：state != NEW 条件成立，说明当前task已经被执行过了 或者 被cancel了，总之非NEW状态的任务，线程就不处理了//条件二：!UNSAFE.compareAndSwapObject(this, runnerOffset, null, Thread.currentThread())//       条件成立，CAS失败，当前任务被其他线程抢占了if (state != NEW ||!UNSAFE.compareAndSwapObject(this, runnerOffset,null, Thread.currentThread()))return;//执行到这里，当前task一定是NEW状态，而且当前线程也抢占task成功try {//callable 就是程序员自己封装逻辑的callable 或者 装饰后的runnableCallable<V> c = callable;//条件一：c != null 防止空指针异常//条件二：state == NEW 防止外部线程 cancel掉当前任务if (c != null && state == NEW) {//结果引用V result;//true 表示callable.call 代码块执行成功 未抛出异常//false 表示callable.call 代码块执行失败，抛出异常boolean ran;try {//调用程序员自己实现的callable 或者 装饰后的runnableresult = c.call();ran = true;} catch (Throwable ex) {result = null;ran = false;setException(ex);}if (ran)//说明当前c.call正常执行结束//set就是设置结果到outcomeset(result);}} finally {runner = null;int s = state;if (s >= INTERRUPTING)handlePossibleCancellationInterrupt(s);}}//正常情况下设置结果到outcomeprotected void set(V v) {//使用CAS方式，设置当前任务状态为 完成中...//有没有可能失败？外部线程等不及了，直接在set执行CAS之前，将task取消了。很小的概率if (UNSAFE.compareAndSwapInt(this, stateOffset, NEW, COMPLETING)) {outcome = v;//将结果赋值给 outcome之后，马上会将当前线程状态修改为 NORMAL 正常结束状态。UNSAFE.putOrderedInt(this, stateOffset, NORMAL);finishCompletion();}}//异常情况下设置结果到outcomeprotected void setException(Throwable t) {//使用CAS方式，设置当前任务状态为 完成中...//有没有可能失败？外部线程等不及了，直接在set执行CAS之前，将task取消了。很小的概率if (UNSAFE.compareAndSwapInt(this, stateOffset, NEW, COMPLETING)) {//引用的是 callable 向上层抛出来的异常outcome = t;//将结果赋值给 outcome之后，马上会将当前线程状态修改为 EXCEPTIONAL 异常结束状态。UNSAFE.putOrderedInt(this, stateOffset, EXCEPTIONAL);finishCompletion();}}
}
FutureTask中的get方法
public class FutureTask<V> implements RunnableFuture<V> {//场景：多个线程等待当前任务执行完成后的结果public V get() throws InterruptedException, ExecutionException {//获取当前任务状态int s = state;//条件成立：未执行、正在执行、正在完成。调用get的外部线程会被阻塞在get方法上if (s <= COMPLETING)s = awaitDone(false, 0L);return report(s);}private int awaitDone(boolean timed, long nanos)throws InterruptedException {//0 不带超时final long deadline = timed ? System.nanoTime() + nanos : 0L;//引用当前线程 封装成WaitNode对象WaitNode q = null;//表示当前线程waitNode对象 有没有 入队/出队boolean queued = false;//自旋for (;;) {//条件成立：说明当前线程唤醒 是被其他线程使用中断这种方式唤醒的。//interrupted()：返回true，后会将Thread的中断标记重置回falseif (Thread.interrupted()) {//当前线程node出队removeWaiter(q);//get方法抛出中断异常throw new InterruptedException();}//假设当前线程是被其他线程 使用unpark(thread)唤醒的话。会正常自旋，走下面逻辑。//获取当前任务最新状态int s = state;//条件成立：说明当前任务 已经有结果了..可能是好 也可能是坏..if (s > COMPLETING) {//条件成立：说明已经为当前线程创建过node了。此时需要将node.thread=null helpGCif (q != null)q.thread = null;//直接返回当前状态return s;}//条件成立：说明当前任务已经接近完成状态...这里让当前线程再释放CPU，进行下一次抢占CPU。else if (s == COMPLETING) // cannot time out yetThread.yield();//条件成立：第一次自旋。当前线程还未创建WaitNode对象。此时为当前线程创建WaitNode对象else if (q == null)q = new WaitNode();//条件成立：第二次自旋，当前线程已经创建WaitNode对象了，但是node对象还未入队else if (!queued)//q.next = waiters 当前线程node节点next指向原队列头结点 waiters一直指向队列的头//CAS方式设置waiters引用指向当前线程node，成功的话， queued=true，否则，可能有其他线程先你一步入队了。queued = UNSAFE.compareAndSwapObject(this, waitersOffset,q.next = waiters, q);else if (timed) {nanos = deadline - System.nanoTime();if (nanos <= 0L) {removeWaiter(q);return state;}LockSupport.parkNanos(this, nanos);}else//当前get操作的线程会被park了。线程状态会变为WAITING状态，相当于休眠了..//除非有其他线程将你唤醒 或者 将当前线程中断LockSupport.park(this);}}private void removeWaiter(WaitNode node) {if (node != null) {node.thread = null;retry:for (;;) {          // restart on removeWaiter racefor (WaitNode pred = null, q = waiters, s; q != null; q = s) {s = q.next;if (q.thread != null)pred = q;else if (pred != null) {pred.next = s;if (pred.thread == null) // check for racecontinue retry;}else if (!UNSAFE.compareAndSwapObject(this, waitersOffset,q, s))continue retry;}break;}}}
}

 


http://chatgpt.dhexx.cn/article/0uJ5D2bM.shtml

相关文章

总结：JDK源码

总结：JDK源码

一、JDK源码下载 地址&#xff1a;http://jdk.java.net/java-se-ri/8 选择版本&#xff0c;下载 RI Source Code 代码路径在:/openjdk/jdk/src/windows/native 对应着java中的类名 如&#xff1a;jdk 中SocketOutputStream中的write0的native方法 /openjdk/jdk/src/windows…
阅读更多...
JAVA JDK 源码学习

JAVA JDK 源码学习

JAVA JDK 源码学习 &#xff0c;以1.8为例&#xff0c;按照下面图片顺序依次学习&#xff1a; applet ,awt,beans,io,lang,math,net,nio,rmi,security,sql,text,time,util 第一课&#xff0c;广泛认知它们 1 applet Java applet 为使用Java语言编写的一些程序&#xff0c;可以…
阅读更多...
JDK源码学习

JDK源码学习

Java集合框架之Collection集合 http://www.leocook.org/category/#java Java的集合框架分两大系Collection系和Map系&#xff0c;之所以要分开是因为Collection内存储的是线性集合&#xff0c;而 Map的元素是以键值对&#xff08;Key-Value&#xff09;的形式存的。其实Map和…
阅读更多...
如何阅读Java源码？

如何阅读Java源码？

阅读Java源码的前提条件&#xff1a; 1、技术基础 在阅读源码之前&#xff0c;我们要有一定程度的技术基础的支持。 假如你从来都没有学过Java&#xff0c;也没有其它编程语言的基础&#xff0c;上来就啃《Core Java》&#xff0c;那样是很难有收获的&#xff0c;尤其是《深入J…
阅读更多...
JDK源码学习-基础

JDK源码学习-基础

JDK源码学习 目录 基础 1. 安装 1.1 下载JDK 1.2 配置环境变量 1.3 验证 2. 简单的程序 2.1 编写代码 2.2 编译文件 2.3 执行类 3. java基本类型 基础 1. 安装 1.1 下载JDK Java下载地址&#xff1a;https://www.oracle.com/technetwork/java/javase/downloads/in…
阅读更多...
bug修复---同时触发mousedown事件和touchstart事件

bug修复---同时触发mousedown事件和touchstart事件

这两天遇到一个bug&#xff0c;每次点击下方键盘时&#xff0c;点击一次数字&#xff0c;文本框中会出现两次重复值&#xff0c;如下所示&#xff1a; 而且console中还有以下报错信息&#xff1a; 查看项目代码&#xff0c;代码如下&#xff1a; <ul><liv-for"…
阅读更多...
Vue下 touchstart touchend 事件无效失效解决办法

Vue下 touchstart touchend 事件无效失效解决办法

Vue下 touchstart touchend 事件无效失效解决办法 <van-button:disabled"isLoading"plaintype"info"touchstart.native.prevent"touchstart"touchend.native.prevent"touchend"style"width:40%;height: 40px;"round>对…
阅读更多...
触屏touchstart 与 click

触屏touchstart 与 click

设计效果&#xff1a;当手指点击或触摸红框线menuList之外的部分时&#xff0c;弹框menuList消失。 问题&#xff1a;在优化触屏版的时候发现如图问题&#xff0c;当menuList弹出&#xff0c;手指触摸屏幕向下滑动时&#xff0c;menuList弹框不消失&#xff0c;只有手指点击men…
阅读更多...
移动端事件touchstart touchmove touchend 动画事件 过渡事件

移动端事件touchstart touchmove touchend 动画事件 过渡事件

在移动端新增了touch事件&#xff0c;因为手指的行为叫做“触摸”&#xff0c; 鼠标的行为叫做“点击” 但是它仍然支持点击事件&#xff0c;有300ms的延迟&#xff0c;检测是否双击 移动端的三个事件 touchstart&#xff1a;触摸开始 绑定方式&#xff1a; dom.addEve…
阅读更多...
微信小程序、uniapp使用touchstart和touchmove左右滑动删除。以及解决上下抖动问题。

微信小程序、uniapp使用touchstart和touchmove左右滑动删除。以及解决上下抖动问题。

展示效果图直接上代码 <viewv-for"(item, index) in arr":key"item.id"touchstart"touchstart($event)"touchmove"touchmove(index, $event)":class"[touch-item, item.isTouchMove ? touch-move-active : ]" ><…
阅读更多...
html按键使用touch,HTML touchstart事件用法及代码示例

html按键使用touch,HTML touchstart事件用法及代码示例

每当用户触摸HTML元素时&#xff0c;就会使用touchstart事件执行脚本。触摸特定元素时&#xff0c;如果touchstart事件与之关联&#xff0c;则可以使用它触发javascript函数。 注意&#xff1a;touchstart事件仅在触摸屏设备上起作用。 用法: object.ontouchstart myScript; 以…
阅读更多...
JavaScript touch 事件 touchstart touchmove touchend

JavaScript touch 事件 touchstart touchmove touchend

JavaScript touch 事件 touchstart touchmove touchend MDN 官方文档&#xff1a; https://developer.mozilla.org/en-US/docs/Web/API/Touch_events 一、touch 事件有哪些 页面中的 touch 事件一般在移动端使用&#xff0c;pc 端是没有效果的。 touch 相关的事件有四个 touc…
阅读更多...
触摸事件(touchstart、touchmove和touchend)

触摸事件(touchstart、touchmove和touchend)

触摸事件(touch)会在用户手指放在屏幕上面的时候、在屏幕上滑动的时候或者是从屏幕上移开的时候出发。下面具体说明 touchstart事件&#xff1a;当手指触摸屏幕时候触发&#xff0c;即使已经有一个手指放在屏幕上也会触发。 touchmove事件&#xff1a;当手指在屏幕上滑动的时候…
阅读更多...
Vue 绑定使用 touchstart touchmove touchend

Vue 绑定使用 touchstart touchmove touchend

今天要做一个页面div长按后触发事件&#xff0c;简单学习后实现如下&#xff1a; 先看代码&#xff1a; <template><div><div class"test" touchstart"gtouchstart()" touchmove"gtouchmove()" touchend"gtouchend()"…
阅读更多...
H5移动端 利用touchstart 达到长按事件

H5移动端 利用touchstart 达到长按事件

一开始的没加.native ,结果长按事件不会触发, 原因是: 给vue组件绑定事件时候&#xff0c;必须加上native &#xff0c;否则会认为监听的是来自Item组件自定义的事件等同于在子组件中: 子组件内部处理click事件然后向外发送click事件: semit"dlick”.fn) //长按事件&am…
阅读更多...
javaScript-touch事件详解(touchstart、touchmove和touchend)-滑动事件案例

javaScript-touch事件详解(touchstart、touchmove和touchend)-滑动事件案例

HTML5中新添加了很多事件&#xff0c;但是由于他们的兼容问题不是很理想&#xff0c;应用实战性不是太强&#xff0c;所以在这里基本省略&#xff0c;咱们只分享应用广泛兼容不错的事件&#xff0c;日后随着兼容情况提升以后再陆续添加分享。今天为大家介绍的事件主要是触摸事件…
阅读更多...
「移动端」touch事件，touchEvent对象

「移动端」touch事件，touchEvent对象

随着智能手机普及&#xff0c;有越来越多的手机网页和网页版游戏&#xff0c;手机触摸、移动、旋转等等&#xff0c;多种操作。一般电脑的人机交互靠的是鼠标&#xff0c;而手机用的就是触摸。区别有&#xff1a; PC 端一个电脑只能有一个鼠标&#xff0c;而移动端有多点触摸。…
阅读更多...
移动端开发touchstart，touchmove，touchend事件详解使用

移动端开发touchstart，touchmove，touchend事件详解使用

页面使用到了触摸事件"touchstart"&#xff0c;“touchmove”&#xff0c;“touchend”。需求&#xff1a;当你手指接触到屏幕并向左滑动时&#xff0c;被滑动的服务商信息开始向左滑动同时出现"编辑"和"停用"操作按钮。若继续用手指向右滑动&am…
阅读更多...
C++智能指针的实现与使用(详解)

C++智能指针的实现与使用(详解)

C智能指针的实现与使用(详解) 智能指针介绍 缘起 C指针的实际问题 分配内存忘记释放&#xff0c;导致内存泄漏有指针引用时释放内存&#xff0c;导致其它指针非法访问异常一些对象的声明周期难以明确 办法 首先重载运算符*、->、[]、使得一个类具有指针的操作 其次&a…
阅读更多...
详谈智能指针

详谈智能指针

一、什么是智能指针 在讲智能指针之前我们必须先知道什么是智能指针&#xff0c;智能指针是一个类&#xff0c;是对普通指针的一个封装使得智能指针对象具有普通指针类型一样的操作。 智能指针是存储指向动态分配&#xff08;堆&#xff09;对象指针的类&#xff0c;用于生…
阅读更多...
推荐文章

Copyright @ 2022~2023