Java源码 | 哈希映射

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

  • HashMap
  • TreeMap
  • LinkedHashMap
  • Hashtable
  • ConcurrentHashMap

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

我关注的主要有以下几点

  • AbstractMap, TreeMap, HashMap, LinkedHashMap 之间的继承关系。
  • LinkedHashMapHashMap 的基础上,对 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 - 11 的数量+1,相当于必定多考虑一位 hash, 减少碰撞概率。 同时在 resize() 函数中可以通过判断 (e.hash & oldCap) == 0 来确定该项索引保持不变或 +oldCap
HashMap的扩容机制 为什么是2幂_Java_dalong3976的博客-CSDN博客
HashMap的扩容机制 为什么是2幂假设length为Hash表数组的大小,方法indexFor(Java

LinkedHashMap Class

LinkedHashMapHashMap 的子类

  • 底层实现:同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...

Reference

HashMap vs. TreeMap vs. HashTable vs. LinkedHashMap - DZone Java
Check out this tutorial to learn all about important data structures like HashMap, HashTable, and TreeMap, with code examples.
Map 综述(三):彻头彻尾理解 ConcurrentHashMap_Java_Rico’s Blogs-CSDN博客
ConcurrentHashMap是J.U.C的重要成员,它是HashMap的一个线程安全的版本。在Java