在 Set 中查找元素的最有效方法

Question

我有这个人 class:

public class Person implements Comparable<Person> {
    private int id;
    @Override
    public int hashCode() {
        return id;
    }

    @Override
    public boolean equals(Object obj) {
        Person other = (Person) obj;
        return id == other.id;
    }

    @Override
    public int compareTo(Person o) {
        return Integer.compare(id, o.id);
    }
}

我有 TreeSet 的人。我需要在 TreeSet.

中实现方法 findPersonById(int id)

我是这样做的：

public Person find(int id) {
    List<Person> personList = new ArrayList(idTreeSet);
    Person pattern = new Person(id);
    int index = Collections.binarySearch(personList, pattern);
    return index < 0 ? null : personList.get(index);
}

现在 find 方法的效率是 O(n)，因为它需要将所有元素从 TreeSet 复制到 ArrayList。

但是有没有更有效的方法来实现这个方法呢？

我不需要地图。我有兴趣在没有地图的情况下解决它。

Answer 1

因为TreeSet是一个NavigableSet，你可以使用TreeSet.subSet，它利用关于元素顺序的知识来提取尽可能接近元素的元素范围您感兴趣的是：

Person pattern = new Person(id);

return
    // Get the Persons between pattern (inclusive) and pattern (inclusive).
    // In other words: all the Persons with id equal to the input,
    // of which there are zero or one.
    idTreeSet.subSet(pattern, true, pattern, true).stream()
        .findFirst()
        .orElse(null);

Answer 2

既然你准备分配一个临时的Person对象，你可以这样做：

public Person find(int id) {
    Person temp = new Person(id);
    Person candidate = idTreeSet.ceiling(temp);
    return temp.equals(candidate) ? candidate : null;
}

这是O(logN)。

注意我们这里只创建了一个临时对象。如果我们使用 tailSet 或 subSet 我们将至少创建第二个；即 tailSet 或 subSet 调用返回的 NavigableSet。（查看 TreeSet 实施的幕后情况，看起来会创建更多。）

如果您不需要 TreeSet 的属性，那么使用 HashMap<Integer, Person> 或 HashSet<Person> 将为您提供 O(1) 查找。但在后一种情况下，您需要更改 Person class 以满足 equals / hashCode 合同。

Answer 3

Map<Integer, Person> personsById = new HashMap<>();

肯定是最快的，尽管不是基于树的。用于插入顺序的 LinkedHashMap 将允许一些顺序。

这是更坚固的解决方案。

在 Set 中查找元素的最有效方法

The most efficient method to find an element in Set

java

collections

set

treeset