Java笔记之HashMap保存数据

Photo by **Pixabay **from Pexels
HashMap
使用由Node<K,V>
(继承自Map.Entry<K,V>
)组成的数组table
保存数据。
在table
中保存数据时根据key
的hashCode
计算到一个随机保存位置(但都在table
数组的大小范围内),当存储的数据总量超过加载系数loadFactor
规定的阈值时则对table
进行扩容。
HashMap有以下全局变量
1 | transient Node<K,V>[] table;//实际保存键值对的数组 |
loadFactor
:默认的负载因子0.75是对空间和时间效率的一个平衡选择,建议大家不要修改,除非在时间和空间比较特殊的情况下:如果内存空间很多而又对时间效率要求很高,可以降低负载因子Load factor的值;
相反,如果内存空间紧张而对时间效率要求不高,可以增加负载因子
loadFactor
的值,这个值可以大于1。
每个Node
包含了以下信息:
1 | Node<K,V> implements Map.Entry<K,V>{ |
在执行hashMap.put("k", "v");
时,会先计算key
的hash
值
1 | static final int hash(Object key) { |
V put(K key, V value)
使用HashMap
保存数据时:
使用
hash(Object key)
计算key
的hash
值通过
hash
值计算value
应该保存的位置i
1
2
3i = (table.length - 1) & hash
//由于table.length限定为2的n次方,所以上面的等式相当于给table.length取余数
//即i永远<=table.length在此时会判断是否需要扩容(只有
table
为空,或者当前存储的数据总数size
大于阈值threshold
时才会扩容resize()
)1
2threshold = capacity * loadFactor
阈值 = 容量 * 负载系数(默认为0.75)接下来会插入数据
- 指定位置为空(没有hash冲突),或已有
key
相同的值:则直接插入value
- 已经存在值并且数量大于8:则将链表转化为红黑树(JDK1.8),否则以链表形式保存数据
- 在移除数据时,如果红黑树数量小于6:则将红黑树转化为链表
- 指定位置为空(没有hash冲突),或已有
在JDK1.7中,数据以数组或链表形式保存,JDK1.8中则新增了红黑树。
发生hash冲突时,JDK1.7采用采用头插法,可能会产生逆序和环形链表;JDK1.8采用尾插法,直接插入链表或红黑树尾部。
具体JDK1.7与1.8对比查看这里
V get(Object key)
使用HashMap
获取数据时:
计算key的
hash值
查找对应位置的
node
null
:返回null
node
不为空且key
一致:返回该node
node
不为空且key
不一致:如果是链表:遍历链表查找是否存在与
key
一致的node
如果是树:遍历树查找是否存在与
key
一致的node
V remove(Object key)
使用HashMap
移除数据时:
其大体过程与get(Object key)
类似,遍历找到对应的node
并删除。
计算索引
一个key
对应的索引index
是由这个key
的hash()
值对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
序列化时不主动去序列化这些值,那这样岂不是没法反序列化这些数据了?
其实在后面我们可以看到,**HashMap
在writeObject()
方法中主动保存了部分数据**(原因是默认的Serializable
由于不同JVM实现对同一对象如String
的HashCode
不一定一致,会导致严重的问题——HashMap
基于hash
值保存数据):
1 | private void writeObject(java.io.ObjectOutputStream s) |
并在readObject()
恢复了这些值。
位运算
位运算 | 符号 | 计算 |
---|---|---|
按位与 | & | 相同为1,不同为0 |
按位或 | | | 有1则1 |
按位异或 | ^ | 相同为0,不同位1 |
按位取反 | ~ | |
左移 | << | 相当于乘以2^n^ |
右移 | >> |
相当于除以2^n^ |
无符号右移 | >>> |
参考资料
HashCode计算扰动分析-关于hashMap的一些按位与计算的问题? - 胖君的回答 - 知乎
真实面试题之:Hashmap的结构,1.7和1.8有哪些区别