首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >TreeMap或HashMap速度更快

TreeMap或HashMap速度更快
EN

Stack Overflow用户
提问于 2011-08-14 22:39:59
回答 5查看 49.9K关注 0票数 25

我正在写一个字典,在Map<String, Index>中大量使用字符串作为键。我关心的是HashMapTreeMap中的哪一个在地图中搜索关键字时会有更好(更快)的性能?

EN

回答 5

Stack Overflow用户

发布于 2011-08-14 22:43:52

假设没有太多的排序,hashmap将提供o(1)性能(对于大量的排序,这可能会降级到O(n),其中N是任何单个存储桶中的条目(排序)的数量)。另一方面,如果您想要有某种平衡的树结构,产生O(logN)检索,则使用TreeMaps。因此,这真的取决于您的特定用例。但是,如果您只想访问元素,而不管它们的顺序,请使用HashMap

票数 22
EN

Stack Overflow用户

发布于 2014-05-12 19:49:00

代码语言:javascript
复制
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));
}
}

给出了以下结果:

代码语言:javascript
复制
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
票数 19
EN

Stack Overflow用户

发布于 2011-08-14 22:43:12

对于访问,HashMap为O(1) (通常);TreeMap为O(log )(保证)。

这假设您的键对象是不可变的,并且具有正确编写的equals和hashCode方法。有关如何正确覆盖equals和hashCode的信息,请参阅Joshua Bloch的"Effective“chapter 3

票数 12
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/7057430

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档