Java容器学习（4）

HashMap 类

【哈希表】 实现 Map 接口。底层使用散列存储：构造一个 Entry 数组，根据 key 的 hash 值将 Entry 存入指定位置。

• key 值无序且不可重复，且允许 null 作为 key 值存在。
• 发生哈希冲突时，HashMap 采用链表保存多个元素。当链表长度大于 8 时，链表自动转化为红黑树。
• 达到负载因数后，HashMap 将调用 resize 方法动态扩容：新建一个 2 倍容量的新数组复制当前数组的数据。

HashMap 构造方法

Map<String,Integer> map = new HashMap<>();                       // 默认初始容量 16 负载因数 0.75
Map<String,Integer> map = new HashMap<>(32);                     // 自定义初始容量
Map<String,Integer> map = new HashMap<>(32, 0.5f);               // 自定义初始容量和负载因数Copy to clipboardErrorCopied

LinkedHashMap 类

【链式哈希表】继承 HashMap 类。

1. 底层使用散列存储：构造一个 Entry 数组，根据 key 的 hash 值将 Entry 存入指定位置。
2. Entry 额外添加了引用 before & after ，使哈希表内的所有 Entry 构成一个双向链表维护 Entry 的顺序。

LinkedHashMap 构造方法

在默认情况下 Entry 按照插入顺序排序，可指定创建时的初始容量和负载因数。

Map<String,Integer> map = new LinkedHashMap<>();                  // 默认初始容量 16 负载因数 0.75 
Map<String,Integer> map = new LinkedHashMap<>(32);                // 自定义初始容量
Map<String,Integer> map = new LinkedHashMap<>(32, 0.5f);          // 自定义初始容量和负载因数Copy to clipboardErrorCopied

Entry 也可以按照访问顺序排序：对 Entry 进行操作时会先删除再插入，将 Entry 移动到双向链表的表尾。

Map<String,Integer> map = new LinkedHashMap<>(32，0.5f, true);    // 基于访问顺序排序Copy to clipboardErrorCopied

LinkedHashMap 类提供了 removeEldestEntry 方法，在使用 put 操作插入 Entry 时将自动调用此方法决定是否移除双向链表表头的 Entry：默认返回 false ，可通过重写此方法以实现 LRU 算法。

// Entry 超过容量后自动删除最久未使用的 Entry
Map<String,Integer> map = new LinkedHashMap<>(capacity, 0.5f, true){
    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {  
        return size() > capacity;  
    }  
};Copy to clipboardErrorCopied

TreeMap 类

【树表】 实现了 Map 接口。底层使用红黑树存储：Entry 按照 key 值大小插入红黑树，并动态调整红黑树高度。

TreeMap 类方法

TreeMap 类提供了以下专属方法使用。

map.firstKey();                   // 返回最小 key
map.lastKey();                    // 返回最大 key

map.ceilingKey("10");             // 返回大于等于10的最小 Key，不存在则返回 null
map.ceilingEntry("10");           // 返回大于等于10的最小 Key 的键值对(getKey / getValue 方法)

map.floorKey("10");               // 返回小于等于10的最大 Key，不存在则返回 null
map.floorEntry("10");             // 返回小于等于10的最大 Key 的键值对Copy to clipboardErrorCopied

Set 子类

• HashSet 类：【散列集】基于 HashMap 类实现。
• LinkedHashSet 类：【链式散列集】基于 LinkedHashMap 类实现。
• TreeSet 类：【树集】基于 TreeMap 类实现。