TreeMap, HashMap 和 LinkedHashMap 的区别

TreeMap, HashMap and LinkedHashMap: 相同点是什么?

  • 都提供 a key->value map 并且提供迭代这些 key 的方法和迭代器. 这些类中的区别是键的及时性和是否有序.
  • 3 个类 HashMap, TreeMap and LinkedHashMap 都实现了 java.util.Map 接口, 并代表键到值的唯一映射.

关键点

  1. HashMap: HashMap 是 0(1) 在查询和插入中的时间复杂度. 如果你去遍历,你发现键基本上是任意的. 由数组链表实现.
    Syntax:
    **public class HashMap extends AbstractMap 
    implements Map,Cloneable, Serializable**
  • A HashMap 通过键来表示值.
    • 键值唯一.
    • 可用 null 做键,可用多个 null 做 value.
    • 它是 无序的.
  1. **LinkedHashMap: **LinkedHashMap 是 **0(1)** 在插入和查找方面的时间复杂度. 键值插入什么样,就是什么样. 它是由双向链表实现的.
    Syntax:
    **public class LinkedHashMap extends HashMap 
    0implements Map**
  • A LinkedHashMap 通过键来表示值.
    • 键值唯一.
    • 可用 null 做键,可用多个 null 做 value
    • 与 HashMap 同其保持插入顺序.
  1. TreeMap: TreeMap 是时间按复杂度 O(log N). 键值有序, 如果你想可以有序迭代键值. 所以这些键值类必须实现 Comparable 接口. TreeMap 由红黑树实现.
    Syntax:
   public class TreeMap extends AbstractMap implements
    NavigableMap, Cloneable, Serializable
  • A TreeMap contains values based on the key. It implements the NavigableMap interface and extends AbstractMap class.
    • It contains only unique elements.
    • It cannot have null key but can have multiple null values.
    • It is same as HashMap instead maintains ascending order(Sorted using the natural order of its key).
  1. ** Hashtable: **“Hashtable” is the generic name for hash-based maps.
    Syntax:
    **public class Hashtable extends Dictionary implements
    Map, Cloneable, Serializable**
  • A Hashtable is an array of list. Each list is known as a bucket. The position of bucket is identified by calling the hashcode() method. A Hashtable contains values based on the key.
    • It contains only unique elements.
    • It may have not have any null key or value.
    • It is synchronized.
    • It is a legacy class.

hashmap

image.png

LinkedHashMap

image.png

TreeMap

image.png

Output of HashMap:

-1, 0, 1, -2, 2,     
// ordering of the keys is essentially arbitrary (any ordering)

Output of LinkedHashMap:

 1, -1, 0, 2, -2,     
// Keys are ordered by their insertion order

Output of TreeMap:

 -2, -1, 0, 1, 2,   
// Keys are in sorted order

Comparison Table

Real Life Applications

  1. Suppose you were creating a mapping of names to Person objects. You might want to periodically output the people in alphabetical order by name. A TreeMap lets you do this.
  2. A TreeMap also offers a way to, given a name, output the next 10 people. This could be useful for a “More”function in many applications.
  3. A LinkedHashMap is useful whenever you need the ordering of keys to match the ordering of insertion. This might be useful in a caching situation, when you want to delete the oldest item.
  4. Generally, unless there is a reason not to, you would use HashMap. That is, if you need to get the keys back in insertion order, then use LinkedHashMap. If you need to get the keys back in their true/natural order, then use TreeMap. Otherwise, HashMap is probably best. It is typically faster and requires less overhead.

This article is contributed by Mr. Somesh Awasthi. If you like GeeksforGeeks and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to contribute@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

  
    展开阅读全文