Java：搜索对象的 ArrayList 以匹配 id 但字段不同的有效方法

Question

假设我有一个很大的 (> 100,000,000) ArrayList of Person，其中 Person 定义为：

class Person {
    public int id;
    public String name;
}

我正在尝试编写一种方法，hasDuplicatePersonsWithDifferentNames() 如果 ArrayList 包含具有相同 ID 但名称不同的元素，则 return 会 true。例如：

这会 return 正确，因为有两个相同的 ID 但名称不同

ArrayList<Person> people = new ArrayList<Person>();
people.add(new Person(1, "bob");
people.add(new Person(1, "alice");

这会 return 错误，因为虽然有两个相同的 ID，但它们共享相同的名称

ArrayList<Person> people = new ArrayList<Person>();
people.add(new Person(1, "bob");
people.add(new Person(1, "bob");

我在想会有一些方法可以利用 Java Streams，它被认为是高效的，甚至可能是并发的。但我找不到任何一个例子。我知道我可以使用字典并在 O(n) time/space 中解决这个问题，但我相信使用 streams/concurrency 我可以节省 space 的复杂性。

Answer 1

问题是你的数据结构不对。

如果您使用列表，则在列表中搜索某些内容涉及迭代列表。在您的情况下，这意味着（可能）测试列表中的每个元素。全部一亿。

使用流或并发将无济于事。您的代码仍然需要测试 1 亿个条目。（好吧，并行搜索可以让你的速度提高 P 倍，其中 P 是可用的物理核心数。但是 P 会很小而且不变。）

所以如果你想比 O(N) 做得更好......其中 N 是一个非常大的数字......你需要一个支持基于元素字段的查找的数据结构。这里有一些可能性：

使用 Map<Integer, Person> 并将其填充为从 id 到 Person 的映射。问题是 Map 只能为每个键保存一个值，因此您实际上不能同时在映射中存储 Bob 和 Alice。（但这可能是比您目前正在做的更好的解决方案。）

如果你使用HashMap，插入删除和查找等操作是O(1)。
使用多地图。 Apache Commons 和 Guava 都提供多映射类，或者你可以给我们一个 Map<Integer, List<Person>>.
以上两者都比 ArrayList 使用更多的内存。另一种选择是让您的列表按 Person 对象的 id 值排序，以便您可以执行二进制搜索。

Java: Efficient way to search ArrayList of objects for matching ids but different fields