TreeMap或HashMap更快
我正在编写一个字典，它大量使用String作为Map 。 我关心的是HashMap和TreeMap哪一个会在搜索地图中的键时产生更好（更快）的性能？
鉴于没有太多的碰撞，hashmaps会给你o（1）性能（有很多colissions，这可能降级到潜在的O（n），其中N是任何一个桶中的条目数（colissions））。 另一方面，如果您想要某种平衡的树结构来生成O（logN）检索，则使用TreeMaps。 所以它真的取决于你的特定用例。 但是如果你只想访问元素，不管它们的顺序如何都使用HashMap
public class MapsInvestigation { public static HashMap hashMap = new HashMap(); public static TreeMap treeMap = new TreeMap(); public static ArrayList list = new ArrayList (); 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 map) { for (String s : list) { map.get(s); } } private static void populateSet(Map map) { map.clear(); for (String s : list) { map.put(s, s); } } private static void measureTimeToPopulate(Map 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 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是O（1）（通常）用于访问; TreeMap是O（log n）（保证）。
这假设您的密钥对象是不可变的，并且具有正确编写的equals和hashCode方法。 有关如何正确覆盖equals和hashCode，请参阅Joshua Bloch的“Effective Java” 第3章 。
HashMap平均值为O（1），所以它应该更快，对于大型地图可能会有更好的吞吐量。
但是，当负载平衡变得过高时， HashMap需要重新散列。 rehashing是O（n），因此在程序生命的任何时候，由于重新散列，您可能会遭受意外的性能损失，这在一些应用程序中可能是至关重要的[高延迟]。 如果延迟是一个问题，那么在使用HashMap之前要三思而后行！
HashMap也容易受到差的散列函数的影响，如果使用的许多项被散列到同一个地方，这可能会导致O（n）。
HashMap更快。 但是，如果您经常需要按字母顺序处理字典，那么最好使用TreeMap，因为每次需要按字母顺序处理时，您需要对所有单词进行排序。
对于您的应用程序，HashMap是更好的选择，因为我怀疑您将经常需要按字母顺序排序的列表，如果有的话。