Hashmap,linkedashmap 和 TreeMap 的区别

What is the difference between HashMap, LinkedHashMap and TreeMap in Java? I don't see any difference in the output as all the three has keySet and values. What are Hashtables?

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

转载于:https://stackoverflow.com/questions/2889777/difference-between-hashmap-linkedhashmap-and-treemap

15个回答

All three classes implement the Map interface and offer mostly the same functionality. The most important difference is the order in which iteration through the entries will happen:

  • HashMap makes absolutely no guarantees about the iteration order. It can (and will) even change completely when new elements are added.
  • TreeMap will iterate according to the "natural ordering" of the keys according to their compareTo() method (or an externally supplied Comparator). Additionally, it implements the SortedMap interface, which contains methods that depend on this sort order.
  • LinkedHashMap will iterate in the order in which the entries were put into the map

"Hashtable" is the generic name for hash-based maps. In the context of the Java API, Hashtable is an obsolete class from the days of Java 1.1 before the collections framework existed. It should not be used anymore, because its API is cluttered with obsolete methods that duplicate functionality, and its methods are synchronized (which can decrease performance and is generally useless). Use ConcurrentHashMap instead of Hashtable.

csdnceshi55
~Onlooker You can choose whether you want the LinkedHashMap iteration in insertion-order or access-order.
接近 6 年之前 回复
weixin_41568126
乱世@小熊 Yes - in fact those are the standard ways to implement sorting. TreeMap has a constructor that takes a Comparator to use, and if none is provided, it expects all objects added to implement Comparable.
7 年多之前 回复
csdnceshi64
游.程 it is possible to use Comparable or Comparator for implementing sorting mechanism in SortedMap (stackoverflow.com/questions/4108604/…)
7 年多之前 回复
csdnceshi72
谁还没个明天 A notable difference between Hashtable and HashMap is that in a Hashtable, "neither the key nor the value can be null". This constraint does not exist on the latter.
10 年多之前 回复
weixin_41568126
乱世@小熊 Read the API doc, that's what it's for: java.sun.com/javase/6/docs/api/java/util/package-summary.html
10 年多之前 回复
weixin_41568126
乱世@小熊 Map is an interface. HashMap and Hashtable both implement it; as I wrote, Hashtable is a legacy class.
10 年多之前 回复
weixin_41568127
?yb? What is then Map actually and whats the difference between Map,HashMap and Hashtables.
10 年多之前 回复

I prefer visual presentation:

