【Java核心-基础】哈希表 Map

 

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 实现对空间占用敏感的缓存

LinkedHashMap<String, String> accessOrderedMap = new LinkedHashMap<String, String>(16, 0.75F, true){
  @Override
  protected boolean removeEldestEntry(Entry<String, String> eldest) {
    // 缓存最多只能存 3 个键值对
    return size() > 3;
  }
};

// 添加数据
accessOrderedMap.put("key1", "v1");
accessOrderedMap.put("key2", "v2");
accessOrderedMap.put("key3", "v3");
// 遍历数据。输出顺序应是：key1、key2、key3
accessOrderedMap.forEach((k,v) -> System.out.println(k + ":" + v));

// 读取数据
accessOrderedMap.get("key1");
accessOrderedMap.get("key3");
// 遍历数据。输出顺序应是：key2, key1, key3
accessOrderedMap.forEach((k,v) -> System.out.println(k + ":" + v));

// 添加数据
accessOrderedMap.put("key4", "v4);
// 遍历数据。输出顺序应是：key1, key3, key4。因为超过缓存上限 3，key2 被移除了
accessOrderedMap.forEach((k,v) -> System.out.println(k + ":" + v));