小红书Java面试被问：使用VarHandle实现内存安全的无锁数据结构
一、VarHandle 基础与优势
1. VarHandle 与 Atomic 对比
java
复制
下载
// 传统的 Atomic 类使用 AtomicInteger count = new AtomicInteger(0); count.compareAndSet(0, 1); // CAS 操作 // VarHandle 实现相同功能 class Counter { private volatile int value = 0; private static final VarHandle VALUE_HANDLE; static { try { VALUE_HANDLE = MethodHandles.lookup() .findVarHandle(Counter.class, "value", int.class); } catch (Exception e) { throw new Error(e); } } public boolean compareAndSet(int expected, int update) { return VALUE_HANDLE.compareAndSet(this, expected, update); } }
2. VarHandle 的核心特性
java
复制
下载
public class VarHandleFeatures { /** * VarHandle 相比 Unsafe 的优势： * 1. 类型安全 - 编译期检查 * 2. 内存语义明确 - acquire/release/volatile * 3. 平台无关性 - 在 AOT 编译中有更好支持 * 4. 访问模式 - 支持多种访问模式 */ // VarHandle 支持的内存访问模式 enum AccessMode { GET, // 普通读 SET, // 普通写 GET_VOLATILE, // volatile 读 SET_VOLATILE, // volatile 写 GET_ACQUIRE, // acquire 语义读 SET_RELEASE, // release 语义写 GET_OPAQUE, // opaque 读（无内存排序保证） SET_OPAQUE, // opaque 写 COMPARE_AND_SET, // CAS COMPARE_AND_EXCHANGE, // 比较并交换 GET_AND_SET, // 获取并设置 GET_AND_ADD, // 获取并增加 GET_AND_BITWISE_OR // 获取并按位或 } }
二、无锁栈实现（Treiber Stack）
1. 完整的无锁栈实现
java
复制
下载
import java.lang.invoke.MethodHandles; import java.lang.invoke.VarHandle; import java.util.NoSuchElementException; import java.util.concurrent.atomic.AtomicReference; /** * 基于 VarHandle 实现的内存安全无锁栈 * Treiber Stack 算法，使用 CAS 实现线程安全 */ public class LockFreeStack<E> { /** * 栈节点定义 */ private static class Node<E> { final E item; Node<E> next; Node(E item) { this.item = item; this.next = null; } } /** * 使用 VarHandle 替代 AtomicReference */ private volatile Node<E> top = null; private static final VarHandle TOP_HANDLE; static { try { TOP_HANDLE = MethodHandles.lookup() .findVarHandle(LockFreeStack.class, "top", Node.class); } catch (Exception e) { throw new Error(e); } } /** * 压栈操作 - 无锁实现 * @param item 要压入的元素 */ public void push(E item) { Node<E> newNode = new Node<>(item); Node<E> currentTop; do { // acquire 语义读当前栈顶 currentTop = (Node<E>) TOP_HANDLE.getAcquire(this); newNode.next = currentTop; // CAS 操作更新栈顶 // release 语义确保 newNode 的初始化对后续读可见 } while (!TOP_HANDLE.compareAndSet(this, currentTop, newNode)); // 可选：压栈后的清理或通知操作 postPush(newNode); } /** * 弹栈操作 - 无锁实现 * @return 弹出的元素 * @throws NoSuchElementException 如果栈为空 */ public E pop() { Node<E> currentTop; Node<E> nextTop; do { // volatile 读当前栈顶 currentTop = (Node<E>) TOP_HANDLE.getVolatile(this); if (currentTop == null) { throw new NoSuchElementException("Stack is empty"); } nextTop = currentTop.next; // CAS 操作更新栈顶 // 使用 release 语义确保弹栈操作的可见性 } while (!TOP_HANDLE.compareAndSetRelease(this, currentTop, nextTop)); // 帮助 GC，断开引用 currentTop.next = null; return currentTop.item; } /** * 安全的弹栈操作（无异常版） * @return 弹出的元素，如果栈为空则返回 null */ public E popSafe() { Node<E> currentTop; Node<E> nextTop; do { currentTop = (Node<E>) TOP_HANDLE.getVolatile(this); if (currentTop == null) { return null; // 栈为空 } nextTop = currentTop.next; // 使用 weakCompareAndSet 在某些场景下性能更好 } while (!TOP_HANDLE.weakCompareAndSet(this, currentTop, nextTop)); E item = currentTop.item; currentTop.next = null; // 帮助 GC return item; } /** * 批量压栈操作 - 减少 CAS 竞争 * @param items 要压入的元素数组 */ public void pushAll(E[] items) { if (items == null || items.length == 0) { return; } // 构建本地链表 Node<E> first = new Node<>(items[0]); Node<E> last = first; for (int i = 1; i < items.length; i++) { Node<E> node = new Node<>(items[i]); last.next = node; last = node; } Node<E> currentTop; do { // 获取当前栈顶 currentTop = (Node<E>) TOP_HANDLE.getAcquire(this); last.next = currentTop; // 一次性将整个链表压入 } while (!TOP_HANDLE.compareAndSet(this, currentTop, first)); } /** * 查看栈顶元素（不弹出） * @return 栈顶元素，如果栈为空则返回 null */ public E peek() { // acquire 语义读，确保看到最新的数据 Node<E> currentTop = (Node<E>) TOP_HANDLE.getAcquire(this); return currentTop != null ? currentTop.item : null; } /** * 栈是否为空 * @return 如果栈为空返回 true */ public boolean isEmpty() { // 使用 opaque 读，减少内存屏障开销 return TOP_HANDLE.getOpaque(this) == null; } /** * 获取栈的大小（非线程安全，仅用于调试） * @return 栈的近似大小 */ public int size() { int count = 0; // acquire 语义确保读到最新的链表 Node<E> current = (Node<E>) TOP_HANDLE.getAcquire(this); while (current != null) { count++; current = current.next; } return count; } /** * 清空栈 */ public void clear() { // 使用 setVolatile 确保清空操作对其他线程可见 TOP_HANDLE.setVolatile(this, null); } /** * 压栈后的回调（模板方法，子类可重写） */ protected void postPush(Node<E> newNode) { // 默认空实现，可用于统计、监控等 } /** * 性能优化的弹栈操作 - 使用自旋优化 */ public E popOptimized() { final int MAX_SPINS = 100; // 最大自旋次数 int spins = 0; while (true) { Node<E> currentTop = (Node<E>) TOP_HANDLE.getAcquire(this); if (currentTop == null) { return null; } // 检查是否有可能竞争 if (spins < MAX_SPINS && TOP_HANDLE.getVolatile(this) == currentTop) { spins++; Thread.onSpinWait(); // JDK 9+ 自旋提示 continue; } Node<E> nextTop = currentTop.next; if (TOP_HANDLE.compareAndSet(this, currentTop, nextTop)) { E item = currentTop.item; currentTop.next = null; return item; } spins = 0; // CAS 失败，重置自旋计数 } } }
篇幅限制下面就只能给大家展示小册部分内容了。整理了一份核心面试笔记包括了：Java面试、Spring、JVM、MyBatis、Redis、MySQL、并发编程、微服务、Linux、Springboot、SpringCloud、MQ、Kafc
需要全套面试笔记及答案
【点击此处即可/免费获取】
2. 带 ABA 问题防护的增强版栈
java
复制
下载
/** * 使用指针标记解决 ABA 问题的无锁栈 * 通过版本号防止 ABA 问题 */ public class LockFreeStackWithStamped<E> { /** * 带标记的指针 */ private static class StampedReference<T> { final T reference; final long stamp; // 版本号 StampedReference(T reference, long stamp) { this.reference = reference; this.stamp = stamp; } } /** * 栈节点 */ private static class Node<E> { final E item; volatile Node<E> next; Node(E item) { this.item = item; } } /** * 使用 VarHandle 管理带标记的栈顶 */ private volatile StampedReference<Node<E>> top = new StampedReference<>(null, 0); private static final VarHandle TOP_HANDLE; private static final VarHandle STAMP_HANDLE; static { try { TOP_HANDLE = MethodHandles.lookup() .findVarHandle( LockFreeStackWithStamped.class, "top", StampedReference.class ); } catch (Exception e) { throw new Error(e); } } /** * 压栈 - 带版本号的 CAS */ public void push(E item) { Node<E> newNode = new Node<>(item); StampedReference<Node<E>> currentTop; StampedReference<Node<E>> newTop; do { // 获取当前栈顶和版本号 currentTop = (StampedReference<Node<E>>) TOP_HANDLE.getAcquire(this); newNode.next = currentTop.reference; // 创建新的带版本号的引用 newTop = new StampedReference<>( newNode, currentTop.stamp + 1 // 版本号递增 ); } while (!TOP_HANDLE.compareAndSet( this, currentTop, newTop )); } /** * 弹栈 - 带版本号的 CAS */ public E pop() { StampedReference<Node<E>> currentTop; StampedReference<Node<E>> newTop; Node<E> nextNode; do { currentTop = (StampedReference<Node<E>>) TOP_HANDLE.getVolatile(this); Node<E> topNode = currentTop.reference; if (topNode == null) { return null; } nextNode = topNode.next; // 版本号递增 newTop = new StampedReference<>( nextNode, currentTop.stamp + 1 ); } while (!TOP_HANDLE.compareAndSetRelease( this, currentTop, newTop )); return currentTop.reference.item; } }
三、无锁队列实现（Michael-Scott 队列）
1. 完整的无锁队列实现
java
复制
下载
import java.lang.invoke.MethodHandles; import java.lang.invoke.VarHandle; import java.util.NoSuchElementException; import java.util.concurrent.atomic.AtomicReference; /** * 基于 VarHandle 实现的内存安全无锁队列 * Michael-Scott 算法，支持多生产者多消费者 */ public class LockFreeQueue<E> { /** * 队列节点 */ private static class Node<E> { volatile E item; volatile Node<E> next; Node(E item) { this.item = item; } } /** * 哑节点（sentinel） */ private volatile Node<E> dummy = new Node<>(null); /** * 队列头指针（始终指向哑节点） */ private volatile Node<E> head; /** * 队列尾指针 */ private volatile Node<E> tail; /** * VarHandle 声明 */ private static final VarHandle HEAD_HANDLE; private static final VarHandle TAIL_HANDLE; private static final VarHandle NEXT_HANDLE; private static final VarHandle ITEM_HANDLE; static { try { MethodHandles.Lookup lookup = MethodHandles.lookup(); HEAD_HANDLE = lookup.findVarHandle( LockFreeQueue.class, "head", Node.class ); TAIL_HANDLE = lookup.findVarHandle( LockFreeQueue.class, "tail", Node.class ); NEXT_HANDLE = lookup.findVarHandle( Node.class, "next", Node.class ); ITEM_HANDLE = lookup.findVarHandle( Node.class, "item", Object.class ); } catch (Exception e) { throw new Error(e); } } /** * 构造函数 */ public LockFreeQueue() { head = dummy; tail = dummy; } /** * 入队操作 */ public void enqueue(E item) { if (item == null) { throw new NullPointerException(); } Node<E> newNode = new Node<>(item); Node<E> currentTail; Node<E> tailNext; while (true) { // 获取当前尾节点 currentTail = (Node<E>) TAIL_HANDLE.getAcquire(this); tailNext = (Node<E>) NEXT_HANDLE.getAcquire(currentTail); // 检查尾节点是否仍然有效 if (currentTail == (Node<E>) TAIL_HANDLE.getVolatile(this)) { if (tailNext == null) { // 尝试链接新节点 if (NEXT_HANDLE.compareAndSet( currentTail, null, newNode)) { // 成功链接，尝试更新尾指针 TAIL_HANDLE.compareAndSetRelease( this, currentTail, newNode ); return; } } else { // 帮助其他线程推进尾指针 TAIL_HANDLE.compareAndSet( this, currentTail, tailNext ); } } } } /** * 出队操作 */ public E dequeue() { while (true) { Node<E> currentHead = (Node<E>) HEAD_HANDLE.getAcquire(this); Node<E> currentTail = (Node<E>) TAIL_HANDLE.getAcquire(this); Node<E> headNext = (Node<E>) NEXT_HANDLE.getAcquire(currentHead); // 检查队列状态 if (currentHead == (Node<E>) HEAD_HANDLE.getVolatile(this)) { if (currentHead == currentTail) { if (headNext == null) { throw new NoSuchElementException("Queue is empty"); } // 尾指针落后，帮助推进 TAIL_HANDLE.compareAndSet( this, currentTail, headNext ); } else { // 读取要返回的元素 E item = (E) ITEM_HANDLE.getVolatile(headNext); if (item != null) { // 尝试出队 if (HEAD_HANDLE.compareAndSetRelease( this, currentHead, headNext)) { // 清空旧头节点的引用，帮助 GC ITEM_HANDLE.setVolatile(currentHead, null); NEXT_HANDLE.setVolatile(currentHead, null); return item; } } } } } } /** * 安全的出队操作 */ public E dequeueSafe() { while (true) { Node<E> currentHead = (Node<E>) HEAD_HANDLE.getAcquire(this); Node<E> currentTail = (Node<E>) TAIL_HANDLE.getAcquire(this); Node<E> headNext = (Node<E>) NEXT_HANDLE.getAcquire(currentHead); if (currentHead == (Node<E>) HEAD_HANDLE.getVolatile(this)) { if (currentHead == currentTail) { if (headNext == null) { return null; // 队列为空 } // 帮助推进尾指针 TAIL_HANDLE.compareAndSet( this, currentTail, headNext ); } else { E item = (E) ITEM_HANDLE.getVolatile(headNext); if (item != null && HEAD_HANDLE.compareAndSet( this, currentHead, headNext)) { // 清理 ITEM_HANDLE.setRelease(currentHead, null); NEXT_HANDLE.setRelease(currentHead, null); return item; } } } } } /** * 查看队首元素 */ public E peek() { while (true) { Node<E> currentHead = (Node<E>) HEAD_HANDLE.getAcquire(this); Node<E> headNext = (Node<E>) NEXT_HANDLE.getAcquire(currentHead); if (currentHead == (Node<E>) HEAD_HANDLE.getVolatile(this)) { if (headNext == null) { return null; } E item = (E) ITEM_HANDLE.getAcquire(headNext); if (item != null) { return item; } } } } /** * 队列是否为空 */ public boolean isEmpty() { Node<E> currentHead = (Node<E>) HEAD_HANDLE.getOpaque(this); Node<E> currentTail = (Node<E>) TAIL_HANDLE.getOpaque(this); return currentHead == currentTail && NEXT_HANDLE.getOpaque(currentHead) == null; } /** * 批量入队 */ public void enqueueAll(E[] items) { if (items == null || items.length == 0) { return; } // 构建本地链表 Node<E> first = new Node<>(items[0]); Node<E> last = first; for (int i = 1; i < items.length; i++) { Node<E> node = new Node<>(items[i]); NEXT_HANDLE.setRelease(last, node); last = node; } Node<E> currentTail; Node<E> tailNext; while (true) { currentTail = (Node<E>) TAIL_HANDLE.getAcquire(this); tailNext = (Node<E>) NEXT_HANDLE.getAcquire(currentTail); if (currentTail == (Node<E>) TAIL_HANDLE.getVolatile(this)) { if (tailNext == null) { if (NEXT_HANDLE.compareAndSet( currentTail, null, first)) { // 更新尾指针 TAIL_HANDLE.compareAndSetRelease( this, currentTail, last ); return; } } else { // 帮助推进尾指针 TAIL_HANDLE.compareAndSet( this, currentTail, tailNext ); } } } } }
2. 无锁双端队列
java
复制
下载
/** * 无锁双端队列 * 基于 CAS 实现的双向链表 */ public class LockFreeDeque<E> { private static class Node<E> { volatile E item; volatile Node<E> prev; volatile Node<E> next; Node(E item) { this.item = item; } } /** * 哑节点 */ private final Node<E> sentinel = new Node<>(null); /** * 队首指针（指向第一个真实节点） */ private volatile Node<E> head = sentinel; /** * 队尾指针（指向最后一个真实节点） */ private volatile Node<E> tail = sentinel; /** * VarHandle 声明 */ private static final VarHandle HEAD_HANDLE; private static final VarHandle TAIL_HANDLE; private static final VarHandle NEXT_HANDLE; private static final VarHandle PREV_HANDLE; private static final VarHandle ITEM_HANDLE; static { try { MethodHandles.Lookup lookup = MethodHandles.lookup(); HEAD_HANDLE = lookup.findVarHandle( LockFreeDeque.class, "head", Node.class ); TAIL_HANDLE = lookup.findVarHandle( LockFreeDeque.class, "tail", Node.class ); NEXT_HANDLE = lookup.findVarHandle( Node.class, "next", Node.class ); PREV_HANDLE = lookup.findVarHandle( Node.class, "prev", Node.class ); ITEM_HANDLE = lookup.findVarHandle( Node.class, "item", Object.class ); } catch (Exception e) { throw new Error(e); } } public LockFreeDeque() { // 初始化双向链表 NEXT_HANDLE.setRelease(sentinel, sentinel); PREV_HANDLE.setRelease(sentinel, sentinel); } /** * 从头部添加 */ public void addFirst(E item) { if (item == null) throw new NullPointerException(); Node<E> newNode = new Node<>(item); Node<E> currentHead; do { currentHead = (Node<E>) HEAD_HANDLE.getAcquire(this); Node<E> next = (Node<E>) NEXT_HANDLE.getAcquire(currentHead); // 设置新节点的前后指针 NEXT_HANDLE.setRelease(newNode, next); PREV_HANDLE.setRelease(newNode, currentHead); // 更新原头节点的后指针 } while (!NEXT_HANDLE.compareAndSet( currentHead, next, newNode )); // 更新新头节点 HEAD_HANDLE.compareAndSetRelease(this, currentHead, newNode); } /** * 从尾部添加 */ public void addLast(E item) { if (item == null) throw new NullPointerException(); Node<E> newNode = new Node<>(item); Node<E> currentTail; do { currentTail = (Node<E>) TAIL_HANDLE.getAcquire(this); Node<E> prev = (Node<E>) PREV_HANDLE.getAcquire(currentTail); // 设置新节点的前后指针 PREV_HANDLE.setRelease(newNode, prev); NEXT_HANDLE.setRelease(newNode, currentTail); // 更新原尾节点的前指针 } while (!PREV_HANDLE.compareAndSet( currentTail, prev, newNode )); // 更新新尾节点 TAIL_HANDLE.compareAndSetRelease(this, currentTail, newNode); } /** * 移除头部元素 */ public E removeFirst() { Node<E> currentHead; Node<E> nextNode; do { currentHead = (Node<E>) HEAD_HANDLE.getAcquire(this); nextNode = (Node<E>) NEXT_HANDLE.getAcquire(currentHead); if (nextNode == sentinel) { return null; // 队列为空 } Node<E> nextNext = (Node<E>) NEXT_HANDLE.getAcquire(nextNode); // 跳过要移除的节点 } while (!NEXT_HANDLE.compareAndSet( currentHead, nextNode, nextNext )); // 更新头部 HEAD_HANDLE.compareAndSetRelease(this, currentHead, nextNode); // 清理移除的节点 E item = (E) ITEM_HANDLE.getAndSet(nextNode, null); NEXT_HANDLE.setRelease(nextNode, null); PREV_HANDLE.setRelease(nextNode, null); return item; } /** * 移除尾部元素 */ public E removeLast() { Node<E> currentTail; Node<E> prevNode; do { currentTail = (Node<E>) TAIL_HANDLE.getAcquire(this); prevNode = (Node<E>) PREV_HANDLE.getAcquire(currentTail); if (prevNode == sentinel) { return null; // 队列为空 } Node<E> prevPrev = (Node<E>) PREV_HANDLE.getAcquire(prevNode); // 跳过要移除的节点 } while (!PREV_HANDLE.compareAndSet( currentTail, prevNode, prevPrev )); // 更新尾部 TAIL_HANDLE.compareAndSetRelease(this, currentTail, prevNode); // 清理移除的节点 E item = (E) ITEM_HANDLE.getAndSet(prevNode, null); NEXT_HANDLE.setRelease(prevNode, null); PREV_HANDLE.setRelease(prevNode, null); return item; } }
篇幅限制下面就只能给大家展示小册部分内容了。整理了一份核心面试笔记包括了：Java面试、Spring、JVM、MyBatis、Redis、MySQL、并发编程、微服务、Linux、Springboot、SpringCloud、MQ、Kafc
需要全套面试笔记及答案
【点击此处即可/免费获取】
四、无锁哈希表实现
1. 无锁哈希表基础实现
java
复制
下载
import java.lang.invoke.MethodHandles; import java.lang.invoke.VarHandle; import java.util.function.Function; /** * 无锁哈希表实现 * 使用开放寻址法和 CAS 操作 */ public class LockFreeHashTable<K, V> { /** * 哈希表条目 */ private static class Entry<K, V> { final K key; volatile V value; volatile int hash; // key 的哈希值缓存 Entry(K key, V value, int hash) { this.key = key; this.value = value; this.hash = hash; } } /** * 哈希表桶数组 */ private volatile Entry<K, V>[] table; /** * 大小（元素个数） */ private volatile int size = 0; /** * 容量阈值（触发扩容） */ private volatile int threshold; /** * VarHandle 声明 */ private static final VarHandle TABLE_HANDLE; private static final VarHandle SIZE_HANDLE; private static final VarHandle ENTRY_VALUE_HANDLE; private static final VarHandle ENTRY_HASH_HANDLE; static { try { MethodHandles.Lookup lookup = MethodHandles.lookup(); TABLE_HANDLE = lookup.findVarHandle( LockFreeHashTable.class, "table", Entry[].class ); SIZE_HANDLE = lookup.findVarHandle( LockFreeHashTable.class, "size", int.class ); ENTRY_VALUE_HANDLE = lookup.findVarHandle( Entry.class, "value", Object.class ); ENTRY_HASH_HANDLE = lookup.findVarHandle( Entry.class, "hash", int.class ); } catch (Exception e) { throw new Error(e); } } /** * 默认初始容量 */ private static final int DEFAULT_INITIAL_CAPACITY = 16; /** * 负载因子 */ private static final float LOAD_FACTOR = 0.75f; /** * 空键标记（用于标记删除的条目） */ private static final Object TOMBSTONE = new Object(); @SuppressWarnings("unchecked") public LockFreeHashTable() { table = (Entry<K, V>[]) new Entry<?, ?>[DEFAULT_INITIAL_CAPACITY]; threshold = (int) (DEFAULT_INITIAL_CAPACITY * LOAD_FACTOR); } /** * 获取值 */ public V get(K key) { int hash = hash(key); Entry<K, V>[] tab = (Entry<K, V>[]) TABLE_HANDLE.getAcquire(this); int index = indexFor(hash, tab.length); // 线性探测 for (int i = 0; i < tab.length; i++) { Entry<K, V> entry = tabAt(tab, index); if (entry == null) { return null; // 未找到 } if (entry.key == TOMBSTONE) { // 跳过已删除的条目 index = nextIndex(index, tab.length); continue; } // acquire 语义读哈希值 int entryHash = (int) ENTRY_HASH_HANDLE.getAcquire(entry); if (entryHash == hash && (entry.key == key || (key != null && key.equals(entry.key)))) { // acquire 语义读值 return (V) ENTRY_VALUE_HANDLE.getAcquire(entry); } index = nextIndex(index, tab.length); } return null; } /** * 插入或更新值 */ public V put(K key, V value) { if (key == null) throw new NullPointerException(); int hash = hash(key); Entry<K, V>[] tab; int index; while (true) { tab = (Entry<K, V>[]) TABLE_HANDLE.getAcquire(this); index = indexFor(hash, tab.length); // 查找现有条目或空位 for (int i = 0; i < tab.length; i++) { Entry<K, V> entry = tabAt(tab, index); if (entry == null) { // 找到空位，尝试插入 if (tryPutNewEntry(tab, index, key, value, hash)) { return null; } // CAS 失败，重试 break; } if (entry.key == TOMBSTONE) { // 尝试复用已删除的位置 if (tryReplaceTombstone(tab, index, key, value, hash)) { return null; } // 失败则继续探测 } // 检查是否为相同 key int entryHash = (int) ENTRY_HASH_HANDLE.getAcquire(entry); if (entryHash == hash && (entry.key == key || key.equals(entry.key))) { // 更新现有值 V oldValue = (V) ENTRY_VALUE_HANDLE.getAcquire(entry); if (ENTRY_VALUE_HANDLE.compareAndSet( entry, oldValue, value)) { return oldValue; } // CAS 失败，重试 break; } index = nextIndex(index, tab.length); } // 检查是否需要扩容 if (needResize()) { resize(); } } } /** * 尝试插入新条目 */ private boolean tryPutNewEntry(Entry<K, V>[] tab, int index, K key, V value, int hash) { Entry<K, V> newEntry = new Entry<>(key, value, hash); // 使用 VarHandle 的 compareAndExchange Entry<K, V> expected = null; Entry<K, V> actual = (Entry<K, V>) TABLE_HANDLE.compareAndExchange( this, tab, tab // 检查表未改变 ); if (actual != tab) { return false; // 表已改变，需要重试 } // CAS 设置数组元素 VarHandle arrayHandle = MethodHandles.arrayElementVarHandle(Entry[].class); if (arrayHandle.compareAndSet(tab, index, null, newEntry)) { // 成功插入，增加大小 incrementSize(); return true; } return false; } /** * 原子增加大小 */ private void incrementSize() { int current; do { current = (int) SIZE_HANDLE.getVolatile(this); } while (!SIZE_HANDLE.compareAndSet(this, current, current + 1)); } /** * 删除键值对 */ public V remove(K key) { int hash = hash(key); Entry<K, V>[] tab; int index; while (true) { tab = (Entry<K, V>[]) TABLE_HANDLE.getAcquire(this); index = indexFor(hash, tab.length); for (int i = 0; i < tab.length; i++) { Entry<K, V> entry = tabAt(tab, index); if (entry == null) { return null; // 未找到 } if (entry.key == TOMBSTONE) { index = nextIndex(index, tab.length); continue; } int entryHash = (int) ENTRY_HASH_HANDLE.getAcquire(entry); if (entryHash == hash && (entry.key == key || key.equals(entry.key))) { // 获取当前值 V oldValue = (V) ENTRY_VALUE_HANDLE.getAcquire(entry); // 标记为已删除（tombstone） if (ENTRY_VALUE_HANDLE.compareAndSet( entry, oldValue, TOMBSTONE)) { // 减少大小 decrementSize(); return oldValue; } // CAS 失败，重试 break; } index = nextIndex(index, tab.length); } } } /** * 原子减少大小 */ private void decrementSize() { int current; do { current = (int) SIZE_HANDLE.getVolatile(this); } while (!SIZE_HANDLE.compareAndSet(this, current, current - 1)); } /** * 计算索引 */ private int indexFor(int hash, int length) { return hash & (length - 1); // 假设 length 是 2 的幂 } /** * 下一个索引（线性探测） */ private int nextIndex(int index, int length) { return (index + 1) & (length - 1); } /** * 哈希函数 */ private int hash(Object key) { int h = key.hashCode(); // 扰动函数，减少碰撞 h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } /** * 获取数组元素 */ @SuppressWarnings("unchecked") private Entry<K, V> tabAt(Entry<K, V>[] tab, int index) { VarHandle arrayHandle = MethodHandles.arrayElementVarHandle(Entry[].class); return (Entry<K, V>) arrayHandle.getVolatile(tab, index); } /** * 检查是否需要扩容 */ private boolean needResize() { int currentSize = (int) SIZE_HANDLE.getOpaque(this); return currentSize >= threshold; } /** * 扩容操作 */ @SuppressWarnings("unchecked") private void resize() { Entry<K, V>[] oldTab = (Entry<K, V>[]) TABLE_HANDLE.getAcquire(this); int oldCap = oldTab.length; if (oldCap >= (1 << 30)) { threshold = Integer.MAX_VALUE; // 不能再扩容 return; } int newCap = oldCap << 1; // 双倍扩容 Entry<K, V>[] newTab = (Entry<K, V>[]) new Entry<?, ?>[newCap]; // 尝试 CAS 设置新表 if (TABLE_HANDLE.compareAndSet(this, oldTab, newTab)) { // 重新哈希所有元素 rehash(oldTab, newTab); threshold = (int) (newCap * LOAD_FACTOR); } } /** * 重新哈希 */ private void rehash(Entry<K, V>[] oldTab, Entry<K, V>[] newTab) { for (Entry<K, V> entry : oldTab) { if (entry != null && entry.key != TOMBSTONE) { int newIndex = indexFor(entry.hash, newTab.length); // 插入到新表 while (true) { Entry<K, V> existing = tabAt(newTab, newIndex); if (existing == null) { VarHandle arrayHandle = MethodHandles.arrayElementVarHandle(Entry[].class); if (arrayHandle.compareAndSet( newTab, newIndex, null, entry)) { break; } } newIndex = nextIndex(newIndex, newTab.length); } } } } /** * 计算大小（近似值） */ public int size() { return (int) SIZE_HANDLE.getAcquire(this); } /** * 使用 computeIfAbsent 模式 */ public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) { V value = get(key); if (value != null) { return value; } V newValue = mappingFunction.apply(key); if (newValue == null) { return null; } V result = put(key, newValue); return result != null ? result : newValue; } }
五、性能优化技巧
1. 内存布局优化
java
复制
下载
/** * 缓存行填充，避免伪共享 * 64字节对齐，针对现代CPU缓存行大小 */ public class PaddedAtomicReference<T> { // 前填充 private volatile long p1, p2, p3, p4, p5, p6, p7; // 核心数据 private volatile T value; // 后填充 private volatile long p8, p9, p10, p11, p12, p13, p14, p15; private static final VarHandle VALUE_HANDLE; static { try { VALUE_HANDLE = MethodHandles.lookup() .findVarHandle(PaddedAtomicReference.class, "value", Object.class); } catch (Exception e) { throw new Error(e); } } public boolean compareAndSet(T expected, T update) { return VALUE_HANDLE.compareAndSet(this, expected, update); } @SuppressWarnings("unchecked") public T get() { return (T) VALUE_HANDLE.getAcquire(this); } public void set(T newValue) { VALUE_HANDLE.setRelease(this, newValue); } } /** * 使用 @Contended 注解（JDK 8+） */ import jdk.internal.vm.annotation.Contended; public class ContendedCounter { @Contended // 防止伪共享 private volatile long value1 = 0; @Contended private volatile long value2 = 0; private static final VarHandle VALUE1_HANDLE; private static final VarHandle VALUE2_HANDLE; static { try { VALUE1_HANDLE = MethodHandles.lookup() .findVarHandle(ContendedCounter.class, "value1", long.class); VALUE2_HANDLE = MethodHandles.lookup() .findVarHandle(ContendedCounter.class, "value2", long.class); } catch (Exception e) { throw new Error(e); } } public void increment1() { long current; do { current = (long) VALUE1_HANDLE.getAcquire(this); } while (!VALUE1_HANDLE.compareAndSet(this, current, current + 1)); } }
2. 批量操作优化
java
复制
下载
/** * 批量计数器，减少 CAS 竞争 */ public class BatchCounter { private static final int BATCH_SIZE = 64; // 线程本地计数器 private static final ThreadLocal<ThreadLocalCounter> COUNTERS = ThreadLocal.withInitial(ThreadLocalCounter::new); // 全局计数器 private volatile long globalCount = 0; private static final VarHandle GLOBAL_COUNT_HANDLE; static { try { GLOBAL_COUNT_HANDLE = MethodHandles.lookup() .findVarHandle(BatchCounter.class, "globalCount", long.class); } catch (Exception e) { throw new Error(e); } } /** * 线程本地计数器 */ private static class ThreadLocalCounter { private long localCount = 0; private int batch = 0; public void increment() { localCount++; batch++; // 达到批量大小时，同步到全局 if (batch >= BATCH_SIZE) { flushToGlobal(); } } private void flushToGlobal() { if (localCount > 0) { long currentGlobal; do { currentGlobal = (long) GLOBAL_COUNT_HANDLE.getAcquire(BatchCounter.this); } while (!GLOBAL_COUNT_HANDLE.compareAndSet( BatchCounter.this, currentGlobal, currentGlobal + localCount )); localCount = 0; batch = 0; } } } public void increment() { COUNTERS.get().increment(); } public long get() { // 获取全局计数前，先同步所有线程本地计数 COUNTERS.get().flushToGlobal(); // 返回全局计数 return (long) GLOBAL_COUNT_HANDLE.getAcquire(this); } }
六、测试与验证
1. 并发测试框架
java
复制
下载
import java.util.concurrent.*; import java.util.concurrent.atomic.AtomicInteger; public class LockFreeStructureTest { /** * 测试无锁栈 */ public static void testLockFreeStack() throws Exception { LockFreeStack<Integer> stack = new LockFreeStack<>(); int threadCount = 10; int operationsPerThread = 10000; ExecutorService executor = Executors.newFixedThreadPool(threadCount); CyclicBarrier barrier = new CyclicBarrier(threadCount); AtomicInteger pushCount = new AtomicInteger(0); AtomicInteger popCount = new AtomicInteger(0); // 创建测试任务 Runnable task = () -> { try { barrier.await(); // 同时开始 for (int i = 0; i < operationsPerThread; i++) { // 压栈 stack.push(i); pushCount.incrementAndGet(); // 偶尔弹栈 if (i % 3 == 0) { stack.popSafe(); popCount.incrementAndGet(); } } } catch (Exception e) { e.printStackTrace(); } }; // 提交任务 for (int i = 0; i < threadCount; i++) { executor.submit(task); } executor.shutdown(); executor.awaitTermination(1, TimeUnit.MINUTES); // 验证 System.out.println("Push operations: " + pushCount.get()); System.out.println("Pop operations: " + popCount.get()); System.out.println("Final stack size: " + stack.size()); // 清空栈，验证无内存泄漏 Integer item; int remaining = 0; while ((item = stack.popSafe()) != null) { remaining++; } System.out.println("Remaining items after cleanup: " + remaining); assert remaining == pushCount.get() - popCount.get(); } /** * 测试 ABA 防护 */ public static void testABAPrevention() throws Exception { LockFreeStackWithStamped<Integer> stack = new LockFreeStackWithStamped<>(); // 模拟 ABA 场景 stack.push(1); stack.push(2); // 线程1：读取栈顶为2 // 线程2：弹出2，弹出1，压入2（相同值但不同对象） // 线程1：尝试CAS，应该失败（因为有版本号） ExecutorService executor = Executors.newFixedThreadPool(2); Future<?> future1 = executor.submit(() -> { // 线程1：记录栈顶，休眠 Integer top = stack.peek(); try { Thread.sleep(100); // 让线程2有时间操作 } catch (InterruptedException e) { Thread.currentThread().interrupt(); } // 尝试弹栈（应该失败或得到新对象） return stack.pop(); }); Future<?> future2 = executor.submit(() -> { // 线程2：制造ABA场景 stack.pop(); // 弹出2 stack.pop(); // 弹出1 stack.push(2); // 压入新2（不同Node对象） return null; }); future2.get(); Object result = future1.get(); System.out.println("ABA test result: " + result); // 验证结果应该是新压入的2，而不是原来的2 executor.shutdown(); } /** * 性能对比测试 */ public static void performanceComparison() { int iterations = 1000000; // 测试 ConcurrentLinkedQueue Queue<Integer> clq = new ConcurrentLinkedQueue<>(); long start = System.nanoTime(); for (int i = 0; i < iterations; i++) { clq.offer(i); if (i % 2 == 0) { clq.poll(); } } long clqTime = System.nanoTime() - start; // 测试我们的无锁队列 LockFreeQueue<Integer> lfq = new LockFreeQueue<>(); start = System.nanoTime(); for (int i = 0; i < iterations; i++) { lfq.enqueue(i); if (i % 2 == 0) { lfq.dequeueSafe(); } } long lfqTime = System.nanoTime() - start; System.out.println("ConcurrentLinkedQueue time: " + clqTime / 1e6 + " ms"); System.out.println("LockFreeQueue time: " + lfqTime / 1e6 + " ms"); System.out.println("Speedup: " + (double) clqTime / lfqTime); } public static void main(String[] args) throws Exception { System.out.println("Testing LockFreeStack..."); testLockFreeStack(); System.out.println("\nTesting ABA Prevention..."); testABAPrevention(); System.out.println("\nPerformance Comparison..."); performanceComparison(); } }
七、最佳实践与注意事项
1. 内存语义选择指南
java
复制
下载
public class MemorySemanticsGuide { /** * VarHandle 内存语义选择： * * 1. getAcquire / setRelease * - 用于建立 happens-before 关系 * - 适用于发布-订阅模式 * * 2. getVolatile / setVolatile * - 完全的 volatile 语义 * - 确保所有线程的可见性 * * 3. getOpaque / setOpaque * - 仅保证原子性，不保证内存顺序 * - 性能最好，适用于统计计数等场景 * * 4. compareAndSet * - 具有 volatile 语义的 CAS * - 适用于无锁算法 * * 5. weakCompareAndSet * - 可能更高效，但可能假失败 * - 适用于高竞争场景 */ // 示例：正确的内存语义使用 class CorrectUsage { private volatile Data data; private static final VarHandle DATA_HANDLE; void publisher() { Data newData = new Data(); // 初始化数据 newData.init(); // release 语义发布 DATA_HANDLE.setRelease(this, newData); } void consumer() { // acquire 语义获取 Data currentData = (Data) DATA_HANDLE.getAcquire(this); if (currentData != null) { // 可以安全地读取数据内容 currentData.process(); } } } }
篇幅限制下面就只能给大家展示小册部分内容了。整理了一份核心面试笔记包括了：Java面试、Spring、JVM、MyBatis、Redis、MySQL、并发编程、微服务、Linux、Springboot、SpringCloud、MQ、Kafc
需要全套面试笔记及答案
【点击此处即可/免费获取】
2. 常见陷阱与解决方法
java
复制
下载
public class CommonPitfalls { /** * 陷阱1：忘记 volatile 修饰符 * 解决：必须用 volatile 修饰 VarHandle 操作的字段 */ class Pitfall1 { private int value; // 错误：缺少 volatile // VarHandle 操作仍能工作，但内存语义不正确 } /** * 陷阱2：错误的初始化顺序 * 解决：使用静态初始化块，确保线程安全初始化 */ class Pitfall2 { // 正确做法 private static final VarHandle HANDLE; static { try { HANDLE = MethodHandles.lookup() .findVarHandle(Pitfall2.class, "field", int.class); } catch (Exception e) { throw new Error(e); } } } /** * 陷阱3：ABA 问题 * 解决：使用版本号或指针标记 */ class Pitfall3 { // 使用带版本号的引用 private static class VersionedRef<T> { final T ref; final long version; // ... } } /** * 陷阱4：内存泄漏 * 解决：及时清理无用节点引用 */ class Pitfall4 { void safePop(Node<E> node) { // 弹出后清理引用 node.item = null; node.next = null; // 帮助 GC } } /** * 陷阱5：活锁（live lock） * 解决：引入随机退避或队列机制 */ class Pitfall5 { void operationWithBackoff() { int attempts = 0; while (!tryOperation()) { attempts++; if (attempts > MAX_ATTEMPTS) { // 退避或抛出异常 exponentialBackoff(attempts); } } } private void exponentialBackoff(int attempts) { try { Thread.sleep((1L << Math.min(attempts, 10))); // 指数退避 } catch (InterruptedException e) { Thread.currentThread().interrupt(); } } } }
3. 性能监控与调优
java
复制
下载
import java.util.concurrent.atomic.LongAdder; public class PerformanceMonitor { /** * 性能统计 */ public static class Stats { // 使用 LongAdder 代替 AtomicLong，减少竞争 private final LongAdder operations = new LongAdder(); private final LongAdder casFailures = new LongAdder(); private final LongAdder retries = new LongAdder(); // 使用 VarHandle 保护时间戳 private volatile long startTime = 0; private static final VarHandle START_TIME_HANDLE; static { try { START_TIME_HANDLE = MethodHandles.lookup() .findVarHandle(Stats.class, "startTime", long.class); } catch (Exception e) { throw new Error(e); } } public void recordOperation() { operations.increment(); } public void recordCASFailure() { casFailures.increment(); } public void recordRetry() { retries.increment(); } public void startTiming() { START_TIME_HANDLE.setVolatile(this, System.nanoTime()); } public long getElapsedNanos() { long start = (long) START_TIME_HANDLE.getAcquire(this); return System.nanoTime() - start; } public void printStats() { long ops = operations.sum(); long failures = casFailures.sum(); long retryCount = retries.sum(); double failureRate = ops > 0 ? (double) failures / ops : 0; System.out.printf("Operations: %,d%n", ops); System.out.printf("CAS failures: %,d (%.2f%%)%n", failures, failureRate * 100); System.out.printf("Retries: %,d%n", retryCount); System.out.printf("Elapsed time: %.2f ms%n", getElapsedNanos() / 1e6); if (ops > 0) { System.out.printf("Throughput: %.2f ops/ms%n", ops / (getElapsedNanos() / 1e6)); } } } /** * 监控装饰器 */ public static class MonitoredLockFreeStack<E> extends LockFreeStack<E> { private final Stats stats = new Stats(); @Override public void push(E item) { stats.startTiming(); int attempts = 0; while (true) { attempts++; stats.recordOperation(); try { super.push(item); return; } catch (Exception e) { stats.recordCASFailure(); if (attempts > 10) { stats.recordRetry(); // 指数退避 try { Thread.sleep(1L << Math.min(attempts - 10, 4)); } catch (InterruptedException ie) { Thread.currentThread().interrupt(); throw new RuntimeException(ie); } } } } } public Stats getStats() { return stats; } } }
八、总结
VarHandle 无锁数据结构优势：
- 类型安全 - 编译期检查，避免 Unsafe 的类型错误
- 内存语义明确 - 清晰的 acquire/release/volatile 语义
- 性能优异 - 接近原生操作的性能
- 平台兼容 - 在 AOT 编译和未来 JDK 版本中支持更好
- 代码可维护 - 标准 API，易于理解和维护
使用建议：
- 对于新建项目，优先使用 VarHandle 而不是 Unsafe
- 理解不同内存语义的适用场景
- 注意处理 ABA 问题和内存泄漏
- 进行充分的并发测试和性能测试
- 结合缓存行填充等优化技巧
通过 VarHandle 实现的无锁数据结构，可以在保证线程安全的同时，获得接近最优的性能表现，是现代 Java 并发编程的重要工具。
