1

为了便于理解，我试图在这里提出我的要求的简化版本。

我有这门课

public class MyClass {
   private byte[] data1;
   private byte[] data2;
   private long hash1;  // Hash value for data1
   private long hash2;  // Hash value for data2
   // getter and setters }

现在我需要在这个类的 2 个 List 实例之间进行搜索，找到这 2 个实例之间有多少 hash1 匹配，以及所有匹配有多少对应的 hash2 匹配。2 列表将有大约 1000 万个 MyClass 对象。

现在我打算遍历第一个列表并在第二个列表中搜索。有没有一种方法可以通过以任何特定方式排序或排序来优化搜索？我应该对两个列表进行排序还是仅对 1 个列表进行排序？

4

4 回答 4

0

仅第二次排序，首先迭代并在第二次进行二进制搜索，排序 O(nlogn) 并且对 n 项进行二进制搜索 O(nlogn)

或第二次使用哈希集，首先迭代并在第二次搜索，O(n)

于 2012-10-12T18:21:52.813 回答
0

最好的解决方案是迭代没有比这更快的解决方案。您可以创建 Hashmap 并利用 map 不会添加相同的键，但它有自己的创建重载

于 2012-10-12T18:23:46.483 回答
0

如果您必须检查所有元素，我认为您应该遍历第一个列表并为第二个列表创建一个 Hashmap，如 AmitD 所述。

您只需要正确覆盖equals并hashcode在您的MyClass班级中。最后，我会建议你尽可能使用基本类型。例如，对于第一个列表，使用简单数组而不是列表会更好。

此外，在开始时，您可以选择两个列表中的哪一个是较短的（如果大小不同）并迭代该列表。

于 2012-10-12T18:31:57.993 回答
0

我认为您应该为其中一个列表创建一个哈希图（例如list1）-

Map<Long, MyClass> map = new HashMap<Long, MyClass>(list1.size());//specify the capacity
//populate map like - put(myClass.getHash1(), myClass) : for each element in the list

现在只需遍历第二个列表（对两者进行排序没有意义）-

int hash1MatchCount = 0;
int hash2MatchCount = 0;
for(MyClass myClass : list2) {
    MyClass mc = map.get(myClass.getHash1());
    if(mc != null) {
        hash1MatchCount++;
        if(myClass.getHash2() == mc.getHash2) {
            hash2MatchCount++;
        }
    }
}

注意：假设没有关于hash1重复的问题。

于 2012-10-12T18:43:51.820 回答