java - 具有快速查找功能的排序集(与 HashSet 一样快？)

Question

我正在寻找某种可以满足这两个要求的集合数据结构:

1. 已排序
2. O(1) 查找

这就是我到目前为止所得到的，但我真的希望那里有一个现有的、不那么笨拙的数据结构。

/**
 * This MUST support both 
 * (1) Looking up by A - O(n)
 * (2) Iteration by sorted Foo<A, B>
 */
public class MySet<Foo<A, B>> extends TreeSet<Foo<A, B>>
{ 
    private Map<A, Foo<A, B>> temp = new HashMap<A, Foo<A, B>>();

    public Foo<A, B> getNode(A a)
    {
       return temp.get(a);
    }

    @Override
    public boolean add(Foo<A, B> foo)
    {
       temp.put(foo.getA(), foo);
       return super.add(foo);
    }
}

我的 Foo 类如下所示:

public class Foo<A, B>
{
    private A a; //Can NEVER be null
    private B b; //Can NEVER be null

    //... constructor and stuff omitted 

    public int compareTo(Foo<A, B> that)
    {
        if (this.equals(that))
           return 0;

        //Compare by a first
        int ret = this.a.compareTo(that);
        if (ret == 0)
            return 0;

        //Compare by b
        return this.b.compareTo(that.b);            
    }

    public boolean equals(Object obj)
    {
        if (!(obj instanceof Foo))
            return false;

        Foo rhs = (Foo) obj;

        return this.a.equals(rhs.a) && this.b.equals(rhs.b);
    }
}

更新:

这是我的集合的一个用例:

MySet<Foo<SomeA, SomeB>> mySet = getTheData(); //getTheData() returns a set with a bunch of Foo objects

SomeA a = getA(); //getA() returns some instance of SomeA that I'm interested in

我希望能够检查集合并检索 Foo 对象(如果存在)，这样 Foo.getA() == a;

mySet.getNode(a); 

Answer 1

您可以使用一些额外的空间来获取它。所以你需要一个 HashSet。此外，每个元素将指向排序顺序中的下一个值。假设您有键 1、3、5、10，并且您正在使用线性探测。

value array   =  [3, 5, null, null, 10,   1];
pointer array =  [1, 4, null, null, null, 0];

因此值数组包含值。哈希函数决定值的去向。因此在上面的示例中，h(1) = 5(1 转到索引 5)、h(3) = 0、h(5) = 1 和 h(10) = 4。索引 2、3 具有空值( future 元素的开放空间)。指针数组表示哪个元素在排序顺序中跟在当前元素之后。假设我们正在执行 set.contains(3)，它将导致计算 h(3)(将产生 0)，并且我们知道该元素存在于集合中。如果我们想要根据排序顺序排列元素集中的下一个元素，我们会查看指针数组中的值。因此，对于值 3(在值数组中的位置 0)，我们通过查找指针数组(pointer_array[0]，即 1)中的索引，然后查找 value_array 来获取排序顺序中的下一个元素[1], 即 5.

这是一个非常常见的实现。 Java的LinkedHashMap通常用作LRU缓存，实现为 HashMap +键的双向链表。双向链表中的键按访问顺序排列。

在您的情况下，当您插入一个元素时，您需要调整非常慢的指针数组。你必须做一个线性扫描。 如果这不是只读的，您可以使用以下方法。

在你的数据结构中，有一个 hashset 和一个 avl 树，一个红黑树或任何其他平衡二叉树。每当您进行 containsKey 测试时，它都是 O(1)。每当您进行枚举时，您都可以使用二叉树按排序顺序在线性时间内遍历它们。每当您插入一个新元素时，您也会将它同时插入到二叉树和 HashSet 中。当你删除时，你从哈希集和二叉树中删除元素。所以删除和插入变为 O(log n)。