.contains()方法对于Hashtable <ArrayList <String>,布尔值>比ArrayList <ArrayList <String >>快多少？

Question

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

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

• 为另一个DB表做同样的事情.

• ArrayList< String>通过遍历它并执行操作来查找第二个DB中第一个DB中的所有行a.contains(b.get(i)).如果包含true然后我做a.remove(b.get(i))

现在,如果我使用Hashtable <Arraylist <String >>代替上面提到的ArrayList使用a.containsKey(i.getKey())其中i是迭代器而不是b然后使用i.remove删除,那么会快多少？进行改变是否足够好？

另外,使用Hashmap会更谨慎吗？如果是这样的话......

Answer 1

我自下而上的回答:

• HashMap和HashMap之间的差异已经(彻底)讨论过HashMap和Hashtable之间的区别？.简短摘要:HashMap效率更高,应该用Hashtable代替Hashtable.

• 在散列数据结构中查找数据(contains()和remove()操作)的顺序为O(log2) - 也就是说,它与结构中数据点数的2对数成比例.如果有4个数据元素需要X时间; 如果有8个元素需要2倍时间,16个元素,3倍时间等等.哈希结构的数据访问时间增长非常缓慢.
  查找列表中的数据的顺序为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

在这样的简单测试中,性能特征非常好.我使用更多数据运行地图版本并获得以下内容:

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;
}