Java笔记之HashMap保存数据

Photo by Pixabay from Pexels

HashMap使用由Node<K,V>(继承自Map.Entry<K,V>)组成的数组table保存数据。

table中保存数据时根据keyhashCode计算到一个随机保存位置(但都在table数组的大小范围内),当存储的数据总量超过加载系数loadFactor规定的阈值时则对table进行扩容

HashMap有以下全局变量

1
2
3
4
5
6
7
transient Node<K,V>[] table;//实际保存键值对的数组
transient Set<Map.Entry<K,V>> entrySet;//Holds cached entrySet().用来遍历HashMap
transient int size;//本HashMap实际保存的键值对个数
transient int modCount;//HashMap修改的次数,每次修改HashMap都会叠加,
//用来在遍历的过程中检查HashMap是否被改动过来,如果有则抛出异常ConcurrentModificationException
int threshold;//是否扩容的阈值
final float loadFactor;//加载系数,默认0.75f

loadFactor:默认的负载因子0.75是对空间和时间效率的一个平衡选择,建议大家不要修改,除非在时间和空间比较特殊的情况下:

如果内存空间很多而又对时间效率要求很高,可以降低负载因子Load factor的值;

相反,如果内存空间紧张而对时间效率要求不高,可以增加负载因子loadFactor的值,这个值可以大于1。

https://tech.meituan.com/2016/06/24/java-hashmap.html

每个Node包含了以下信息:

1
2
3
4
5
6
Node<K,V> implements Map.Entry<K,V>{
final int hash;
final K key;
V value;
Node<K,V> next;
}

在执行hashMap.put("k", "v");时,会先计算keyhash

1
2
3
4
5
6
7
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
//这里原始hash值(32位)的高位和地位进行按位异或(不同为,相同为0),
//增加了随机性,避免因为hashCode计算得到的hash值(低位相同概率高)
//计算索引时(见下文↓)一直取低位值而可能导致的索引一直的重复问题。
}

V put(K key, V value)

使用HashMap保存数据时:

  1. 使用hash(Object key)计算keyhash

  2. 通过hash值计算value应该保存的位置i

    1
    2
    3
    i = (table.length - 1) & hash
    //由于table.length限定为2的n次方,所以上面的等式相当于给table.length取余数
    //即i永远<=table.length

    在此时会判断是否需要扩容(只有table为空,或者当前存储的数据总数size大于阈值threshold时才会扩容resize())

    1
    2
    threshold = capacity * loadFactor
    阈值 = 容量 * 负载系数(默认为0.75
  3. 接下来会插入数据

    • 指定位置为空(没有hash冲突),或已有key相同的值:则直接插入value
    • 已经存在值并且数量大于8:则将链表转化为红黑树(JDK1.8),否则以链表形式保存数据
    • 在移除数据时,如果红黑树数量小于6:则将红黑树转化为链表

在JDK1.7中,数据以数组或链表形式保存,JDK1.8中则新增了红黑树。

发生hash冲突时,JDK1.7采用采用头插法,可能会产生逆序和环形链表;JDK1.8采用尾插法,直接插入链表或红黑树尾部。

具体JDK1.7与1.8对比查看这里

V get(Object key)

使用HashMap获取数据时:

  1. 计算key的hash值

  2. 查找对应位置的node

    • null:返回null

    • node不为空且key一致:返回该node

    • node不为空且key不一致:

      如果是链表:遍历链表查找是否存在与key一致的node

      如果是:遍历树查找是否存在与key一致的node

V remove(Object key)

使用HashMap移除数据时:

其大体过程与get(Object key)类似,遍历找到对应的node并删除。

计算索引

一个key对应的索引index是由这个keyhash()值对HashMap的数组长度length的余数:

1
index = hash % length;

又有Length为2^n^时:

hash % 2^n^ = hash & ( 2^n^ - 1)

hash % 2^n^ = hash - (hash / 2^n^) 2^n^
= hash - (hash>>n)
2^n^
= hash & ( 2^n^ - 1)

HashMap的长度Length又只能是2^n^,所以:

1
index = (length - 1) & hash;

保存值

  • table为空或者长度超过加载因子DEFAULT_LOAD_FACTOR规定的容量(默认容量为16,加载因子为0.75)时会自动扩容。

  • table[index]为空时,直接新建Node并保存到table[index]中。

  • table[index]不为空时:

    • 如果是同一个key则覆盖旧的值
    • 如果是不同的key则先尝试以链表保存数据
    • 如果是不同的key,并且链表长度超过MIN_TREEIFY_CAPACITY规定的长度(默认64),则将链表转化为红黑树(JDK1.8新增)

序列化

第一节我们可以看到,HashMap的很多变量都被标记为transient,这表示在Serializable序列化时不主动去序列化这些值,那这样岂不是没法反序列化这些数据了?

其实在后面我们可以看到,HashMapwriteObject()方法中主动保存了部分数据(原因是默认的Serializable由于不同JVM实现对同一对象如StringHashCode不一定一致,会导致严重的问题——HashMap基于hash值保存数据):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
private void writeObject(java.io.ObjectOutputStream s)
throws IOException {
int buckets = capacity();//容量
// Write out the threshold, loadfactor, and any hidden stuff
s.defaultWriteObject();
s.writeInt(buckets);
s.writeInt(size);//保存size
internalWriteEntries(s);//保存table数据
}

/**
* table不为空则返回table长度
* 否则threshold不为空则返回threshold
* 否则返回默认的DEFAULT_INITIAL_CAPACITY
*/
final int capacity() {
return (table != null) ? table.length :
(threshold > 0) ? threshold :
DEFAULT_INITIAL_CAPACITY;
}

并在readObject()恢复了这些值。

位运算

位运算 符号 计算
按位与 & 相同为1,不同为0
按位或 | 有1则1
按位异或 ^ 相同为0,不同位1
按位取反 ~
左移 << 相当于乘以2^n^
右移 >> 相当于除以2^n^
无符号右移 >>>

参考资料

HashCode计算扰动分析-关于hashMap的一些按位与计算的问题? - 胖君的回答 - 知乎

一文读懂Java之HashMap索引位置计算

hashMap在jdk1.7与jdk1.8中的原理及不同

真实面试题之:Hashmap的结构,1.7和1.8有哪些区别

Java 8系列之重新认识HashMap

java.util.HashMap源码要点浅析

Why HashMap.Entry is transient?

Java中HashMap关键字transient的疑惑