AbstractQueuedSynchronizer 简介

本文主要介绍了 JUC 中的 AbstractQueuedSynchronizer 的实现基础、其和 CLH 队列锁之间的关联、独占锁模式及共享锁模式加解锁的过程等。不包含 ConditionObject 的分析。 简介 AQS 提供了实现同步阻塞队列的基本框架，是 juc 包中其他众多同步原语和锁实现的基础。 Provides a framework for implementing blocking locks and related synchronizers (semaphores, events, etc) that rely on first-in-first-out (FIFO) wait queues. This class is designed to be a useful basis for most kinds of synchronizers that rely on a single atomic int value to represent state. Subclasses must define the protected methods that change this state, and which define what that state means in terms of this object being acquired or released.

深入理解 CLH Queue Lock

JUC 包中的很多同步原语是基于 AbstractQueuedSynchronizer（以下简称 AQS） 实现的，而 AQS 的实现又是基于 CLH 队列锁（CLH queued lock），因此学习并理解 CLH 队列锁对我们学习 JUC 中的各种同步原语非常有帮助。本文将阐述 CLH 队列锁的实现和原理。 CLH Queue Lock CLH 队列锁是由 Craig, Landin, Hagersten 三位大佬提出的，因此被称为 CLH 队列锁，它是一种自旋公平锁，基于虚链表实现（virtual linked list）。 《The Art of Multiprocessor Programming》7.5.2 节给出了 CLH 可能的一种 Java 语言实现： public class CLHLock implements Lock { AtomicReference<QNode> tail; ThreadLocal<QNode> myPred; ThreadLocal<QNode> myNode; public CLHLock() { tail = new AtomicReference<QNode>(new QNode()); myNode = new ThreadLocal<QNode>() { protected QNode initialValue() { return new QNode(); } }; myPred = new ThreadLocal<QNode>() { protected QNode initialValue() { return null; } }; } public void lock() { QNode qnode = myNode.

LeetCode 笔记 5：Search in Rotated Sorted Array

今天要讲的题目都使用到了二分查找（或者和二分查找紧密相关），同时又都是基于一个 Rotated Sorted Array。那么先从 Rotated Sorted Array 的特点讲起吧。 Rotated Sorted Array 的定义是这样子的： There is an integer array nums sorted in ascending order (with distinct values). nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). 就拿 int[] nums = new int[]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; 举例好了，如果 nums 在 nums[4] 位置进行旋转，那么它将变成： {4, 5, 6, 7, 8, 9, 10, 0, 1, 2, 3} ，那么我们能够观察到几个特性：

深入理解 B+ Tree

B+ 树的定义和 B 树是类似的，B+ 树在数据结构上进行了一定的改进，它的特性使得它的某些场景下教 B 树有了显著的优势。本文笔者将对 B+ 树的定义、特点以及应用进行详细解析。 定义 B+ 树和 B 树的定义是类似的，它们都是平衡多路搜索树，在文件系统和数据库系统中都有大量的应用。只不过 B+ 树有以下几点独特的属性： B+ 树的非叶子结点不包含值（value），只存储键（key） B+ 树的叶子结点之间是互相连接的，B+ 树叶子结点这一层构成了一个双向链表（Doubly linked list） B+ 树的叶子结点这一层存储了所有数据的 key-links pairs，而 B 树的所有数据是散布在整棵树中的，B 树的叶子结点这一层只存储了数据全集的一部分。 B+ 树的查找、添加、删除算法和 B 树是类似的，可以参考笔者的上一篇博客进行了解：深入理解 B-Tree | caffcen’s blog，在此不在赘述。 特性 对于阶数为 m 的 B+ 树，它拥有如下性质： 每个节点最多有 m 个子节点。 每个节点最多有 m-1 个键值。 每个内部节点至少有 ⌈m/2⌉ 个子节点，根节点除外。 根节点至少有 2 个子节点。 所有叶子节点出现在同一层级上，叶子结点与叶子结点之间有双向引用，叶子结点这一层构成了一条双向链表。 一个具有 k 个子节点的非叶节点包含 k-1 个键值。 叶子结点这一层存储了所有数据（所有的 key-link pairs） B-Tree vs. B+ Tree B 树和 B+ 树的区别对比，可以参考 Stack Overflow 这个问题：database - What are the differences between B trees and B+ trees?

深入理解 B-Tree

B 树是一种平衡多路搜索树，可以看做是对二叉搜索树（Binary Search Tree）的拓展。因为 B 树的自平衡以及允许一个节点存储多个值的特性，被广泛运用在数据库以及文件系统中，非常适用于存储大量数据。 要理解 B 树，最好的方式就是学习 2-3 搜索树——B 树的一种特例。 1. 2-3 搜索树 (2-3 Search Tree) 1.1 定义 2-3 搜索树是对二叉搜索树一种自然的扩充，二叉搜索树的任意一个节点只能存储一个 key、两个 links，但是 2-3 搜索树扩展了这一设定，2-3 搜索树允许存在以下两类节点： 2-node：拥有一个 key 两个 links，2-node 和二叉搜索树中的节点完全等价，两个 links 分别指向左子树和右子树： 左子树中的所有节点的 key 均『小于』当前 2-node 的 key； 右子树中的所有节点均『大于』当前 2-node 的 key。 3-node：拥有两个 keys 三个 links，3 个 links 分别指向左子树、右子树和中间子树： 左子树中的所有节点的 key 均『小于』当前 3-node 较小的 key； 右子树中的所有节点均『大于』当前 3-node 较大的 key； 中间子树中的所有节点均大于 3-node 较小的 key，且小于 3-node 较大的 key。 这里大于、小于打引号是因为类型的大小关系往往是可以自定义的。 本文使用 key 表示存储数据的键，links 表示指向其他节点的引用，value 表示存储数据实际存储的值，在数据库以及文件系统中，value 可能是指向实际数据的指针。