Java源码 | 哈希映射 | 个人笔记存档

基于jdk1.8的源代码，学习java中有关哈希map的类。

HashMap
TreeMap
LinkedHashMap
Hashtable
ConcurrentHashMap

首先使用IDEA查看与这几个类有关的UML类图。

我关注的主要有以下几点

AbstractMap, TreeMap, HashMap, LinkedHashMap 之间的继承关系。
LinkedHashMap 在 HashMap 的基础上，对 Map 接口的修改。
TreeMap 使用的SortedMap, NavigableMap 提供的额外特性。
Hashtable 作为 Dictionary 的子类，有什么特点。

Map Interface

源码的 javaDoc 中对 Map 的定义有几个关键点

Map 提供键值映射；不存在重复的键；一个键只映射一个值；
提供三种集合视图 (collection views)
- 键的集合
- 值的集合
- 键值映射的集合
顺序 order 取决于操作集合视图的迭代器。TreeMap 提供了额外的顺序保证。
需要特别注意 "mutable" 的键的情况。Related Issue Here
两种标准构造器
- (void): 构造空的 Map。
- (Map): 构造一个传入的 Map 的副本。
类似 clone(), equals(), hashCode(), toString() 的函数，在处理自引用(self-referential instances)的Map时，可能会触发异常。

Hashtable Class

提供键值映射；不允许 null 作为键或值；
底层实现为 Entry[], Entry 是单链表节点，存储 hash, key, value, next
线程安全：引起映射改变的方法均为 synchronized 所修饰。
性能由初始容量(initial capacity)（默认11）和负载系数(load factor)（默认为0.75）决定

添加操作：put(), addEntry()

计算哈希 Object.hashCode()
计算映射索引 (hash & 0x7FFFFFFF) % tab.length
覆盖旧的值，或在链表后添加新的键值对

扩容：rehash()

扩容阈值由当前容量和负载系数决定
当到达阈值后仍需添加新键值对时，更新容量 newCapacity = (oldCapacity << 1) + 1;

默认初始容量为11，可以保证容量总为素数常用的hash函数是选一个数m取模（余数），这个数在课本中推荐m是素数，但是经常见到选择m=2^n，因为对2^n求余数更快，并认为在key分布均匀的情况下，key%m也是在[0,m-1]区间均匀分布的。但实际上，key%m的分布同m是有关的。Reference
将旧的 Map 更新到新的 Map 中（需要重新计算索引）

删除和清空映射不会重新分配较小的 Map 空间

HashMap class

提供键值映射，允许 null 作为键或值；底层实现为数组 Node<K,V>[] table
非线程安全: 多线程对结构进行操作必须考虑同步问题【添加或删除，不包含修改】并发环境可能会形成环状链表
不保证插入顺序且无法维护数据顺序；
get() 和 put() 保持常数时间复杂度；
迭代性能：capacity * size 【考虑迭代性能时，capacity不能过大，load factor不能过小】
扩容：容量翻倍（*2）默认容量：16 默认负载系数：0.75

扩容 resize()：

对原有的元素根据hash值重新计算索引并更新位置。
扩容后长度变为2倍（当长度大于默认最大 1<<30，则长度固定为 Integer.MaxValue）
当hash碰撞较多时，及链表长度>=8时，将单链表转换至红黑树

为什么扩容2倍

index = hash & (length-1): length - 1 的二进制表示为 0*1*，可以充分利用空间
每次扩容后的 length - 1 中 1 的数量+1，相当于必定多考虑一位 hash，减少碰撞概率。同时在 resize() 函数中可以通过判断 (e.hash & oldCap) == 0 来确定该项索引保持不变或 +oldCap

LinkedHashMap Class

LinkedHashMap 是 HashMap 的子类

底层实现：同HashMap, 但节点为双向链表节点 可以记录插入顺序（重复插入key无法体现）【保持顺序复制map】

可以快速实现 LRU 结构

1
2
3
4
5


    private static final int MAX_ENTRIES = 100;
    @override
    protected boolean removeEldestEntry(Map.Entry eldest) {
       return size() > MAX_ENTRIES;
    }

对 collection-view 的操作不会影响映射的结构 （HashMap, Hashtable 会影响）
提供键值映射，允许 null 作为键或值；
get() 和 put() 保持常数时间复杂度；
非线程安全: 多线程对结构进行操作必须考虑同步问题【添加或删除，不包含修改】

TreeMap Class

底层实现为红黑树
get(), put(), remove() 和 containsKey() 保持$O(log n)$ 时间复杂度；
非线程安全: 多线程对结构进行操作必须考虑同步问题【添加或删除，不包含修改】
树形实现，因此对 Comparator 严格要求（存在性，可比较性）
- 按照 key 的范围快速获取子树
使用迭代器获取按照 key 有序的键值对

ConcurrentHashMap

线程安全 get() 不会被锁影响，put(), remove() 会分段上锁，默认16段 (segment)

Updating...

Java源码 | 哈希映射