.

HashMap

这是最常使用的哈希表实现。

非线程安全。

在理想情况下，如果哈希散列正常，put 和 get 等操作可达到常数时间的性能。

HashMap 使用了 链地址法 来解决哈希冲突；当冲突元素较多时又会用 树结构 替代单链表，来存储数据，以提高存取效率。

（《哈希表解决哈希冲突的方法》）

 

Hashtable

这是早期Java类库提供的一个哈希表实现。行为与 HashMap 大致相同。

线程安全；不支持 null 键和值

因为同步性能开销，不推荐使用。在需要线程安全的场景中可以使用性能更好的 ConcurrentHashMap。

 

TreeMap

这是基于红黑树的 Map，支持按照 key 的排序顺序遍历数据（可通过构造方法指定 key 的 Comparator）

它的 get、put、remove 等操作时间复杂度都是 O(long(n))。

 

LinkedHashMap

继承自 HashMap，支持按照键值对的“访问”顺序遍历数据，最不常被访问的键值对排在最前

内部有一个双向链表来记录键值对的插入顺序。

put、get、compute等相关操作都属于访问。默认情况下，读取（get、getOrDefault）不会对内部链表顺序产生影响；可以通过构造方法指定

 

示例：利用 LinkedHashMap 实现对空间占用敏感的缓存

Java代码

 

1. LinkedHashMap<String, String> accessOrderedMap = new LinkedHashMap<String, String>(16, 0.75F, true){  

2.   @Override  

3.   protected boolean removeEldestEntry(Entry<String, String> eldest) {  

4.     // 缓存最多只能存 3 个键值对  

5.     return size() > 3;  

6.   }  

7. };  

8.   

9. // 添加数据  

10. accessOrderedMap.put("key1", "v1");  

11. accessOrderedMap.put("key2", "v2");  

12. accessOrderedMap.put("key3", "v3");  

13. // 遍历数据。输出顺序应是：key1、key2、key3  

14. accessOrderedMap.forEach((k,v) -> System.out.println(k + ":" + v));  

15.   

16. // 读取数据  

17. accessOrderedMap.get("key1");  

18. accessOrderedMap.get("key3");  

19. // 遍历数据。输出顺序应是：key2, key1, key3  

20. accessOrderedMap.forEach((k,v) -> System.out.println(k + ":" + v));  

21.   

22. // 添加数据  

23. accessOrderedMap.put("key4", "v4);  

24. // 遍历数据。输出顺序应是：key1, key3, key4。因为超过缓存上限 3，key2 被移除了  

25. accessOrderedMap.forEach((k,v) -> System.out.println(k + ":" + v));