java - 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());

时间:

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

  • HashMap 对迭代顺序绝对不保证。 在添加新元素时,它甚至可以完全改变。
  • 根据"自然排序" TreeMap 将迭代的关键根据( 或者外部提供的Comparator ) compareTo() 方法。 此外,它还实现了 SortedMap 接口,它包含依赖于这里排序顺序的方法。
  • LinkedHashMap 将按条目放入映射的顺序进行迭代

"hashtable"是hash-based映射的通用名称。 在 Java API的上下文中,Hashtable 是从 1.1开始的一个过时类,在收集框架存在之前。 它不应该再被使用,因为它的API充斥着过时的方法,重复了功能,而且它的方法是同步的( 这可以降低性能,而且通常毫无用处) 。 使用 ConcurrrentHashMap web 而不是 Hashtable 。

我更喜欢视觉演示:


╔══════════════╦═════════════════════╦═══════════════════╦══════════════════════╗
║ Property ║ HashMap ║ TreeMap ║ LinkedHashMap ║
╠══════════════╬═════════════════════╬═══════════════════╬══════════════════════╣
║ ║ 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 ║
╚══════════════╩════════════════════════════════════════════════════════════════╝

所有三个代表从唯一键到值的映射,因此实现映射接口。

  1. HashMap是基于散列键的映射。 它支持 O(1) 获取/放置操作。 键必须有一致的hashCode()equals() 实现才能工作。

  2. HashMaplinkedhashmap非常相似,但它增加了意识的订单项添加( 或者访问), 所以迭代顺序是一样的插入顺序( 或者访问顺序,取决于构造参数) 。

  3. TreeMap是基于树的映射。 它的放置/获取操作占用 O(log n) 时间。 它需要有一些比较机制,或者比较或者比较器。 迭代顺序由这个机制决定。

就从我自己的经验更多的输入地图,当我将使用每一个:

  • HashMap - 在寻找 best-performance ( 快速) 实现时最有用。
  • TreeMap ( SortedMap接口) - 当我关注一个我定义的特定顺序的关键字时,非常有用。
  • LinkedHashMap - 结合了保证的顺序,而不增加维护树的成本。 ( 它几乎和HashMap一样快) 。 特别是,LinkedHashMap也为创建缓存对象提供了一个很好的起点,它覆盖了 removeEldestEntry() 方法。 这允许你创建一个缓存对象,该对象可以使用你定义的某些条件过期数据。

参见下面的图( 大一个 ) 中的类层次结构中的位置。 TeeMap实现 SortedMapNavigableMap,而 HashMap 不执行。

HashTable 已经过时,应使用相应的ConcurrentHashMap 类。 enter image description here

@Amit: SortedMap 是一个接口,而 TreeMap 是一个实现 SortedMap 接口的类。 这意味着如果遵循 SortedMap 要求它的实现者执行的协议。 除非实现为搜索树,否则树不能为你提供有序数据,因为树可以是任何类型的树。 所以为了使树形图像排序顺序一样工作,它实现了 SortedMap ( e.g, 二叉搜索树- BST,平衡的BST,如AVL和R-B树,甚至是三元搜索树- 主要用于有序搜索) 。


public class TreeMap<K,V>
extends AbstractMap<K,V>
implements SortedMap<K,V>, Cloneable, Serializable

在 NUT-SHELL HashMap 中:给出 O(1) 中的数据,没有排序

TreeMap: 在 O(log N), 基础 2中提供数据。 使用有序键

LinkedHashMap: 带有链接列表( 考虑 indexed-SkipList ) 功能的哈希表,以将数据按插入树的方式存储。 最适合实现 LRU ( 最近使用最少) 。

这些是同一接口的不同实现。 每个实现都有一些优点和缺点( 快速插入,慢速搜索) 或者反之亦然。

详情看javadoc TreeMap, HashMap, LinkedHashMap

HashMap绝对不能保证迭代顺序。 添加新元素时,它甚至可以完全改变。 根据"自然排序"treemap将迭代的关键根据( 或者外部提供的比较器) compareTo() 方法。 另外,它实现了SortedMap接口,它包含依赖于这个排序顺序的方法。 LinkedHashMap将按照条目放入映射的顺序迭代

看看性能如何变化。 enter image description here

树映射是排序映射的实现,因为自然排序,它需要 O(log2n) 来放置或者获取

...