目录
HashMap 概述
内部字段及构造方法
存储元素
扩容
取出元素
删除元素
判断
总结
HashMap 概述
前面我们分析了基于数组实现的 ArrayList 和基于双向链表实现的 LinkedList, 它们各有优缺点: ArrayList 查找元素快但是插入删除元素慢, LinkedList 插入删除元素快但是查找元素慢. 那么有没有一种数据对象能够做到高效的查询和插入删除呢? 答案是有的, HashMap 就能够很好的满足这个特性.
由于 JDK1.8 对 HashMap 进行了优化, 与 JDK1.7 版本的实现有很大的不同, 相对来说也要负责一些, 故本文以 JDK1.7 版本的 HashMap 为基础进行分析, 主要分析 HashMap 的内部结构及插入扩容原理; 将在下一篇文章分析 JDK1.8 版本的 HashMap 带来了那些改进和优化.
JDK api 是这样介绍 HashMap 的:
Hash table based implementation of the Map interface. This implementation provides all of the optional map operations, and permits null values and the null key. (The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.
大意是 HashMap 是基于哈希表对 Map 接口的实现, 此实现提供所有可选的映射操作, 并允许使用 null 值和 null 键.(除了是线程不安全的和允许 null 键值对插入, HashMap 大致等同于 HashTable),HashMap 不保证映射的顺序, 特别是它不保证该顺序恒久不变.
HashMap 数据结构
画了个示意图如下, 由图可知, HashMap 基于数组和单链表实现. 使用过 HashMap 都知道, 它储存的是键值对, 当我们存储键值对时, 先根据哈希算法计算出哈希值, 根据计算出来的哈希值映射到数组上得到一个索引, 可能会有多个对象映射到同一个索引上, 就是图片上出现单链表的情况, 这时候就产生了哈希冲突, 一个好的算法能够尽量避免哈希冲突. 根据哈希值, HashMap 能够以几乎 O(1)的复杂度存储或查询元素, 效率相当高.
HashMap 继承结构
HashMap 继承了 AbstractMap 类, 并实现了 Map,Cloneable 和 Serializable 接口. AbstractMap 提供了 Map 接口的抽象实现, 并提供了一些方法的基本实现. 注意, Map 接口属于集合框架, 但并没有继承 Collection 接口, 实际上 Map 接口是与 Collection 接口同级别的接口.
内部字段及构造方法
Entry 类
键值对 Entry 对象存储了键值对 key-value, 这里的 next 属性指向发生哈希冲突了的键值对对象.
- static class Entry<K,V> implements Map.Entry<K,V> {
- // 键对象, final 修饰, 不可变
- final K key;
- // 值对象
- V value;
- // 下一个键值对 Entry 对象
- Entry<K,V> next;
- // 键对象的哈希值
- int hash;
- // 提供了一个有参构造方法
- Entry(int h, K k, V v, Entry<K,V> n) {
- value = v;
- next = n;
- key = k;
- hash = h;
- }
- }
字段属性
HashMap 的底层是由数组和链表实现的, JDK 注释中把 Entry 数组称为桶, 这里规定了桶的默认容量和最大容量. 对于桶的容量 JDK 官方注释都会有这么一句: MUST be a power of two, 桶的容量一定要是 2 的幂次, 这里先说结论: 桶的容量是 2 的 N 次方能够减少哈希冲突, 提高桶的利用率, 至于原因我们会在后面分析.
加载因子 loadFactor 和阈值 threshold 是一对密不可分的概念, 在当前桶的容量下, 存储键值对个数超过 threshold 就会进行扩容, 阈值 threshold 等于桶的容量乘以加载因子; 加载因子一般我们就用默认的 0.75f, 加载因子设置的太小, 桶的利用率低, 而且频繁扩容也会降低 HashMap 的性能, 设置的加载因子太大, 键值对越存越多容易发生哈希冲突, 所以 0.75 是时间复杂度与空间复杂度的一个平衡点.
- // 桶的初始化默认的长度
- static final int DEFAULT_INITIAL_CAPACITY = 16;
- // 桶的最大长度
- static final int MAXIMUM_CAPACITY = 1 <<30;
- // 默认加载因子
- static final float DEFAULT_LOAD_FACTOR = 0.75f;
- //Entry 数组, 空桶
- transient Entry<K,V>[] table;
- // 储存元素个数
- transient int size;
- // 桶内存储键值对个数的阈值, 超过阈值对桶进行 resize
- int threshold;
- // 加载因子
- final float loadFactor;
- // 确保 fail-fast 机制
- transient int modCount;
- // 备选的负载值, 以 String 作为 Key 时的备选负载值.
- static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
构造方法
我们常用的雾草构造器, 会调用的 HashMap(int initialCapacity, float loadFactor)构造方法, 按照默认初始容量为 16, 加载因子为 0.75 构造 HashMap 对象.
- public HashMap(int initialCapacity, float loadFactor) {
- // 检查参数有效性
- if (initialCapacity <0)
- throw new IllegalArgumentException("Illegal initial capacity:" +
- initialCapacity);
- if (initialCapacity> MAXIMUM_CAPACITY)
- initialCapacity = MAXIMUM_CAPACITY;
- if (loadFactor <= 0 || Float.isNaN(loadFactor))
- throw new IllegalArgumentException("Illegal load factor:" +
- loadFactor);
- // Find a power of 2>= initialCapacity
- // 注意这个容量并不是直接用输入的参数, 而是通过循环左移找到比 initialCapacity
- // 且离它最近的 2 的幂次. 如输入 12, 容量初始化为 16
- int capacity = 1;
- while (capacity <initialCapacity)
- capacity <<= 1;
- this.loadFactor = loadFactor;
- // 阈值等于桶的容量乘以加载因子(不超过最大容量)
- threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
- table = new Entry[capacity];
- useAltHashing = sun.misc.VM.isBooted() &&
- (capacity>= Holder.ALTERNATIVE_HASHING_THRESHOLD);
- // 空方法
- init();
- }
- // 生成一个空的 HashMap, 容量大小使用默认值 16, 负载因子使用默认值 0.75
- public HashMap() {
- this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
- }
- // 生成一个空的 HashMap, 并指定其容量大小, 负载因子使用默认的 0.75
- public HashMap(int initialCapacity) {
- this(initialCapacity, DEFAULT_LOAD_FACTOR);
- }
- public HashMap(Map<? extends K, ? extends V> m) {
- // 实际容量为 m.size/0.75 和 16 较大者, 0.75f 作为加载因子
- this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
- DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
- // 将传入的子 Map 中的全部元素逐个添加到 HashMap 中
- putAllForCreate(m);
- }
存储元素
put(K key, V value)
put(K key, V value)方法将传入的键值对存到 HashMap 中, 如果 HashMap 存在键相同的键值对, 就将这个键值对覆盖, 返回被覆盖键值对的值. 首先检查键值对的键是否为 null, 是的话调用 putForNullKey 方法. 如果不是通过 hash 方法得到键 key 的值, 通过 indexFor 方法得到键值对映射到桶的索引, 在得到了这个索引后, 使用 for 循环去这个索引找这个桶里是否已经存放了键值对, 如果已经有键值对, 就对这个单向链表遍历, 看是否有键值对的键与传入的 key 相同, 判断条件: e.hash == hash && ((k = e.key) == key || key.equals(k)), 找到了就替换, 找不到调用 addEntry 方法插入到桶中.
通过以上分析, HashMap 在发生了哈希冲突后是以链表的形式仍然保存到桶中, 就是我们俗称的拉链法. 对于这里的哈希冲突指的是键值对键的哈希值通过 indexFor 方法得到一个索引值(其实就是哈希值对桶的容量取余), 放到同一个桶的键值对并不一定哈希值就相等, 但哈希值相等一定会放到同一个桶中. 当然我会在 indexFor 这个方法分析的, putForNullKey 方法与 put 方法流程大致相同, 只不过 null 的哈希值不需要计算, 直接规定为 0.
indexFor 方法传入键的哈希值和桶的容量, 那么是怎么映射得到在桶中的索引呢? 其实就一句话: h & (length-1). 注意 length 一定是 2 的幂次, 我们假设为 16, 那么哈希值就要与 15 每一位相与, 15 的二进制形式为 1111, 就相当于保留哈希值第一位到第四位, 就是哈希值与 16 取余的效果. 而桶的容量始终为 2 的幂次, 那么哈希值都要与每一位都是一的二进制做 &
即相当于: h%length, 所以发生哈希冲突并不代表哈希值相同, 只是哈希值与桶的容量取余的所得到的索引相同
- public V put(K key, V value) {
- if (key == null)
- return putForNullKey(value);
- int hash = hash(key);
- int i = indexFor(hash, table.length);
- // 如果 table[i]这个桶中存放有元素, 查找有没有含有键为 key 的键值对,
- // 存在则替换
- for (Entry<K,V> e = table[i]; e != null; e = e.next) {
- Object k;
- if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
- V oldValue = e.value;
- e.value = value;
- e.recordAccess(this);
- return oldValue;
- }
- }
- modCount++;
- // 桶中不存在指定键, 则调用 addEntry 方法添加向桶中添加新结点
- addEntry(hash, key, value, i);
- return null;
- }
- private V putForNullKey(V value) {
- // 如果有 key 为 null 的键值对, 替换值
- for (Entry<K,V> e = table[0]; e != null; e = e.next) {
- if (e.key == null) {
- V oldValue = e.value;
- e.value = value;
- e.recordAccess(this);
- return oldValue;
- }
- }
- modCount++;
- // 桶中不存在 null 键, 则调用 addEntry 方法添加向桶中添加新结点
- addEntry(0, null, value, 0);
- return null;
- }
- final int hash(Object k) {
- int h = 0;
- if (useAltHashing) {
- if (k instanceof String) {
- return sun.misc.Hashing.stringHash32((String) k);
- }
- h = hashSeed;
- }
- // 一次散列, 调用 k 的 hashCode 方法, 与 hashSeed 做异或操作
- h ^= k.hashCode();
- // 二次散列
- h ^= (h>>> 20) ^ (h>>> 12);
- return h ^ (h>>> 7) ^ (h>>> 4);
- }
- static int indexFor(int h, int length) {
- return h & (length-1);
- }
- void addEntry(int hash, K key, V value, int bucketIndex) {
- // 如果 HashMap 中条目的数量达到了重构阈值且指定的桶不为 null, 则对 HashMap 进行扩容(即增加桶的数量)
- if ((size>= threshold) && (null != table[bucketIndex])) {
- // 调用 resize 方法对 HashMap 进行扩容
- resize(2 * table.length);
- hash = (null != key) ? hash(key) : 0;
- // 桶的数量增加, 重新计算索引
- bucketIndex = indexFor(hash, table.length);
- }
- createEntry(hash, key, value, bucketIndex);
- }
- void createEntry(int hash, K key, V value, int bucketIndex) {
- // 保存桶中已有元素 e
- Entry<K,V> e = table[bucketIndex];
- // 新元素插入桶中, 把 next 指向
- table[bucketIndex] = new Entry<>(hash, key, value, e);
- size++;
- }
- putAll(Map<? extends K, ? extends V> m)
构造方法 HashMap(Map<? extends K, ? extends V> m)调用的是 putAll 方法, putAll 方法把传入的 Map 对象保存的元素插入到 HashMap 里面.
- public void putAll(Map<? extends K, ? extends V> m) {
- int numKeysToBeAdded = m.size();
- if (numKeysToBeAdded == 0)
- return;
- // 如果 Map 包含的键值对个数大于 thrshold, 先扩容
- if (numKeysToBeAdded> threshold) {
- int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
- if (targetCapacity> MAXIMUM_CAPACITY)
- targetCapacity = MAXIMUM_CAPACITY;
- int newCapacity = table.length;
- while (newCapacity <targetCapacity)
- newCapacity <<= 1;
- if (newCapacity> table.length)
- resize(newCapacity);
- }
- // 调用 put 方法将键值对放入 HashMap 总
- for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
- put(e.getKey(), e.getValue());
- }
扩容
resize(int newCapacity)
risize 扩容方法没有访问修饰符修饰, 我们在外部是无法调用的. 每次扩容在以前的容量的基础上扩大两倍(从 addEntry 方法可以看出), 扩容分为两部, 构建一个新的 Entry 数组(桶), 调用 transfer 方法将老数组 oldTable 的数据转移到新数组 newTable 中.
transfer 源码如下, for 循环遍历每一个桶, while 循环遍历桶中链表, 如果桶中键值对 e 不为空 (e!=null), 先保存 e 的下一个键值对 next, 重新计算 e 的索引, 把 e 的 next 指向整个 newTable[i] 保存的数据, 在把 e 放到新的桶中, 下面 table[0]元素转移到新桶做了简单的图帮助理解:
由于新插入的元素 e 的 next 指向桶中元素, 所以新的桶中的元素顺序会倒过来. 其实这个图并不严谨, 因为元素从旧桶转移到新桶会按照新桶的容量重新计算索引, 所以老桶中 table[0]并不一定会被映射到新桶的 table[0].
可以看到, HashMap 使用 riseize 扩容, 在原来的容量基础上扩大两倍, 对原来每一个键值对键重新计算哈希值和索引, 然后再移到新桶中, 这是很消耗性能的. 另外, 由于 HashMap 是线程不安全的, 在多线程环境下 transfer 可能会引发死循环问题, 有兴趣的可以了解一下: 不正确地使用 HashMap 引发死循环及元素丢失.
- void resize(int newCapacity) {
- // 保存扩容前的桶
- Entry[] oldTable = table;
- int oldCapacity = oldTable.length;
- // 如果目前的容量已经达到了 MAXIMUM_CAPACITY, 不会扩容, 把 threshold 设置为 Integer.MAX_VALUE
- if (oldCapacity == MAXIMUM_CAPACITY) {
- threshold = Integer.MAX_VALUE;
- return;
- }
- Entry[] newTable = new Entry[newCapacity];
- // 计算是否需要对键重新进行哈希码的计算
- boolean oldAltHashing = useAltHashing;
- useAltHashing |= sun.misc.VM.isBooted() &&
- (newCapacity>= Holder.ALTERNATIVE_HASHING_THRESHOLD);
- boolean rehash = oldAltHashing ^ useAltHashing;
- /**
- * 将原有所有的桶迁移至新的桶数组中, 在迁移时, 桶在桶数组中的绝对位置可能会发生变化
- */
- transfer(newTable, rehash);
- table = newTable;
- // 像构造方法中一样来重新计算阈值
- threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
- }
- void transfer(Entry[] newTable, boolean rehash) {
- int newCapacity = newTable.length;
- for (Entry<K,V> e : table) {
- while(null != e) {
- Entry<K,V> next = e.next;
- if (rehash) {
- e.hash = null == e.key ? 0 : hash(e.key);
- }
- // 桶的容量增加了, 重新计算索引
- int i = indexFor(e.hash, newCapacity);
- // 把 e 的 next 指向整个 newTable[i]保存的数据
- e.next = newTable[i];
- // 把 e 放到桶中.
- newTable[i] = e;
- e = next;
- }
- }
- }
取出元素
get(Object key)
之前我们在分析 ArrayList 源码的时候, 因为 ArrayList 基于数组实现的所以根据索引查找非常快. 而 HashMap 根据键值对键的哈希值计算得到一个索引, 在不考虑哈希冲突的情况下, 也能够以 O(1)的时间复杂度找到键值对, 具有很高的性能.
- public V get(Object key) {
- // 若键为 null
- if (key == null)
- return getForNullKey();
- Entry<K,V> entry = getEntry(key);
- return null == entry ? null : entry.getValue();
- }
- private V getForNullKey() {
- // 规定 null 的 hash 为 0, 在 table[0]这个桶里面找键为 null 的键值对
- for (Entry<K,V> e = table[0]; e != null; e = e.next) {
- // 遍历寻找键为 null 的键值对
- if (e.key == null)
- return e.value;
- }
- return null;
- }
- final Entry<K,V> getEntry(Object key) {
- // 根据键值得到键值对所在桶的索引
- int hash = (key == null) ? 0 : hash(key);
- // 计算出索引, 遍历桶中元素, 在不发生哈希冲突的情况下, 第一个元素就能找到了.
- for (Entry<K,V> e = table[indexFor(hash, table.length)];
- e != null;
- e = e.next) {
- Object k;
- // 条件: 比较键的 hash 值是否相等且键是否 == 或 equals
- if (e.hash == hash &&
- ((k = e.key) == key || (key != null && key.equals(k))))
- return e;
- }
- return null;
- }
删除元素
remove(Object key)
remove 方法根据传入的键从 HashMap 移除键值对, 并返回键值对的值.
- public V remove(Object key) {
- // 调用 removeEntryForKey 方法
- Entry<K,V> e = removeEntryForKey(key);
- return (e == null ? null : e.value);
- }
- final Entry<K,V> removeEntryForKey(Object key) {
- int hash = (key == null) ? 0 : hash(key);
- int i = indexFor(hash, table.length);
- Entry<K,V> prev = table[i];
- Entry<K,V> e = prev;
- while (e != null) {
- Entry<K,V> next = e.next;
- Object k;
- // 如果找到了, 就将键值对从链表删除, 这里面一大串就是单链表的删除元素
- if (e.hash == hash &&
- ((k = e.key) == key || (key != null && key.equals(k)))) {
- modCount++;
- size--;
- if (prev == e)
- table[i] = next;
- else
- prev.next = next;
- e.recordRemoval(this);
- return e;
- }
- prev = e;
- e = next;
- }
- return e;
- }
判断
- isEmpty()
- public boolean isEmpty() {
- //HashMap 的 size 为 0, 则为空
- return size == 0;
- }
- containsKey(Object key)
- public boolean containsKey(Object key) {
- // 直接调用 getEntry 方法, 判断返回的键值对是否为 null
- return getEntry(key) != null;
- }
- containsValue(Object value)
- public boolean containsValue(Object value) {
- // 判断 value 是否为 null, 如果是调用 containsNullValue 方法
- if (value == null)
- return containsNullValue();
- // 遍历寻找
- Entry[] tab = table;
- for (int i = 0; i < tab.length ; i++)
- for (Entry e = tab[i] ; e != null ; e = e.next)
- if (value.equals(e.value))
- return true;
- return false;
- }
- private boolean containsNullValue() {
- Entry[] tab = table;
- for (int i = 0; i < tab.length ; i++)
- for (Entry e = tab[i] ; e != null ; e = e.next)
- if (e.value == null)
- return true;
- return false;
- }
总结
HashMap 基于数组加单向链表实现, 以 Key-Value 键值对存储数据, 在不考虑哈希冲突的情况下能够以 O(1)的复杂度进行存储, 查询, 删除元素, 它通过巧妙的设计结合了 ArrayList 和 LinkedList 的优点. HashMap 是线程不安全的, 所以不建议在多线程环境下使用. JDK8 中对 HashMap 的实现进行了改进, 加入了红黑树的设计, 将在下一篇文章中介绍.
来源: https://www.cnblogs.com/rain4j/p/9380606.html