小红书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 无锁数据结构优势：

使用建议：

• 对于新建项目，优先使用 VarHandle 而不是 Unsafe

• 理解不同内存语义的适用场景

• 注意处理 ABA 问题和内存泄漏

• 进行充分的并发测试和性能测试

• 结合缓存行填充等优化技巧

通过 VarHandle 实现的无锁数据结构，可以在保证线程安全的同时，获得接近最优的性能表现，是现代 Java 并发编程的重要工具。