╔══════════════╦═════════════════════╦═══════════════════╦═════════════════════╗
║   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               ║
╚══════════════╩═══════════════════════════════════════════════════════════════╝
csdnceshi70
笑故挽风 love this visual presentation. See my analogous answer on Sets here stackoverflow.com/a/43364019/3886961 based on your work
3 年多之前 回复
csdnceshi77
狐狸.fox It's also worth noting that O(1) isn't always better than O(log n); if you have a very long key, something based on BSTs might be much faster than something that has to perform an O(n) hash on the whole key before being able to do anything.
3 年多之前 回复
csdnceshi73
喵-见缝插针 It may be worth mentioning, that O(1) is the best case scenario (which we wouldn't usually call O, see this question)
接近 5 年之前 回复
weixin_41568131
10.24 LinkedHashMap has the double linked buckets BUT ALSO the bucket table HashMap has. It's not replacing it. This means that accessing buckets is done in the same way as in HashMap, as the linked list is there for iteration in insertion order (or access order) only.
5 年多之前 回复
csdnceshi63
elliott.david Double Linked Buckets? I think that adds unnecessary overhead of searching for the bucket for insertion/removal operations (because it has to search for the right bucket to put the object in). I always thought that LinkedHashMap implementations would be similar to that of a Map but with a little extra overhead of "entries list" (may be as a linked list) that's used for iteration purposes. Are you sure, shevchyk? If yes, can you explain or give me some online links that back your statement?
接近 6 年之前 回复
weixin_41568184
叼花硬汉 In addition to insertion-order, LinkedHashMap also supports access-order (when using the constructor with the boolean access-order param).
6 年多之前 回复
csdnceshi61
derek5. Thanks for visual presentation. Can you provide some links for List and Set visual presentation. Thanks again.
接近 7 年之前 回复

Hash map doesn't preserves the insertion order.
Example. Hashmap If you are inserting keys as

1  3
5  9
4   6
7   15
3   10

It can store it as

4  6
5  9
3  10
1  3
7  15

Linked Hashmap preserves the insertion order.

Example.
If you are inserting keys

1  3
5  9
4   6
7   15
3   10

It will store it as

1  3
5  9
4   6
7   15
3   10

same as we insert.

Tree map stores the vales in Increasing Order Of Keys. Example.
If you are inserting keys

1  3
5  9
4   6
7   15
3   10

It will store it as

1  3
3  10
4   6
5   9
7   15

See where each class is in the class hierarchy in the following diagram (bigger one). TreeMap implements SortedMap and NavigableMap while HashMap doesn't.

HashTable is obsolete and the corresponding ConcurrentHashMap class should be used. enter image description here

All offer a key->value map and a way to iterate through the keys. The most important distinction between these classes are the time guarantees and the ordering of the keys.

  1. HashMap offers 0(1) lookup and insertion. If you iterate through the keys, though, the ordering of the keys is essentially arbitrary. It is implemented by an array of linked lists.
  2. TreeMap offers O(log N) lookup and insertion. Keys are ordered, so if you need to iterate through the keys in sorted order, you can. This means that keys must implement the Comparable interface.TreeMap is implemented by a Red-Black Tree.
  3. LinkedHashMap offers 0(1) lookup and insertion. Keys are ordered by their insertion order. It is implemented by doubly-linked buckets.

Imagine you passed an empty TreeMap, HashMap, and LinkedHashMap into the following function:

void insertAndPrint(AbstractMap<Integer, String> map) {
  int[] array= {1, -1, 0};
  for (int x : array) {
    map.put(x, Integer.toString(x));
  }
  for (int k: map.keySet()) {
   System.out.print(k + ", ");
  }
}

The output for each will look like the results below.

For HashMap, the output was, in my own tests, { 0, 1, -1}, but it could be any ordering. There is no guarantee on the ordering.
Treemap,the output was,{ -1, 0, 1}
LinkedList,the output was,{ 1, -1, 0}

@Amit: SortedMap is an interface whereas TreeMap is a class which implements the SortedMap interface. That means if follows the protocol which SortedMap asks its implementers to do. A tree unless implemented as search tree, can't give you ordered data because tree can be any kind of tree. So to make TreeMap work like Sorted order, it implements SortedMap ( e.g, Binary Search Tree - BST, balanced BST like AVL and R-B Tree , even Ternary Search Tree - mostly used for iterative searches in ordered way ).

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

In NUT-SHELL HashMap : gives data in O(1) , no ordering

TreeMap : gives data in O(log N), base 2. with ordered keys

LinkedHashMap : is Hash table with linked list (think of indexed-SkipList) capability to store data in the way it gets inserted in the tree. Best suited to implement LRU ( least recently used ).

HashMap makes absolutely not guarantees about the iteration order. It can (and will) even change completely when new elements are added. TreeMap will iterate according to the "natural ordering" of the keys according to their compareTo() method (or an externally supplied Comparator). Additionally, it implements the SortedMap interface, which contains methods that depend on this sort order. LinkedHashMap will iterate in the order in which the entries were put into the map

Look at how performance varying.. enter image description here

Tree map which is an implementation of Sorted map. The complexity of the put, get and containsKey operation is O(log n) due to the Natural ordering

All three represent mapping from unique keys to values, and therefore implement the Map interface.

  1. HashMap is a map based on hashing of the keys. It supports O(1) get/put operations. Keys must have consistent implementations of hashCode() and equals() for this to work.

  2. LinkedHashMap is very similar to HashMap, but it adds awareness to the order at which items are added (or accessed), so the iteration order is the same as insertion order (or access order, depending on construction parameters).

  3. TreeMap is a tree based mapping. Its put/get operations take O(log n) time. It requires items to have some comparison mechanism, either with Comparable or Comparator. The iteration order is determined by this mechanism.

csdnceshi76
斗士狗 Thanks for your answer, basically what i get as a difference between tree and linked hash map is linked hasmap would iterate the values in order they were inseted , but tree Map would iterate the values according to natural ordering /lexicograhic/sorted odering of "keys" not values.
3 年多之前 回复
weixin_41568208
北城已荒凉 This is because your insertion order matches the lexicographic order of your keys ("abc1", "abc2", "abc3"). If you insert in a different order, your code will still iterate according to the lexicographic ordering.
3 年多之前 回复
csdnceshi76
斗士狗 private TreeMap<String ,Integer> mySection2 = new TreeMap<>(); mySection2.put("abc1", 2); mySection2.put("abc2",5); mySection2.put("abc3",3); for(Integer x : mySection2.values()) { Log.e("LOG","TreeMap===="+x); } This is giving me the same order as items were inserted ?please suggest how is it different from LinkedHashMaps ?
3 年多之前 回复
csdnceshi80
胖鸭 Tree map also has a lot of other nice tricks. Like head and tail maps.
6 年多之前 回复
weixin_41568184
叼花硬汉 As he said in # 2: LinkedHashMap will iterate in the insertion order, not the natural order. So if you add (2,5,3) to a LinkedHashMap and do a for each over it, it will return 2,5,3. If it were 2,5,3 to a TreeMap it will return 2,3,5.
接近 8 年之前 回复
csdnceshi78
程序go So if I understand correctly, the only difference between LinkedHashMap and TreeMap is performance, given that the order of insertion is the same as the natural order?
大约 8 年之前 回复
  • HashMap:

    • Order not maintains
    • Faster than LinkedHashMap
    • Used for store heap of objects
  • LinkedHashMap:

    • LinkedHashMap insertion order will be maintained
    • Slower than HashMap and faster than TreeMap
    • If you want to maintain an insertion order use this.
  • TreeMap:

    • TreeMap is a tree-based mapping
    • TreeMap will follow the natural ordering of key
    • Slower than HashMap and LinkedHashMap
    • Use TreeMap when you need to maintain natural(default) ordering

Just some more input from my own experience with maps, on when I would use each one:

  • HashMap - Most useful when looking for a best-performance (fast) implementation.
  • TreeMap (SortedMap interface) - Most useful when I'm concerned with being able to sort or iterate over the keys in a particular order that I define.
  • LinkedHashMap - Combines advantages of guaranteed ordering from TreeMap without the increased cost of maintaining the TreeMap. (It is almost as fast as the HashMap). In particular, the LinkedHashMap also provides a great starting point for creating a Cache object by overriding the removeEldestEntry() method. This lets you create a Cache object that can expire data using some criteria that you define.
csdnceshi62
csdnceshi62 To be precise, TreeMap doesn't keep the elements in order. It keeps the keys in order.
7 年多之前 回复
共15条数据 1 尾页
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问
相关内容推荐