TreeMap or HashMap faster

This question already has an answer here:

  • Difference between HashMap, LinkedHashMap and TreeMap 16 answers
  • What is the difference between a HashMap and a TreeMap? [duplicate] 8 answers

  • Given that there are not many collissions hashmaps will give you o(1) performance (with a lot of colissions this can degrade to potentially O(n) where N is the number of entries (colissions) in any single bucket). TreeMaps on the other hand are used if you want to have some sort of balanced tree structure which yields O(logN) retrieval. So it really depends on your particular use-case. But if you just want to access elements, irrespective of their order use HashMap


    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
    

    HashMap is O(1) (usually) for access; TreeMap is O(log n) (guaranteed).

    This assumes that your key objects are immutable and have properly written equals and hashCode methods. See Joshua Bloch's "Effective Java" chapter 3 for how to override equals and hashCode correctly.

    链接地址: http://www.djcxy.com/p/92172.html

    上一篇: 树形图和散列表的实时用例?

    下一篇: TreeMap或HashMap更快