Java 锁定数组范围

Question

我正在尝试实现一个基于数组的无锁二叉搜索树。为了使其同时工作，我应该在方法中锁定一系列数组。我怎样才能实现它？

public int getIndex(int data){
        int index = 1;
        while(index<this.capacity && this.array[index] != 0){
            if(data < this.array[index])
                index = index *2;
            else if (data> this.array[index])
                index = index * 2 + 1;
            else
                break;
        }

        if(index >= this.capacity)
            return -1;
        else
            return index;
    }



public void insert(int data){
        int index = this.getIndex(data);
        if (index == -1) {
            this.reallocate();
            index = this.getIndex(data);
            this.array[index] = data;

        }
        else {
            if (this.array[index] == 0)
                this.array[index] = data;
        }

    }

我正在了解在 getIndex 方法中放置数据的位置并插入它。因此，在 getIndex 中，我应该锁定正在迭代的数组的一部分。

Answer 1

如果你的树在插入后不能 self 平衡，它可能会增长到巨大的尺寸(按顺序插入从 1 到 100 的整数，将需要一个大小为 2^100 的数组；你没有那么多的 RAM)。所以我假设你的树做了一些重新平衡以控制内存大小。

要查找键，您需要遍历根节点并最多遍历 log(size-of-array) 个附加节点。如果涉及重新平衡，则该路径中的所有节点(直到根节点)都可能会重新洗牌。由于根可以更改，因此不可能同时发生两次写入(其中写入是插入或删除)。此外，重新平衡涉及移动数组 block ；更换根需要移动整棵树的一半，这是非常昂贵的。我强烈怀疑，由于担心性能足以考虑部分锁定后备数组的部分，您希望在树上进行昂贵的 O(n) 操作。

读取可以更加并发:它们只沿着树向下走一次，并且不会向上重新平衡任何内容(如果您不介意内存不足，非重新平衡树也会在写入时表现出这种情况，不包括删除)。可以有任意数量的并发读取操作同时工作。而且您可以添加内容，而不必担心读取错误 - 所有读取都会找到他们正在寻找的内容，或者如果在另一个线程写入它们时稍微晚了一些，则可能偶尔返回“未找到”。使用 volatile数组，否则其他线程可能永远不会看到更改。

还有一个关于非重新平衡树和delete()的特殊情况。删除(可能)影响直接向下路径之外的节点(请参阅 pictures here )。使用数组移动(子)树是昂贵的(线性的)；您打算移动的位需要被锁定，因为在移动期间可能会进行无效读取。尽管如此，我还是强烈怀疑你不会实现Delete()，因为效率很差。