HashMap理解 {#HashMap理解}

1.说说你对hash算法的理解 {#1-说说你对hash算法的理解}

其实 hash 算法的本质上是对输入任意长度的输入进行编码，然后隐射成固定长度的输出。

追问：hash算法任意长度的输入转化为了固定长度的输出，会不会有问题呢？ {#追问：hash算法任意长度的输入-转化为了-固定长度的输出，会不会有问题呢？}

在程序中碰到 value 在经过计算后得到的 hash 值和之前的一样，这个其实就是 hash 冲突。

追问：hash冲突能避免么？ {#追问：hash冲突能避免么？}

避免理论上是不能避免的，比如我列举一个场景，就是我现在有 10 个苹果，但是抽屉只有 9 个，我要想全部放进去，那么肯定是有一个抽屉会多放的。所以只能尽量的避免，但是不可能完全避免的。

2.你认为好的hash算法，应该考虑点有哪些呢？ {#2-你认为好的hash算法，应该考虑点有哪些呢？}

第一点：这个hash算法它一定效率得高，要做到长文本也能高效计算出hash值嘛。

第二点：不能逆推原文

第三点：hash 后，尽可能的使其排列比较分散，尽可能的减少冲突

3.HashMap中存储数据的结构是什么样的呢？ {#3-HashMap中存储数据的结构是什么样的呢？}

java8 中，数组 + 链表/红黑树

然后每一个数据单元其实就是一个 Node，然后 Node结构中有key字段、有value字段、还有next字段、还有hash字段。

然后 next 字段其实就是为了处理 hash 冲突而建立的，然后发生了冲突，那么当前节点的 next 指针就会指向发生冲突的那个节点，然后连接上来。

4.创建HashMap时，不指定散列表数组长度，初始长度是多少呢？ {#4-创建HashMap时，不指定散列表数组长度，初始长度是多少呢？}

如果没有指定情况下，hashmap 的默认长度为 16

追问：散列表是new HashMap() 时创建的么？ {#追问：散列表是new-HashMap-时创建的么？}

不是，创建散列表的时候，其实她是懒加载的，只有当第一次 put 的时候才会创建。

5.默认负载因子是多少呢，并且这个负载因子有什么作用？ {#5-默认负载因子是多少呢，并且这个负载因子有什么作用？}

默认的负载因子是 0.75，那么也就是说是 75%。

作用其实就是用来扩容用的，比如我们当前的长度为 16，那么达到需要扩容的阈值了，然后就是扩容 16*0.75 = 12，那么她就是以 12 为单位进行扩容。

6.链表转化为红黑树，需要达到什么条件呢？ {#6-链表转化为红黑树，需要达到什么条件呢？}

两个指标：1. Node 节点长度大于 8，2. 散列表长度大于 64

如果 node 长度大于 8，此时散列表的长度是大于 64 的，那么就会先扩容散列表然后取消本次链表翻转的，这是发生 resize 散列表扩容代替链表翻转红黑树升级。

7.Node对象内部的hash字段，这个hash值是key对象的hashcode()返回值么？怎么得到的呢？ {#7-Node对象内部的hash字段，这个hash值是key对象的hashcode-返回值么？怎么得到的呢？}

不是，这个 hash 值是 key.hashCode( )得到的，其中它的操作是 高 16 位 ^ 低 16 位得到的新值。（异或）

追问：hash字段为什么采用高低位异或？ {#追问：hash字段为什么采用高低位异或？}

这个主要还是得考虑 hash 寻址算法的缘故，首先我们都知道，散列表的长度尽可能的都是 2 的 n 次方，比如 16，32，64 等，然后寻址算法是 hash & （table.length - 1），我们知道table.length 是 2^n，那么length转化为二进制后，一定是（1）是高位，然后低位全部是（0），这种数字 -1 也比较特殊，比如 16-1 就是 1111，任何（数）与这种高位全部为0，低位都是一串1的数，按位与之后它得到的这个数值一定是>=0 且<=这个二进制数，然后带上下标为 0 的 slow 则刚刚好为 2 的 n 次方。

8.🌈HashMap put 写数据的具体流程，尽可能的详细点！ {#8-🌈HashMap-put-写数据的具体流程，尽可能的详细点！}

写数据一共分为四种情况：

slow 为空（没有初始数据）
slow 不为空，其实就是当 slow 为一个节点的时候（没有链化）
slow 已经链化
slow 已经树化

然后对于第一种情况：那就是直接 put 进来的值封装成一个 node 节点放入 value 即可。
对于第二种情况：只有一个节点，那还是先封装，如果当前节点的 key 是已经存在的，那么则直接替换 value 即可，否者就是冲突，那么直接使用尾插法。
如果是已经链化了，那么其实跟第二种处理很相识，首先就是遍历迭代查找 node，如果有则替换，没有则插入到尾部，此时还是要判断是否达到树化阈值。

9.红黑树的写入操作，是怎么找到父节点的，找父节点流程？ {#9-红黑树的写入操作，是怎么找到父节点的，找父节点流程？}

红黑树的写入操作，对于红黑树来说（首先得说明它的结构，TreeNode：value、left、right、parent、red），然后红黑树是满足二叉排序树的所有特性的，所以找到父节点其实是和二叉排序树是完全一致的，

对于数据来说：左节点小于当前节点，右节点大于当前节点，然后每次搜索一层就可以过滤掉一半的数据。

插入：如果探测节点一直向下查找没有找到其值，那么此时的位置其实就是可插入的位置（然后就是插入父节点的左边或者右边即可），然后根据插入节点的值可能会打破节点的平衡，那么此时则需要一个红黑树的平衡算法。/ 如果探测节点发现有 TreeNode#key 一致的节点，那么直接替换其 value 即可。

10.🌈红黑树的原则有哪些呢(性质)？ {#10-🌈红黑树的原则有哪些呢-性质-？}

1.每个结点要么是红的要么是黑的。

2.根结点是黑的。

3.每个叶结点（叶结点即指树尾端NIL指针或NULL结点）都是黑的。

4.如果一个结点是红的，那么它的两个儿子都是黑的。

5.对于任意结点而言，其到叶结点树尾端NIL指针的每条路径都包含 相同数目的 黑结点 。

正是红黑树的这5条性质，使一棵n个结点的红黑树始终保持了logn的高度，从而也就解释了上面所说的"红黑树的查找、插入、删除的时间复杂度最坏为O(log n)"这一结论成立的原因。

11.JDK8 HashMap 为什么引入红黑树？解决什么问题？ {#11-JDK8-HashMap-为什么引入红黑树？解决什么问题？}

引入红黑树其实就是为了解决上面的第三点，它如果过长的节点就是会发生 链化问题 ，我们知道链表的查询，它是需要一个一个去遍历的，它不像数组一样它是连续的。

然后至于为什么阈值是 8，因为当链表中的元素数量达到8时，使用红黑树进行查找的效率会超过链表。具体来说，当链表中的元素数量为8时，平均查找长度为(1+8)/2=4。而红黑树的平均查找长度为log(8)，大约是3。因此，将链表转换为红黑树可以提高查找效率。

12.HashMap 什么情况下会触发扩容呢？ {#12-HashMap-什么情况下会触发扩容呢？}

扩容肯定是在除非写入操作的时候，然后在 hashmap 的内部有一个计算数据量的字段，它达到扩容阈值就会触发扩容

|-----------------|----------------------------------------------------------------------------------------------| | 1 2 3 4 | /** * The number of key-value mappings contained in this map. */ transient int size; |

追问：触发扩容后，会扩容多大呢？算法是什么？ {#追问：触发扩容后，会扩容多大呢？算法是什么？}

扩容其实是有一个规则的（它肯定是要满足 2 的次方），其次它每次是根据上一次的 tableSize 位移运算得到的，左移一位：例如 16<<1 => 32

追问：为什么采用位移运算，不是直接 * 2？ {#追问：为什么采用位移运算，不是直接-2？}

其实在计算机的底层是不支持乘除操作，最后在指令层都会转换为加分运算的，我们直接使用位移操作，这样对 cpu 更加友好，其次更简洁高效。

13.🌈HashMap扩容后，老表的数据怎么迁移到扩容后的表的呢？ {#13-🌈HashMap扩容后，老表的数据怎么迁移到扩容后的表的呢？}

对于迁移操作，其实就是桶位推进迁移的操作，主要还是得看当前的状态吧（四种）

第一种是 slot 存储的是 null，第二种是存储的是单个的 node 没有链化，第三种是 node 节点已经链化了，第四种是已经形成了红黑树。

对于第一种情况不需要处理，我们只需要处理后面的三种情况了。

对于单个节点操作，当发现 node 节点的 next 指针为 null，那么直接迁移即可，在新表通过 tableSize 计算位置即可，

对于已经链化的操作（已经发送过冲突）：此时需要把当前保存的链表拆分成两个链表，分别是 高位链 和 低位链 （此处需要重点研究）

低位链（Low-order chain） ：

当HashMap扩容时，会创建一个新的哈希表，其容量是原哈希表容量的两倍。
在这个过程中，每个键值对会根据新的哈希表容量重新计算其哈希值。
如果某个键值对在新哈希表中的位置与旧哈希表中的位置相同（即新哈希值与旧哈希值在新的容量下最低的有效位是相同的），那么这个键值对会被放到"低位链"中。
换句话说，低位链包含了那些不需要移动或者只需要移动到"当前索引+旧容量"位置的元素。

高位链（High-order chain） ：

与低位链相对，高位链包含了那些在新哈希表中位置与旧哈希表位置不同的键值对。
这些元素在新哈希表中的位置是旧索引位置加上旧哈希表的容量。
高位链的元素需要被重新放置到新的位置上。

对于低位链来说：它的高位是 0，那么在迁移到新表的时候，这个 slot 下标和老的是一样的。

对于高位链来说：它的高位是 1，所以说在迁移到新表之后，其实它是要在进行一次运算的（其中是老表的位置+老表的 size 长度）比如是老表的 size 是 16，此时他的位置是 8，那么扩容后的结果则是 24 的桶位置。

14.HashMap扩容后，迁移数据发现该slot是颗红黑树，怎么处理呢？ {#14-HashMap扩容后，迁移数据发现该slot是颗红黑树，怎么处理呢？}

其实红黑树的结构它依然是保留了 next 字段，也就是说，其实它内部还是维护着一个链表（新增删除都需要进行维护），只不过查询的时候是使用的红黑树进行检索。为什么还维护着一个链表呢，因为在拆分链表转换为红黑树的时候需要使用到这个结构，它也是跟高位和低位进行操作的。

唯一不同的就是，如果你的 TreeNode 的长度是小于 6 的时候，它直接转换为链表存储在新的表中即可，如果拆分出来还是大于 6 的则需要转换为红黑树（重建红黑树）

扩展 {#扩展}

HashMap 的 get()流程 {#HashMap-的-get-流程}

源码

|------------------------------------------------------------------------|-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------| | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | 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) { 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 ) { 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 ; } |

流程图

①第一步和put方法一样，获取key的hash值；

②判断数组table是否为空；

③如果数组为空，直接返回null，结束查找；如果数组不为空，则将hash值与数组长度减1做&运算确定数组位置;

④取出该位置的节点判断是否为空，如果为空，直接返回null，结束查找；

⑤判断当前节点的hash、key与待查找的hash、key是否相等，如果相等返回该节点，查找结束；如果不相同则判断当前节点的后继节点是否存在，不存在则直接返回空，结束查找；

⑥若存在则需判断节点类型属于链表节点还是红黑树节点；

⑦如果是红黑树节点则调用红黑树查找方法；

⑧如果是链表节点，则整条遍历链表，找到key和hash值相同的节点则返回，没有找到则返回空。

AQS {#AQS}

AQS 类定义以及 Node 节点数据结构说明 {#AQS-类定义以及-Node-节点数据结构说明}

众所周知 AQS 是AbstractQueuedSynchronizer 的简称

然后他有两个重要的属性

state: volatile int state

它代表着一个同步状态，他在不同的实现子类中有不同的实现

例如在ReentrantLock 中 state = 1 代表当前共享资源已经被加锁，> 1 则代表被多次加锁

然后对于 state 的操作，他有三个方法

|---------------|------------------------------------------------------------------------------------------------| | 1 2 3 | final int getState () ; final void setState () ; final boolean compareAndSetState () ; |

其实compareAndSetState()我们可以看做 CAS

CAS：全称是 C ompare A nd S wap，是一种用于在多线程环境下实现同步功能的机制。CAS操作包含三个操作数： 内存位置 、 预期数值 和新值 .

CAS的实现逻辑是将内存位置处的数值与预期数值想比较，若相等，则将内存位置处的值替换为新值。若不相等，则不做任何操作。

Node 节点

其中 Node 节点结构如下：（双向链表同步队列）

| int | waitStatus | |--------|------------| | Node | prev | | Node | next | | Thread | thread |

对于 Node 节点，做如下解释：当一个线程拿不到锁的时候，他就会被添加到 Node 节点的双向链表中

+------+ prev +-----+ +-----+

head | | <---- | | <---- | | tail

+------+ +-----+ +-----+

其中 Head 与 Tail 指针是用于标记阻塞线程节点的头尾指针，中间的节点其实就是 Node 节点，可以理解为队列，一个一个的取，处理完成则去除当前线程节点，然后指向下一个节点。

AQS同步队列

如果 thread-0 执行完毕后，他对应的 state = 0，然后释放锁，此时 AQS 队列中排队等待的线程则会按连接顺序依次出队列。此时 thread-1 不是说 thread-1 释放锁了他就直接拿到锁，他还是像之前没有拿到锁一样，通过 cas 进行修改 state 值然后拿锁。假设 thread-1 成功持有锁了，那么 aqs 维护的队列就会让队头元素出队，然后刚刚获取锁的线程成为头结点。然后一直重复入队出队的操作。

：持有锁修改 state 为 1，释放锁修改 state 为 0

从ReentrantLock的非公平独占锁实现来看AQS的原理 {#从ReentrantLock的非公平独占锁实现来看AQS的原理}

通过了解类 AbstractQueuedSynchronizer 我们可以知道他是一个抽象类，其中他还有一个父类AbstractOwnableSynchronizer

|---------------------------------------------------------------------------------------------------|------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------| | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | public abstract class AbstractOwnableSynchronizer implements java .io.Serializable { private static final long serialVersionUID = 3737899427754241961L ; protected AbstractOwnableSynchronizer () { } /** * 目前持有独占锁的线程 * The current owner of exclusive mode synchronization. */ private transient Thread exclusiveOwnerThread; /** * 此项用于设置上述属性的值 * Sets the thread that currently owns exclusive access. * A { @code null} argument indicates that no thread owns access. * This method does not otherwise impose any synchronization or * { @code volatile} field accesses. * @param thread the owner thread */ protected final void setExclusiveOwnerThread (Thread thread) { exclusiveOwnerThread = thread; } /** * 此项用于获取上述属性的值 * Returns the thread last set by { @code setExclusiveOwnerThread}, * or { @code null} if never set. This method does not otherwise * impose any synchronization or { @code volatile} field accesses. * @return the owner thread */ protected final Thread getExclusiveOwnerThread () { return exclusiveOwnerThread; } } |

其中 AQS 中比较重要的成员变量有：1. head：头指针 2. tail：尾指针

|---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------| | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 | public abstract class AbstractQueuedSynchronizer extends AbstractOwnableSynchronizer implements java .io.Serializable { private static final long serialVersionUID = 7373984972572414691L ; protected AbstractQueuedSynchronizer () { } /** * Head of the wait queue, lazily initialized. Except for * initialization, it is modified only via method setHead. Note: * If head exists, its waitStatus is guaranteed not to be * CANCELLED. */ private transient volatile Node head; /** * Tail of the wait queue, lazily initialized. Modified only via * method enq to add new wait node. */ private transient volatile Node tail; /** * The synchronization state. */ private volatile int state; /** * Returns the current value of synchronization state. * This operation has memory semantics of a { @code volatile} read. * @return current state value */ protected final int getState () { return state; } /** * Sets the value of synchronization state. * This operation has memory semantics of a { @code volatile} write. * @param newState the new state value */ protected final void setState ( int newState) { state = newState; } /** * Atomically sets synchronization state to the given updated * value if the current state value equals the expected value. * This operation has memory semantics of a { @code volatile} read * and write. * * @param expect the expected value * @param update the new value * @return { @code true} if successful. False return indicates that the actual * value was not equal to the expected value. */ protected final boolean compareAndSetState ( int expect, int update) { // See below for intrinsics setup to support this return unsafe.compareAndSwapInt( this , stateOffset, expect, update); } // Queuing utilities /** * The number of nanoseconds for which it is faster to spin * rather than to use timed park. A rough estimate suffices * to improve responsiveness with very short timeouts. */ static final long spinForTimeoutThreshold = 1000L ; } |

state：在前一节已经解释过

spinForTimeoutThreshold：超时中断

其中AQS 中还有一个 Node 静态内部类代码块

|------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------| | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 | static final class Node { /** 共享 -- 共享锁 */ static final Node SHARED = new Node (); /** 排他 -- 独占锁 */ static final Node EXCLUSIVE = null ; /** 当前等待的线程可能因为其他原因而取消 */ static final int CANCELLED = 1 ; /** 下一个节点需要被唤醒 */ static final int SIGNAL = - 1 ; /** 用于条件队列 */ static final int CONDITION = - 2 ; /** 用于共享锁 */ static final int PROPAGATE = - 3 ; volatile int waitStatus; // 初始化为0，枚举值使用上面的值 /** * 前驱节点 */ volatile Node prev; /** * 后继节点 */ volatile Node next; /** * The thread that enqueued this node. Initialized on * construction and nulled out after use. */ volatile Thread thread; /** * 在条件队列指向的是下一个指针 * 在同步队列中指向的是我们当前节点想获取的是共享锁还是排他锁 */ Node nextWaiter; /** * Returns true if node is waiting in shared mode. */ final boolean isShared () { return nextWaiter == SHARED; } /** * Returns previous node, or throws NullPointerException if null. * Use when predecessor cannot be null. The null check could * be elided, but is present to help the VM. * * @return the predecessor of this node */ final Node predecessor () throws NullPointerException { Node p = prev; if (p == null ) throw new NullPointerException (); else return p; } Node() { // Used to establish initial head or SHARED marker } Node(Thread thread, Node mode) { // Used by addWaiter this .nextWaiter = mode; this .thread = thread; } Node(Thread thread, int waitStatus) { // Used by Condition this .waitStatus = waitStatus; this .thread = thread; } } |

AQS如何实现加锁的 {#AQS如何实现加锁的}

我们通过追踪lock()方法然后追踪ReentrantLock

|-------------|--------------------------------------------------------| | 1 2 | Lock lock = new ReentrantLock (); lock.lock(); |

然后可以发现其实他是委托给Sync实现的

|---------------|----------------------------------------------| | 1 2 3 | public void lock () { sync.lock(); } |

我们知道，ReentrantLock是可以使用公平锁和非公平锁（默认）两种形式，那么Sync其实在他的类里面就是有两种表现形式。

追踪默认非公平锁实现

|------------------------------------------------------|----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------| | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | static final class NonfairSync extends Sync { private static final long serialVersionUID = 7316153563782823691L ; /** * Performs lock. Try immediate barge, backing up to normal * acquire on failure. */ final void lock () { if (compareAndSetState( 0 , 1 )) // expect: 0（无锁） update: 1（已经有一个线程加锁）如果大于1，则代表同一个线程多次加锁 setExclusiveOwnerThread(Thread.currentThread()); // 如果成功获取锁，那么把当前线程设置为持有锁的线程 else acquire( 1 ); // 如果获取锁失败，我们知道，如果一个线程多次获取锁，其实就是一个自增的情况（每次加 1） } protected final boolean tryAcquire ( int acquires) { return nonfairTryAcquire(acquires); } } |

然后我们可以发现有两个重要的函数出现了，CAS（CompareAndSwap）、Acquire

acquire {#acquire}

|-------------------|------------------------------------------------------------------------------------------------------------------------------------------| | 1 2 3 4 5 | public final void acquire ( int arg) { if (!tryAcquire(arg) && acquireQueued(addWaiter(Node.EXCLUSIVE), arg)) selfInterrupt(); } |

tryAcquire

当前方法其实我们可以理解为，在公路上有红绿灯，其中红灯停是对于人类认为并制定的规则，那么我们这个具体传入多少其实就是看 内部自己的实现 是如何的。

那么其实现类就是，除了实现AQS的state状态以外，还需要提供一些方法用于实现对state的定义。

但是话是这么说，我们通过跟踪 tryAcquire方法我们可以发现，在当前类的父类AQS里面，它是长这样的。

|---------------|-------------------------------------------------------------------------------------------------| | 1 2 3 | protected boolean tryAcquire ( int arg) { throw new UnsupportedOperationException (); } |

我们知道，AQS其实就是一个抽象类，但是在以往的学习中，我们的抽象类的实现一般都是继承全部的父类方法（描述为抽象方法）的？但是我们可以看到上面那个，它没有使用abstract去定义它，子类不是必须去对这个方法进行声明定义的，也就是说：我们只有需要实现什么再对其进行重写即可。

其次我们在对AQS进行搜索关键字 abstract ，我们可以发现当前关键字仅仅声明在类定义中。这种也是一种设计规范，值得学习。

AQS设计的初衷：为了帮助其他的同步组件设计一个规范基础，所以他不希望别人直接可以拿来就使用，而是需要在你的具体场景根据规范去具体实现。

为什么没有设计抽象方法：因为可能有些场景有些不需要去被实现，此时如果子类还调用了不需要实现的方法，那么就会抛出异常。

然后 ReentrantLock 他的 tryAcquire 我们可以发现其实默认是返回的是一个非公平的尝试获取锁（nonfairTryAcquire）

|---------------------------------------------------------------|---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------| | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | final boolean nonfairTryAcquire ( int acquires) { final Thread current = Thread.currentThread(); // 拿到当前线程 int c = getState(); // 拿到状态 if (c == 0 ) { // 没有加锁（state == 0） if (compareAndSetState( 0 , acquires)) { // 通过尝试使用CAS加锁 setExclusiveOwnerThread(current); // 设置当前线程持有锁 return true ; // 获取成功 } } // 判断是不是重入锁，如果当前持有锁的线程是当前线程 else if (current == getExclusiveOwnerThread()) { // 尝试重入，在ReentrantLock中 acquire 其实就是1，有一次重入就加一 int nextc = c + acquires; if (nextc < 0 ) // overflow // 为什么会出现这个问题呢，因为如果重入次数过多超过int的最大值，此时再加1就会变成最小值（负数） throw new Error ( "Maximum lock count exceeded" ); setState(nextc); // 设置重入值 return true ; } return false ; } |

acquireQueued

如果上面那个获取锁失败，然后就会走到这个逻辑。

|-------------|---------------------------------------------------------------| | 1 2 | // 方法签名 acquireQueued(addWaiter(Node.EXCLUSIVE), arg) |

addWaiter(Node.EXCLUSIVE)执行结果作为acquireQueued的入参

|------------------------------------------------------------------------------------------------|----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------| | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | // 没有打包的节点会被封装保存到队列里面 private Node addWaiter (Node mode) { Node node = new Node (Thread.currentThread(), mode); // Try the fast path of enq; backup to full enq on failure Node pred = tail; // AQS的尾指针 if (pred != null ) { node.prev = pred; if (compareAndSetTail(pred, node)) { pred.next = node; return node; } } enq(node); return node; } // 如果尾结点为空 private Node enq ( final Node node) { // 死循环，不断自旋 for (;;) { Node t = tail; if (t == null ) { // Must initialize if (compareAndSetHead( new Node ())) // 通过CAS将虚拟头节点设置为头节点 tail = head; } else { node.prev = t; if (compareAndSetTail(t, node)) { // 还是要通过CAS的方式设置尾指针 t.next = node; return t; // 不断自旋，只有进入了else分支才会return出去 } } } } |

其实这个enq可以和上面的那个方法合并，我们可以在java9看到其实此时已经没有了这个方法了。

acquireQueued方法

|------------------------------------------------------------------|--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------| | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | // 方法定义（其实就是把获取锁失败的线程node给添加同步队列里面去） final boolean acquireQueued ( final Node node, int arg) { boolean failed = true ; // 是否获取锁成功 try { boolean interrupted = false ; // 在获取锁期间是否发送中断 for (;;) { final Node p = node.predecessor(); // 前驱节点 if (p == head && tryAcquire(arg)) { // 是否为头节点 setHead(node); p.next = null ; // help GC failed = false ; return interrupted; } if (shouldParkAfterFailedAcquire(p, node) && // 不可响应中断 parkAndCheckInterrupt()) interrupted = true ; } } finally { if (failed) cancelAcquire(node); } } |

到了这里，可能对于这个acquireQueued的内部逻辑不太理解，没关系，其实就是将没获取锁成功的锁节点加入到同步队列中。

那么此时我们则对最开始的node状态会有所了解了（加上int默认的0，其实是有五个状态的）

|-------------------------|-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------| | 1 2 3 4 5 6 7 8 | /** 当前等待的线程可能因为其他原因而取消 */ static final int CANCELLED = 1 ; /** 下一个节点需要被唤醒 */ static final int SIGNAL = - 1 ; /** 用于条件队列 */ static final int CONDITION = - 2 ; /** 用于共享锁 */ static final int PROPAGATE = - 3 ; |

那么从lock方法进来构建的同步队列中，节点的状态不可能为1的，他是被取消的。

那么 -1是肯定有可能的，因为他用于唤醒下一个节点的。

-2 （CONDITION）是用于条件队列中，我们的队列并不是条件队列，那么肯定是用不到该状态的

-3 （PROPAGATE）用于共享模式下的一个状态，对于ReentrantLock是独占锁，那么肯定是用不到该状态的

-- 此处可以跳过了--

这个我们知道了之后，我们看到有方法shouldParkAfterFailedAcquire

|---------------------------------------------------------------------------------|-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------| | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | private static boolean shouldParkAfterFailedAcquire (Node pred, Node node) { int ws = pred.waitStatus; if (ws == Node.SIGNAL) // 前驱节点是SIGNAL则阻塞当前操作 /* * This node has already set status asking a release * to signal it, so it can safely park. */ return true ; if (ws > 0 ) { // 不是多余的，因为其他的锁实现也是要走当前情况的 /* * Predecessor was cancelled. Skip over predecessors and * indicate retry. */ do { node.prev = pred = pred.prev; } while (pred.waitStatus > 0 ); pred.next = node; } else { /* * waitStatus must be 0 or PROPAGATE. Indicate that we * need a signal, but don't park yet. Caller will need to * retry to make sure it cannot acquire before parking. */ compareAndSetWaitStatus(pred, ws, Node.SIGNAL); } return false ; } |

compareAndSetState() {#compareAndSetState}

JDK动态代理案例 {#JDK动态代理-案例}

**需求: ** 简单的实现增强(AOP)

JDK动态代理只能代理实现了接口的类，不支持对类的直接代理

在此提供一个接口和一个实现类, 需要对接口实现类中的方法进行增强

|-------------------|----------------------------------------------------------------------------------------------| | 1 2 3 4 5 | // Interface public interface IHello { public void hello () ; public void bye () ; } |

增强部分:

首先需要自定义类实现 InvocationHandler 接口, 其次重写 invoke 方法, 通过invoke方法进行代理: 案例如下:

|---------------------------------------------------------------------------------------------------------------|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------| | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | public class ProxyHandler implements InvocationHandler { private Object target; // 目标类 public ProxyHandler (Object target) { this .target = target; // $Proxy01: hello() Bye() } // 生成代理对象方法 public Object createProxy () { // JDK中提供了 Proxy类, 有一个方法专门用于根据接口生成代理类对象的方法 Object proxy = Proxy.newProxyInstance(ProxyHandler.class.getClassLoader(), target.getClass().getInterfaces(), this ); return proxy; // $Proxy01 Hello() Bye() } /** * @param proxy 代理对象 $Proxy01 * @param method 调用的方法 hello() * @param args 方法的参数值 */ @Override public Object invoke (Object proxy, Method method, Object[] args) throws Throwable { // 解释 @Pointcut("execution(* com.hang..add*(..))") if (method.getName().equalsIgnoreCase( "hello" )){ // 增强 showTime(); } // 利用反射机制调用目标类的目标方法 Object reflectObj = method.invoke(target, args); // HelloImpl.Hello() 目标类的方法 return reflectObj; } // 增强的方法 private void showTime () { System.out.println( "当前时间为: " + new Date ()); } } |

对于24-26行: 对于方法名为 hello进行增强, 此处以前置增强为例, 在方法执行(invoke)前, 执行自定义方法(showTime)显示时间

测试方法:

|---------------------------------------------|--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------| | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | public class Main { public static void main (String[] args) { // 在本地生成代理对象字节码文件 System.getProperties().put( "sun.misc.ProxyGenerator.saveGeneratedFiles" , "true" ); IHello target = new HelloImpl (); // 目标类 ProxyHandler handler = new ProxyHandler (target); // 生成代理类 Object proxy = handler.createProxy(); System.out.println(proxy); // Proxy0对象 IHello obj = (IHello) proxy; obj.hello(); // $ Proxy0.Hello() obj.bye(); } } |

输出如下:

|-----------------|-----------------------------------------------------------------------------------| | 1 2 3 4 | com.hang.HelloImpl@61bbe9ba 当前时间为: Sat Nov 25 10:31:56 SGT 2023 Hello Bye |

可以很明显的看到, 在hello方法执行前, 输出了自定义增强方法showTime

此时需要观察生成代理字节码类可以在测试中添加

|-----------|----------------------------------------------------------------------------------------------| | 1 | System.getProperties().put( "sun.misc.ProxyGenerator.saveGeneratedFiles" , "true" ); |

添加该行后, 在当前Module的同目录下会生成文件夹为 com.sum.proxy ,文件夹内会生成字节码$Proxy0 ... $Proxy20 ... 数字部分可变

以当前案例生成的字节码为例: ($Proxy0.class)

|------------------------------------------------------------------------------------------------------------------------------------------|------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------| | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 | public final class $Proxy0 extends Proxy implements IHello { private static Method m1; private static Method m4; private static Method m3; private static Method m2; private static Method m0; public $Proxy0(InvocationHandler var1) throws { super (var1); } public final void bye () throws { try { super .h.invoke( this , m4, (Object[]) null ); } catch (RuntimeException | Error var2) { throw var2; } catch (Throwable var3) { throw new UndeclaredThrowableException (var3); } } public final void hello () throws { try { super .h.invoke( this , m3, (Object[]) null ); } catch (RuntimeException | Error var2) { throw var2; } catch (Throwable var3) { throw new UndeclaredThrowableException (var3); } } // 省略equals,toString,hashCode三方法同上(为默认生成) static { try { m1 = Class.forName( "java.lang.Object" ).getMethod( "equals" , Class.forName( "java.lang.Object" )); m4 = Class.forName( "com.hang.IHello" ).getMethod( "bye" ); m3 = Class.forName( "com.hang.IHello" ).getMethod( "hello" ); m2 = Class.forName( "java.lang.Object" ).getMethod( "toString" ); m0 = Class.forName( "java.lang.Object" ).getMethod( "hashCode" ); } catch (NoSuchMethodException var2) { throw new NoSuchMethodError (var2.getMessage()); } catch (ClassNotFoundException var3) { throw new NoClassDefFoundError (var3.getMessage()); } } } |

通过该字节码文件可以很明显的发现一共生成了 5个 Method (两个为刚刚定义的方法, 三个(1.equals 2.toString 3.hashCode)为默认生成的)
在代码尾部的static部分, 生成了方法上述的5个方法

以当前字节码文件中的 hello() 为例 (因为我们对该方法增强了):

该方法主要逻辑为执行 super.h.invoke(this, m3, (Object[])null);

该方法很明确就是调用父类的 InvocationHandler

|-------------|-------------------------------------------------------------------------------------------| | 1 2 | // the invocation handler for this proxy instance. protected InvocationHandler h; |

然后调用invoke, 这个invoke不就是我们案例中重写了的invoke吗?

总结: 通过代理接口实现接口方法, 当调用时执行代理类中的同名方法然后回调到我们自定义的invoke, 在该方法内可以实现增强(前置,后置,环绕)

JDK谓词 {#JDK谓词}

直接上案例

|-----------------|--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------| | 1 2 3 4 | List<String> ns= Arrays.asList( "calyee blog" , "cal" , "ccaaalyyyyeeee" ); ArrayList<String> names = new ArrayList <>(ns); Predicate<String> predicate = s -> s.length() > 3 ; // 谓词 names.removeIf(predicate); |

追踪Predicate

|---------------------------|---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------| | 1 2 3 4 5 6 7 8 9 | @FunctionalInterface public interface Predicate <T> { boolean test (T t) ; // 仅列出一个 (其他的还有比如或运算) default Predicate<T> and (Predicate<? super T> other) { Objects.requireNonNull(other); return (t) -> test(t) && other.test(t); } } |

当前案例为: 筛选长度大于3的对象

其中 removeIf 方法为传入一个谓词对象, 通过谓词条件构造筛选条件, 然后重复遍历(类似于构造if-else判断)

所以: 谓词工厂就是一个判断

消费者回调 {#消费者回调}

在Java编程中，有时需要对某个对象进行操作或者处理，而这个操作可能是非常灵活的。Java 8引入了函数式编程的特性，其中的一个重要接口就是 Consumer 接口

例如在Java中比较常见的foreach

|---------------------|---------------------------------------------------------------------------------------------------------------------------------------| | 1 2 3 4 5 6 | default void forEach (Consumer<? super T> action) { Objects.requireNonNull(action); for (T t : this ) { action.accept(t); } } |

通过阅读我们可以知道，传入了一个集合，然后对每一个元素进行遍历，然后再 accept(t) 回调消费，像这样回调就能拿到每一个对象的值。

那么后续的回调就是通过匿名函数调用

这里还能实现类似的Spring AOP的功能（增强顺序），情景：通过递归遍历链表

Java8特性 {#Java8特性}

Stream {#Stream}

直接代码奉上

|------------------------------------------------------------|---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------| | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | Map<Integer, List<ByYearInnerDataVO>> optimizedData = yearIndicatorData.entrySet().stream() .collect(Collectors.toMap(Map.Entry::getKey, entry -> { Set<String> indicator = yearAndIndicator.keySet(); // 指标对应年份 -- 即补充标准 return indicator.stream() // 创建指标集合的流 .map(indicatorName -> { // 对每个指标名进行处理 return entry.getValue().stream() // 获取当前年份的内部数据列表的流 .filter(i -> indicatorName.equals(i.getIndicatorName())) // 过滤出匹配指标名的数据（按照补充标准） .findFirst() // 找到第一个匹配的数据(则不需要处理，使用原有数据即可) .orElseGet(() -> { // 如果没有找到，则创建并返回一个新的ByYearInnerDataVO实例 return new ByYearInnerDataVO () .setIndicatorName(indicatorName) // 设置指标名 .setCount( "0" ) .setRate( "/" ) .setIncr( "/" ) .setValue( 0 ); }); // 补充空数据 }).collect(Collectors.toList()); // 将结果收集成列表 } )); |

用的多的就是

map() - 过程中 {#map-过程中}

map是可以对里面的数据进行处理的，同样使用的还有peek( )，不过这个笔者测试好像不会对内部结构改变（不常用）

|-------------------|--------------------------------------------------------------------------------------------------------------------------------------------------| | 1 2 3 4 5 | indicator.stream().map(indicatorName -> { Indicator i = new Indicator (); // 数据处理 return i; }).collect(Collectors.toList()); // 将结果收集成列表 |

groupBy() - 结果 {#groupBy-结果}

|-------------|-------------------------------------------------------------------------------------------------------------------| | 1 2 | Map<Integer, List<OurBean>> groupByYear = list.stream().collect(Collectors.groupingBy(OurBean::getYear)); |

然后就可以得到以年份为key的List对象

其他 {#其他}

笔者今天看到每日一题有解答者使用了 IntStream

|-----------|-----------------------------------------------------------------------------------------| | 1 | int result = IntStream.of(arr).min().getAsInt(); // 通过intstream流获取arr数组的最小值并且获取 |

然后通过分析，笔者发现这个里面还有 DoubleStream 等类，然后点进去发现他们继承自 BaseStream<T, TStream> 其中T代表例如int、double这种数据类型

然后再分析，其实就是stream流的基础操作，这个只不过可以直接处理我们已经明确的基础数据类型数据

Optional {#Optional}

好用，可以避免一些判空的操作

|-------------------|--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------| | 1 2 3 4 5 | // 如果list.get(i)为空，那么就是执行后面的语句 Optional.ofNullable(list.get(i)).orElse( new Obj ()); // 如果byId.getIpInfo()不为空，那么则得到创建的ip，否null blackIP(Optional.ofNullable(byId.getIpInfo()).map(IpInfo::getCreateIp).orElse( null )); |

BigDecimal {#BigDecimal}

浮点类型 {#浮点类型}

高精度之精度丢失

|-----------------|----------------------------------------------------------------------------------------------------------| | 1 2 3 4 | // 用法一 BigDecimal a = new BigDecimal ( 0.01 ); // 用法二 BigDecimal b = BigDecimal.valueOf( 0.01 ); |

对应的结果如下:

a: 0.01000000000000000020816681711721685132943093776702880859375
b: 0.01

那么: 在 new BigDecimal 的时候传入的已经是浮点类型( 近似值 )了, 而在使用 valueOf 的时候, 通过阅读源码可知

|---------------|----------------------------------------------------------------------------------------------------------| | 1 2 3 | public static BigDecimal valueOf ( double val) { return new BigDecimal (Double.toString(val)); } |

在valueOf的方法内部, 调用了Double.toString方法转换成为了字符串, 转换成为字符串就不存在进度丢失问题 (因为可以使用字符串模拟高精度实现计算: 梦回c语言高精度实现)

那么我们需要使用则: (两个方向)

创建对象时, 构造函数传字符串
使用BigDecimal.valueOf传值初始化对象

精度设置 {#精度设置}

其实就是四舍五入的问题

|-------------|-------------------------------------------------------------------------------------------| | 1 2 | BigDecimal a = new BigDecimal ( "1.0" ); BigDecimal b = new BigDecimal ( "3.0" ); |

例如我们需要运算

|-----------|----------------------| | 1 | a.divide(b); |

然后就会抛出异常: ArithmeticException

因为它(结果)是一个无限循环小数, 它不能转换成为我们预期的精确数字

所以需要指定精度

|-----------|--------------------------------------------------------------| | 1 | BigDecimal c = a.divide(b, 4 ,RoundingMode.HALF_UP); |

4: 四位小数
RoundingMode.HALF_UP: HALF_UP-> 大于一半则向上取整

故结果为: 0.3333

其中RoundingMode还有很多枚举, 自行查阅

浮点比较 {#浮点比较}

比较BigDecimal值的大小

|-------------|----------------------------------------------------------------------------------------------| | 1 2 | BigDecimal a = new BigDecimal ( "0.01" ); BigDecimal b = new BigDecimal ( "0.010" ); |

然后有两种比较方法

|-------------|------------------------------------| | 1 2 | a.equals(b) a.compareTo(b) |

其中一看好像没什么区别, 查阅源码( equals )可知

compareTo则是实现比较值的大小, 返回的值为-1（小于），0（等于），1（大于）

我们可以知道, 如果在严格 ++要求精度++ 的情况下, 使用 equals

如果 ++仅考虑值的大小++ 则考虑使用 compareTo

输出格式化 {#输出格式化}

此处仅给出几个示例:

|---------------------------------|------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------| | 1 2 3 4 5 6 7 8 9 10 11 | NumberFormat currency = NumberFormat.getCurrencyInstance(); //建立货币格式化引用 NumberFormat percent = NumberFormat.getPercentInstance(); //建立百分比格式化引用 percent.setMaximumFractionDigits( 4 ); //百分比小数点最多4位 BigDecimal loanAmount = new BigDecimal ( "59988.24" ); //金额 BigDecimal interestRate = new BigDecimal ( "0.007" ); //利率 BigDecimal interest = loanAmount.multiply(interestRate); //相乘 System.out.println( "金额:\t" + currency.format(loanAmount)); System.out.println( "利率:\t" + percent.format(interestRate)); System.out.println( "利息:\t" + currency.format(interest)); |

输出:

|---------------|---------------------------------------------| | 1 2 3 | 金额: ￥59,988.24 利率: 0.7% 利息: ￥419.92 |