HashMap, LinkedHashMap和TreeMap在Java中的区别是什么? 我在输出中没有看到任何不同,因为这三个都有keySet和values。什么是哈希表?

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

当前回答

@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

在坚果壳 HashMap:给出O(1)的数据,没有排序

TreeMap:给出O(log N),以2为底的数据。使用有序键

LinkedHashMap:是具有链表(想想索引- skiplist)功能的哈希表,以插入树的方式存储数据。最适合实现LRU(最近最少使用)。

其他回答

三者中最重要的是如何保存条目的顺序。

HashMap -不保存条目的顺序。 如。

public static void main(String[] args){
        HashMap<String,Integer> hashMap = new HashMap<>();
        hashMap.put("First",1);// First ---> 1 is put first in the map
        hashMap.put("Second",2);//Second ---> 2 is put second in the map
        hashMap.put("Third",3); // Third--->3 is put third in the map
        for(Map.Entry<String,Integer> entry : hashMap.entrySet())
        {
            System.out.println(entry.getKey()+"--->"+entry.getValue());
        }
    }

LinkedHashMap:它保存条目的顺序。例如:

public static void main(String[] args){
        LinkedHashMap<String,Integer> linkedHashMap = new LinkedHashMap<>();
        linkedHashMap.put("First",1);// First ---> 1 is put first in the map
        linkedHashMap.put("Second",2);//Second ---> 2 is put second in the map
        linkedHashMap.put("Third",3); // Third--->3 is put third in the map
        for(Map.Entry<String,Integer> entry : linkedHashMap.entrySet())
        {
            System.out.println(entry.getKey()+"--->"+entry.getValue());
        }
    }

TreeMap:按键的升序保存条目。例如:

public static void main(String[] args) throws IOException {
        TreeMap<String,Integer> treeMap = new TreeMap<>();
        treeMap.put("A",1);// A---> 1 is put first in the map
        treeMap.put("C",2);//C---> 2 is put second in the map
        treeMap.put("B",3); //B--->3 is put third in the map
        for(Map.Entry<String,Integer> entry : treeMap.entrySet())
        {
            System.out.println(entry.getKey()+"--->"+entry.getValue());
        }
    }

我更喜欢视觉呈现:

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

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

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. 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). 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.

HashMap、TreeMap和LinkedHashMap这三个类都实现了java.util.Map接口,并表示从唯一键到值的映射。

HashMap

HashMap包含基于键的值。 它只包含独特的元素。 它可以有一个空键和多个空值。 它没有维持秩序。 公共类HashMap<K,V>扩展了AbstractMap<K,V>实现了Map<K,V>,可克隆,可序列化

LinkedHashMap

LinkedHashMap包含基于键的值。 它只包含独特的元素。 它可以有一个空键和多个空值。 它与HashMap相同,只是维护插入顺序。//见下面的减速等级 公共类LinkedHashMap<K,V>扩展HashMap<K,V>实现Map<K,V>

TreeMap

TreeMap包含基于键的值。它实现了NavigableMap接口并扩展了AbstractMap类。 它只包含独特的元素。 它不能有空键,但可以有多个空值。 它与HashMap相同,只是维护升序(使用键的自然顺序进行排序)。 公共类TreeMap<K,V>扩展AbstractMap<K,V>实现NavigableMap<K,V>,可克隆,可序列化

哈希表

哈希表是一个列表数组。每个列表都被称为一个桶。桶的位置通过调用hashcode()方法来标识。哈希表包含基于键的值。 它只包含独特的元素。 它可能没有任何空键或值。 它是同步的。 这是一个传承类。 公共类Hashtable<K,V>扩展Dictionary<K,V>实现Map<K,V>,可克隆,可序列化

裁判:http://javarevisited.blogspot.in/2015/08/difference-between-HashMap-vs-TreeMap-vs-LinkedHashMap-Java.html

虽然这里有很多很好的答案,但我想给出我自己的表,描述与Java 11绑定的各种Map实现。

我们可以在图表中看到这些差异:

HashMap is the general-purpose Map commonly used when you have no special needs. LinkedHashMap extends HashMap, adding this behavior: Maintains an order, the order in which the entries were originally added. Altering the value for key-value entry does not alter its place in the order. TreeMap too maintains an order, but uses either (a) the “natural” order, meaning the value of the compareTo method on the key objects defined on the Comparable interface, or (b) invokes a Comparator implementation you provide. TreeMap implements both the SortedMap interface, and its successor, the NavigableMap interface. NULLs: TreeMap does not allow a NULL as the key, while HashMap & LinkedHashMap do. All three allow NULL as the value. HashTable is legacy, from Java 1. Supplanted by the ConcurrentHashMap class. Quoting the Javadoc: ConcurrentHashMap obeys the same functional specification as Hashtable, and includes versions of methods corresponding to each method of Hashtable.