HashMap 源码解析
1. 概念
java.lang.Object
↳ java.util.AbstractMap<K, V>
↳ java.util.HashMap<K, V>
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable { }
HashMap 是一个散列表,它存储的内容是键值对(key-value)映射。
HashMap 继承于AbstractMap,实现了Map、Cloneable、java.io.Serializable接口。
HashMap 的实现不是同步的,这意味着它不是线程安全的。(多线程时可以用ConcurrentHashMap,比HashTable更高效)。它的key、value都可以为null。此外,HashMap中的映射不是有序的。
HashMap 的实例有两个参数影响其性能:“初始容量” 和 “加载因子”。容量 是哈希表中桶的数量(默认是16),初始容量 只是哈希表在创建时的容量。加载因子 是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时,则要对该哈希表进行 rehash 操作(即重建内部数据结构),从而哈希表将具有大约两倍的桶数。
通常,默认加载因子是 0.75, 这是在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销,但同时也增加了查询成本(在大多数 HashMap 类的操作中,包括 get 和 put 操作,都反映了这一点)。在设置初始容量时应该考虑到映射中所需的条目数及其加载因子,以便最大限度地减少 rehash 操作次数。如果初始容量大于最大条目数除以加载因子,则不会发生 rehash 操作。
HashMap继承于AbstractMap类,实现了Map接口。Map是”key-value键值对”接口,AbstractMap实现了”键值对”的通用函数接口。
HashMap是通过”拉链法”实现的哈希表。它包括几个重要的成员变量:table, size, threshold, loadFactor, modCount。
table是一个Entry[]数组类型,而Entry实际上就是一个单向链表。哈希表的”key-value键值对”都是存储在Entry数组中的。
size是HashMap的大小,它是HashMap保存的键值对的数量。
threshold是HashMap的阈值,用于判断是否需要调整HashMap的容量。threshold的值=”当前最大容量*加载因子”,当HashMap中存储数据的数量达到threshold时,就需要将HashMap的容量加倍。
loadFactor就是加载因子。
modCount是记录发生内部结构变化的次数,如果是put但是put的值是覆盖原有的值,这样不算是内部结构变化;是用来实现fail-fast机制的。如果在 Iterator 过程中,并发的对集合进行修改,此时会报ConcurrentModificationException异常 => 即线程不安全
1 | package java.util; |
2. Put 方法实现
- table[] 是否为空
- 判断 table[i] 位置是否插入过值
- 判断链表长度是否大于8,如果大于就转换为红黑二叉树,并插入树中
- 判断key是否和原有key相同,如果相同就覆盖原有key的value,并返回原有value
- 如果key不相同,就插入一个key,记录结构变化一次
1 | final V putVal(int hash, K key, V value, boolean onlyIfAbsent, |
3. Get 方法实现
- 判断表或key是否是null,如果是直接返回null key对应的value
- 判断索引处第一个key与传入key是否相等,如果相等直接返回
- 如果不相等,判断链表是否是红黑二叉树,如果是,直接从树中取值
- 如果不是树,就遍历链表查找
1 | final Node<K,V> getNode(int hash, Object key) { |
4. table 的初始化时机是什么时候
- 一般情况下,在第一次 put 的时候,调用 resize 方法进行 table 的初始化(懒初始化,懒加载思想在很多框架中都有应用!)
5. 初始化的 table.length 是多少、阀值(threshold)是多少,实际能容下多少元素
- 默认情况下,table.length = 16; 指定了 initialCapacity 的情况放到问题 5 中分析
- 默认情况下,threshold = 12; 指定了 initialCapacity 的情况放到问题 5 中分析
- 默认情况下,能存放 12 个元素,当存放第 13 个元素后进行扩容
6. 什么时候触发扩容,扩容之后的 table.length、阀值各是多少
- 当 size > threshold 的时候进行扩容
- 扩容之后的 table.length = 旧 table.length * 2,
- 扩容之后的 threshold = 旧 threshold * 2