You've successfully subscribed to The Daily Awesome
Great! Next, complete checkout for full access to The Daily Awesome
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.
Java源码 | 哈希映射

Java源码 | 哈希映射

. 6 min read

基于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 结构
        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