java - Hashtable<ArrayList<String>,boolean> 的 .contains() 方法比 ArrayList<ArrayList<String>> 快多少？

Question

我基本上是在做以下事情:

• 将数据库表中的整行数据作为字符串转储到 ArrayList< ArrayList< String>> 中.

• 对另一个数据库表做同样的事情。

• 查找所有行 ArrayList< String>在第二个数据库中的第一个数据库中遍历它并执行 a.contains(b.get(i)) .如果包含是true然后我做a.remove(b.get(i))

现在，如果我使用 Hashtable< Arraylist< String>> 而不是上面提到的使用 a.containsKey(i.getKey()) 的 ArrayList，会快多少？ i 是 b 上的迭代器，然后使用 i.remove 删除？是否足以进行更改？

此外，使用 Hashmap 会更谨慎吗？如果是，为什么……

Answer 1

我自下而上的回答:

• Hashtable 和 HashMap 之间的区别已在 Differences between HashMap and Hashtable? 中(彻底)讨论过。简短摘要:HashMap 更高效，应该代替 Hashtable 使用。

• 在散列数据结构中查找数据(contains() 和 remove() 操作)的阶数为 O(log2) - 也就是说，它与数据点数量的 2 对数成正比在结构中。如果有 4 个数据元素，则需要 X 时间；如果有 8 个元素，则需要 2X 时间，16 个元素，则需要 3X 时间，依此类推。哈希结构的数据访问时间增长非常缓慢。
  在列表中查找数据的顺序为 O(N) - 即与列表中元素的数量成正比。 1个元素需要Y时间，2个元素需要2Y时间，4个元素需要4Y时间等等。所以时间消耗随着列表的大小线性增长。
  
  

• 因此:如果您必须从数据结构中随机查找大量元素，哈希数据结构是最佳选择，只要:
  -数据有一个不错的 hashCode() 实现(ArrayList 的那个是好的)
  - 数据有 hashCode() 和 equals() 实现相互匹配，即。如果 a.equals(b) 那么 a.hashCode() == b.hashCode()。 ArrayList 也是如此。

• 另一方面，如果您正在处理有序 数据，还有其他算法可以显着减少搜索和删除时间。如果数据库中的数据已编制索引，那么在获取数据时使用 ORDER BY 可能是值得的，然后使用算法来排序数据。

总结一下:使用 HashMap 而不是 ArrayList 来获取列表 a。

我写了一个小程序来对问题进行基准测试。结果优先:程序在 Core i5 2.40 GHz CPU 上运行于 Sun JVM 1.6.0_41 for Windows 7，32 位。打印输出:

For 1000 words: List: 1 ms, Map: 2 ms
For 5000 words: List: 15 ms, Map: 12 ms
For 10000 words: List: 57 ms, Map: 12 ms
For 20000 words: List: 217 ms, Map: 37 ms
For 30000 words: List: 485 ms, Map: 45 ms
For 50000 words: List: 1365 ms, Map: 61 ms

性能特征在像这样的简单测试中表现得很好。我运行带有更多数据的 map 版本并得到以下信息:

For 100000 words: List: - ms, Map: 166 ms
For 500000 words: List: - ms, Map: 1130 ms
For 1000000 words: List: - ms, Map: 3540 ms

最后是基准测试代码:

public void benchmarkListVersusMap() {
    for (int count : new int[]{1000, 5000, 10000, 20000, 30000, 50000}) {
        // Generate random sample data
        List<List<String>> words = generateData(count, 10, count);

        // Create ArrayList
        List<List<String>> list = new ArrayList<List<String>>();
        list.addAll(words);

        // Create HashMap
        Map<List<String>, Boolean> map = new HashMap<List<String>, Boolean>();
        for (List<String> row : words) {
            map.put(row, true);
        }

        // Measure:
        long timer = System.currentTimeMillis();
        for (List<String> row: words) {
            if (list.contains(row)) {
                list.remove(row);
            }
        }
        long listTime = System.currentTimeMillis() - timer;
        timer = System.currentTimeMillis();
        for (List<String> row : words) {
            if (map.containsKey(row)) {
                map.remove(row);
            }
        }
        long mapTime = System.currentTimeMillis() - timer;
        System.out.printf("For %s words: List: %s ms, Map: %s ms\n", count, listTime, mapTime);
    }
}

private List<List<String>> generateData(int rows, int cols, int noOfDifferentWords) {
    List<List<String>> list = new ArrayList<List<String>>(rows);
    List<String> dictionary = generateRandomWords(noOfDifferentWords);
    Random rnd = new Random();
    for (int row = 0; row < rows; row++) {
        List<String> l2 = new ArrayList<String>(cols);
        for (int col = 0; col < cols; col++) {
            l2.add(dictionary.get(rnd.nextInt(noOfDifferentWords)));
        }
        list.add(l2);
    }
    return list;
}

private static final String CHARS = "abcdefghijklmnopqrstuvwxyz0123456789";
private List<String> generateRandomWords(int count) {
    Random rnd = new Random();
    List<String> list = new ArrayList<String>(count);
    while (list.size() < count) {
        StringBuilder sb = new StringBuilder(20);
        for (int i = 0; i < 10; i++) {
            sb.append(CHARS.charAt(rnd.nextInt(CHARS.length())));
        }
        list.add(sb.toString());
    }
    return list;
}