TreeMap或HashMap更快

Question

我正在写一本字典,大量使用String作为键Map<String, Index>.我关心的是哪一个HashMap,并TreeMap会产生更好的(更快)的性能在搜索在地图上的关键？

Answer 1

鉴于没有太多的碰撞,哈希映射将给你o(1)性能(有很多分裂,这可能会降级到潜在的O(n),其中N是任何一个桶中的条目数(colissions)).另一方面,如果您想要某种平衡的树结构来生成O(logN)检索,则使用TreeMaps.所以它真的取决于你的特定用例.但是如果你只想访问元素,不管它们的顺序如何都使用HashMap

Answer 2

public class MapsInvestigation {

public static HashMap<String, String> hashMap = new HashMap<String, String>();
public static TreeMap<String, String> treeMap = new TreeMap<String, String>();
public static ArrayList<String> list = new ArrayList<String>();

static {
    for (int i = 0; i < 10000; i++) {
        list.add(Integer.toString(i, 16));
    }
}


public static void main(String[] args) {
    System.out.println("Warmup populate");
    for (int i = 0; i < 1000; i++) {
        populateSet(hashMap);
        populateSet(treeMap);
    }
    measureTimeToPopulate(hashMap, "HashMap", 1000);
    measureTimeToPopulate(treeMap, "TreeMap", 1000);

    System.out.println("Warmup get");
    for (int i = 0; i < 1000; i++) {
        get(hashMap);
        get(treeMap);
    }
    measureTimeToContains(hashMap, "HashMap", 1000);
    measureTimeToContains(treeMap, "TreeMap", 1000);

}

private static void get(Map<String, String> map) {
    for (String s : list) {
        map.get(s);
    }

}

private static void populateSet(Map<String, String> map) {
    map.clear();
    for (String s : list) {
        map.put(s, s);
    }

}


private static void measureTimeToPopulate(Map<String, String> map, String setName, int reps) {
    long start = System.currentTimeMillis();
    for (int i = 0; i < reps; i++) {
        populateSet(map);
    }
    long finish = System.currentTimeMillis();
    System.out.println("Time to populate " + (reps * map.size()) + " entries in a " + setName + ": " + (finish - start));
}

private static void measureTimeToContains(Map<String, String> map, String setName, int reps) {
    long start = System.currentTimeMillis();
    for (int i = 0; i < reps; i++) {
        get(map);
    }
    long finish = System.currentTimeMillis();
    System.out.println("Time to get() " + (reps * map.size()) + " entries in a " + setName + ": " + (finish - start));
}
}

给出这些结果:

Warmup populate
Time to populate 10000000 entries in a HashMap: 230
Time to populate 10000000 entries in a TreeMap: 1995
Warmup get
Time to get() 10000000 entries in a HashMap: 140
Time to get() 10000000 entries in a TreeMap: 1164

Answer 3

HashMap是O(1)(通常)用于访问; TreeMap是O(log n)(保证).

这假设您的密钥对象是不可变的,并且具有正确编写的equals和hashCode方法.有关如何正确覆盖equals和hashCode,请参阅Joshua Bloch的"Effective Java" 第3章.

Answer 4

a HashMap是O(1)平均值,因此应该更快,对于大型地图可能会有更好的吞吐量.
但是,HashMap当负载平衡变得太高时,需要重新进行重新扫描.重复是O(n),因此在程序生命的任何时候,由于重新散列,您可能会遭受意外的性能损失,这在一些应用程序中可能是至关重要的[高延迟].所以三思而后使用前HashMap如果延迟是一个问题!

a HashMap也容易受到差的散列函数的影响,如果使用的许多项被散列到同一个地方,则可能导致O(n).