当前位置：首页 > news >正文

java哨兵底层原理

news 2025/6/14 11:59:03

哨兵机制在 Java 中是一种重要的设计模式，广泛应用于集合框架、并发控制和垃圾回收等多个领域。下面从不同角度深入分析其底层原理：

哨兵模式的本质

哨兵模式本质上是一种空间换时间的优化策略，通过引入特殊的标记对象来简化算法逻辑，减少边界条件的判断，从而提高执行效率。在 Java 中，哨兵通常以以下形式存在：

特殊节点对象：如 LinkedList 中的哑节点 (Dummy Node)
特殊值标记：如 ConcurrentHashMap 中的 MOVED 标记
空对象模式：如 Collections.emptyList () 返回的不可变空列表

Java 集合框架中的哨兵实现

LinkedList 中的哨兵节点

Java 的 LinkedList 是哨兵模式的经典应用。它使用一个双向循环链表结构，其中包含一个哨兵节点 (header)：

// Java LinkedList中的哨兵节点简化了操作
// 实际JDK源码中的实现与此类似但更复杂public class LinkedListSentinel<E> {// 哨兵节点（哑节点），不存储实际数据private Node<E> header = new Node<>(null, null, null);private int size = 0;// 节点结构private static class Node<E> {E item;Node<E> next;Node<E> prev;Node(Node<E> prev, E element, Node<E> next) {this.item = element;this.next = next;this.prev = prev;}}public LinkedListSentinel() {// 初始化时，哨兵节点指向自己，形成循环header.next = header;header.prev = header;}// 在链表末尾添加元素public boolean add(E e) {// 新节点的前驱是哨兵的前驱（即当前最后一个节点）// 新节点的后继是哨兵Node<E> newNode = new Node<>(header.prev, e, header);// 更新链接关系header.prev.next = newNode;header.prev = newNode;size++;return true;}// 获取指定位置的元素public E get(int index) {checkElementIndex(index);return node(index).item;}// 查找指定位置的节点Node<E> node(int index) {// 优化：根据索引位置决定从头部还是尾部开始遍历if (index < (size >> 1)) {Node<E> x = header.next;for (int i = 0; i < index; i++)x = x.next;return x;} else {Node<E> x = header.prev;for (int i = size - 1; i > index; i--)x = x.prev;return x;}}private void checkElementIndex(int index) {if (!isElementIndex(index))throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}private boolean isElementIndex(int index) {return index >= 0 && index < size;}private String outOfBoundsMsg(int index) {return "Index: "+index+", Size: "+size;}// 其他方法...
}

在这个实现中，哨兵节点 header 的作用：

简化空列表判断：空列表时，header.next == header
统一首尾操作：添加或删除元素时无需特殊处理头尾节点
形成循环结构：使双向链表操作更加一致

HashMap 中的哨兵节点

HashMap 在处理哈希冲突时使用链表或红黑树结构，其中链表的遍历也利用了哨兵思想：

// HashMap中链表遍历的简化示例
final 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 &&((k = first.key) == key || (key != null && key.equals(k))))return first;// 遍历链表，注意这里的条件判断：e != null// 链表末尾节点的next为null，作为遍历结束的哨兵if ((e = first.next) != null) {do {if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;} while ((e = e.next) != null);}
}

这里虽然没有显式的哨兵节点，但链表末尾的 null 值实际上充当了哨兵的角色，终止遍历过程。

并发编程中的哨兵机制

ConcurrentHashMap 中的 MOVED 标记
在 ConcurrentHashMap 的扩容过程中，使用了特殊的节点类型作为哨兵：
// ConcurrentHashMap中的MOVED标记节点
static final class ForwardingNode<K,V> extends Node<K,V> {final Node<K,V>[] nextTable;ForwardingNode(Node<K,V>[] tab) {// hash值为MOVED，作为特殊标记super(MOVED, null, null, null);this.nextTable = tab;}// 重写查找方法，将请求转发到新表Node<K,V> find(int h, Object k) {// 使用循环技巧，避免递归outer: for (Node<K,V>[] tab = nextTable;;) {Node<K,V> e; int n;if (k == null || tab == null || (n = tab.length) == 0 ||(e = tabAt(tab, (n - 1) & h)) == null)return null;for (;;) {int eh; K ek;if ((eh = e.hash) == h &&((ek = e.key) == k || (ek != null && k.equals(ek))))return e;if (eh < 0) {if (e instanceof ForwardingNode) {tab = ((ForwardingNode<K,V>)e).nextTable;continue outer;}elsereturn e.find(h, k);}if ((e = e.next) == null)return null;}}}
}

在扩容过程中，ConcurrentHashMap 会在原位置放置一个 ForwardingNode（hash 值为 MOVED）作为哨兵：

其他线程遇到 MOVED 标记时，知道正在扩容并协助迁移
查找操作会被转发到新表
实现了无锁扩容的并发控制

AQS 中的哨兵节点

AbstractQueuedSynchronizer (AQS) 是 Java 并发包的基础框架，其中也使用了哨兵节点：

// AQS中的CLH队列节点结构
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;volatile Node prev;volatile Node next;volatile Thread thread;Node nextWaiter;// 判断是否为共享模式final boolean isShared() {return nextWaiter == SHARED;}// 获取前驱节点final Node predecessor() throws NullPointerException {Node p = prev;if (p == null)throw new NullPointerException();elsereturn p;}Node() {    // Used to establish initial head or SHARED marker}Node(Thread thread, Node mode) {     // Used by addWaiterthis.nextWaiter = mode;this.thread = thread;}Node(Thread thread, int waitStatus) { // Used by Conditionthis.waitStatus = waitStatus;this.thread = thread;}
}

AQS 的 CLH 队列中，头节点是一个哨兵节点，不关联任何线程，它的作用：