Java高级 (6) 集合之Map

Map 接口

Map接口的常用实现类：HashMap、TreeMap、LinkedHashMap 和 Properties。

• HashMap：
  • HashMap 是 Map 接口使用频率最高的实现类。
  • 效率高，线程不安全的。
  • 可以存储 key 或 value 为 null 的键值对。
• LinkedHashMap：
  • 是 HashMap 的子类。
  • 保证在遍历元素时，可以按照添加的顺序进行遍历（在原有 HashMap 的基础上，为 item 添加了双向链表的结构）。在频繁的遍历操作中，效率高于 LinkedHashMap。
• TreeMap：
  • 底层使用红黑树，是有序的，根据 key 采用自然排序或者定制排序。
• Hashtable：
  • 作为 Map 接口的古老实现类。
  • 效率低，线程安全的。
  • 不可以存储 key 或 value 为 null 的键值对。
• Properties：
  • 是 Hashtable 的子类。
  • 常用于处理配置文件，key 和 value 都是 String 类型。

实现类 - HashMap

底层实现：

• JDK 7 以及之前：数组 + 链表。
• JDK 8：数组 + 链表 + 红黑树。

JDK 7

在 HashMap map = new HashMap(); 实例化之后，底层创建了一个长度为 16 的一维数组 Entry[] table 。

map.put(k1, v1) 存放键值对：

• 首先调用 k1 的 hashcode 方法得到哈希值，接着通过某种计算方法之后得到 在 Entry 数组中的存放位置。
• 如果此位置上为空，则键值对（Entry）添加成功。
• 如果此位置上不为空，比较 k1 和已经存在数据的哈希值：
  • 如果不相同，利用拉链法（头插法）添加；
  • 如果与某个相同，继续调用 k1 所在类的 equals 方法：
    • equals 返回 false 则添加成功；
    • 返回 true 则用 v1 替换原来的 value。

若涉及到（超出临界值 = 数组长度 ✖ 负载因子，默认 0.75，且要存放的位置非空时）扩容，则扩容为原来的 2 倍。

JDK 8

在 new HashMap(); 后，没有创建一个长度为 16 的数组（Node 类型）。在首次调用 put 方法时，底层创建长度为 16 的数组。

当数组的某一个索引位置上的元素，拉链法中元素个数大于 8 且当前数组长度超过 64，此时索引位置上的数据改为红黑树存储。

实现类 - LinkedHashMap

LinkedHashMap 中的内部类 Entry，继承于 Node，其中 before、after 属性表示了插入顺序的前后关系。

static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
    	super(hash, key, value, next);
    }
}