HashMap,LinkedHashMap和TreeMap之间的区别

问题

Java中的 HashMapLinkedHashMapTreeMap 有什么区别?我没有看到它们有任何输出差异,因为它们都有keySetvalues。什么是 Hashtable

Map m1 = new HashMap();
m1.put("map", "HashMap");
m1.put("schildt", "java2");
m1.put("mathew", "Hyden");
m1.put("schildt", "java2s");
print(m1.keySet()); 
print(m1.values()); 

SortedMap sm = new TreeMap();
sm.put("map", "TreeMap");
sm.put("schildt", "java2");
sm.put("mathew", "Hyden");
sm.put("schildt", "java2s");
print(sm.keySet()); 
print(sm.values());

LinkedHashMap lm = new LinkedHashMap();
lm.put("map", "LinkedHashMap");
lm.put("schildt", "java2");
lm.put("mathew", "Hyden");
lm.put("schildt", "java2s");
print(lm.keySet()); 
print(lm.values());

#1 热门回答(1362 赞)

我更喜欢视觉呈现:

╔══════════════╦═════════════════════╦═══════════════════╦═════════════════════╗
║   Property   ║       HashMap       ║      TreeMap      ║     LinkedHashMap   ║
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
║ Iteration    ║  no guarantee order ║ sorted according  ║                     ║
║   Order      ║ will remain constant║ to the natural    ║    insertion-order  ║
║              ║      over time      ║    ordering       ║                     ║
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
║  Get/put     ║                     ║                   ║                     ║
║   remove     ║         O(1)        ║      O(log(n))    ║         O(1)        ║
║ containsKey  ║                     ║                   ║                     ║
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
║              ║                     ║   NavigableMap    ║                     ║
║  Interfaces  ║         Map         ║       Map         ║         Map         ║
║              ║                     ║    SortedMap      ║                     ║
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
║              ║                     ║                   ║                     ║
║     Null     ║       allowed       ║    only values    ║       allowed       ║
║ values/keys  ║                     ║                   ║                     ║
╠══════════════╬═════════════════════╩═══════════════════╩═════════════════════╣
║              ║   Fail-fast behavior of an iterator cannot be guaranteed      ║
║   Fail-fast  ║ impossible to make any hard guarantees in the presence of     ║
║   behavior   ║           unsynchronized concurrent modification              ║
╠══════════════╬═════════════════════╦═══════════════════╦═════════════════════╣
║              ║                     ║                   ║                     ║
║Implementation║      buckets        ║   Red-Black Tree  ║    double-linked    ║
║              ║                     ║                   ║       buckets       ║
╠══════════════╬═════════════════════╩═══════════════════╩═════════════════════╣
║      Is      ║                                                               ║
║ synchronized ║              implementation is not synchronized               ║
╚══════════════╩═══════════════════════════════════════════════════════════════╝

#2 热门回答(1004 赞)

所有三个类实现Map接口并提供大部分相同的功能。最重要的区别是条目的迭代顺序:

  • HashMap对迭代顺序绝对没有保证。它可以(并且将)甚至在添加新元素时完全改变。
  • TreeMap 将根据它们的 compareTo() 方法(或外部提供的比较器)根据键的“自然排序”进行迭代。此外,它还实现 SortedMap 接口,该接口包含依赖于此排序顺序的方法。
  • LinkedHashMap 将按照条目放入 Map 的顺序迭代

"Hashtable" 是基于散列的映射的通用名称。在Java API的上下文中,Hashtable是Java 1.1之前的一个过时类,它存在于集合框架之前。它不应再被使用,因为它的API混杂着复制功能的过时方法,并且它的方法是同步的(这会降低性能并且通常是无用的)。应该使用ConcurrentHashMap而不是Hashtable。


#3 热门回答(58 赞)

这三个都表示从唯一键到值的映射,因此实现了Map接口。

  • HashMap 是一个基于密钥散列的映射。它支持 O(1)get / put操作。键必须具有 hashCode()equals() 的一致实现才能使其工作。
  • LinkedHashMapHashMap 非常相似,但它增加了对项目添加(或访问)顺序的了解,所以迭代顺序与插入顺序(或访问顺序,取决于构造参数)相同。
  • TreeMap 是一种基于树的映射。其 put / get 操作需要O(log n)时间。它要求项目具有一些比较机制,可以使用ComparableComparator。迭代顺序由此机制确定。