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

Question

我有 Person 类：

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。我需要findPersonById(int id)在 TreeSet 中实现方法。

我是这样做的：

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

由于您准备分配一个临时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将创建至少第二个；即or调用NavigableSet返回的值。（在实现的背后，看起来将会创建更多。）tailSetsubSetTreeSet

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