树状图或哈希图速度更快

performance java

2022-09-01 18:12:47

我正在编写一本字典，其中大量使用String作为键。我关心的是，在搜索地图中的键时，哪一个和将导致更好（更快）的性能？Map<String, Index>HashMapTreeMap

答案 1

鉴于没有太多的碰撞哈希映射将为您提供o（1）性能（使用大量连接，这可能会降级为潜在的O（n），其中N是任何单个存储桶中的条目（colissions）的数量）。另一方面，如果您想拥有某种平衡的树结构，从而产生O（logN）检索，则使用树状图。所以这实际上取决于你的特定用例。但是，如果您只想访问元素，无论其顺序如何，请使用HashMap

答案 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