使用 VarHandle 实现内存安全的无锁数据结构

二、无锁栈实现（Treiber Stack）

1. 完整的无锁栈实现

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 失败，重置自旋计数
        }
    }
}

2. 带 ABA 问题防护的增强版栈

/**
 * 使用指针标记解决 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. 完整的无锁队列实现

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. 无锁双端队列

/**
 * 无锁双端队列
 * 基于 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;
    }
}

四、无锁哈希表实现

1. 无锁哈希表基础实现

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. 内存布局优化

/**
 * 缓存行填充，避免伪共享
 * 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. 批量操作优化

/**
 * 批量计数器，减少 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. 并发测试框架

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. 内存语义选择指南

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();
            }
        }
    }
}

2. 常见陷阱与解决方法

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. 性能监控与调优

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

1. 类型安全 - 编译期检查，避免 Unsafe 的类型错误
2. 内存语义明确 - 清晰的 acquire/release/volatile 语义
3. 性能优异 - 接近原生操作的性能
4. 平台兼容 - 在 AOT 编译和未来 JDK 版本中支持更好
5. 代码可维护 - 标准 API，易于理解和维护

使用建议：

• 对于新建项目，优先使用 VarHandle 而不是 Unsafe
• 理解不同内存语义的适用场景
• 注意处理 ABA 问题和内存泄漏
• 进行充分的并发测试和性能测试
• 结合缓存行填充等优化技巧

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