HashMap源码解读(面试题剖析)
【摘要】 HashMap源码深度剖析，对几个有意思的方法进行了分析，如初始化容量如果转换为2的n次幂，扩容过程，存储和获取对象方法，以及面试题的总结
HashMap源码解读(面试题剖析)
1. HashMap继承关系
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
1.1 继承AbstractMap
AbstractMap实现了Map接口，提供了Map中接口的基本实现。
1.2 实现接口
-
Map<K,V>
最基本的接口，它表示将键映射到值的对象。一个映射中不能包含重复的键，每个键对应到唯一的一个值。
-
Cloneable
Object.clone()：它允许在堆中克隆出一块和原对象一样的对象，并将这个对象的地址赋予新的引用。
Java 中 一个类要实现clone功能 必须实现 Cloneable接口，否则在调用 clone() 时会报 CloneNotSupportedException 异常。clone方法是一个native方法，简单地讲，一个Native Method就是一个java调用非java代码的接口
-
Serializable：详解
序列化接口，标记接口（Marker Interface），实现了标记接口的类仅仅是给自身贴了个”标记“，未实现该接口无法被序列化。
2. 实现原理
- 基于hash原理，使用put(key,value)和get(key)方法存储和获取对象。
- 当存储对象时，将键值对传递给put(key,value)方法时，他调用对象key的hashCode方法来计算key的hashCode，然后找到bucket位置，来存储对象value。
- 获取存储对象，先计算key的hashCode，找到数组中对应位置的bucket位置，然后通过key的equals方法找到正确的键值对，然后返回对象的value。
- HashMap使用链表来解决hash碰撞问题，当发生碰撞了，对象将会存储在链表的下一个节点中。每个链表节点中，存储key-value对象，也就是当两个不同的键对象key的hashCode相同时，他们会存储在同一个bucket位置的链表上（JDK8链表长度大于8变为红黑树），取数据可通过键对象key和equals()方法来找到正确的键值对key-value。
3. 核心成员变量
- DEFAULT_INITIAL_CAPACITY：默认容量16。
- MAXIMUM_CAPACITY：最大容量1<<30。
- DEFAULT_LOAD_FACTOR：默认装载因子。
JDK7
- Entry[] table：这个Entry类型的数组存储了HashMap的真正数据
- size大小：代表HashMap内存储了多少个键值对。
- capacity容量：实际上HashMap没有一个成员变量叫capacity，他是作为table这个数组的大小而隐式存在。
- threshold阈值和loadFactor装载因子：threshold是通过capacity*loadFactor得到的。当size超过threshold（刚好相等时不会扩容），HashMap扩容会再次计算每个元素的哈希位置。
- enreySet、keySet和values这三个都是一种视图，真正的数据都来自table。
JDK8
- Node[] table。这个Node类型的数组存储了HashMap的真正数据static class Node<key,value> implements Map.Entry<key,value>。
- size大小。代表HashMap内存储了多少个键值对。
- capacity容量。实际上HashMap没有一个成员叫capacity，他是作为table这个数组的大小而隐式存在。
- threshold和loadFactor装载因子。threshold是通过capacity*loadFactor得到的。当size超过threshold时（刚好相等时不会扩容），HashMap会扩容哈希计算比之前有改进。
- enreySet、keySet和values这三个都是一种视图，真正的数据都来自table。
- TREEIFY_THRESHOLD 转换成红黑树的临界值，默认8
- UNTREEIFY_THRESHOLD 红黑树转换成链表的临界值，默认6
- MIN_TREEIFY_CAPACITY 最小树形化阈值，默认64
4. 构造方法
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);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
入参initialCapacity：设置阈值，即HashMap中Node数组的长度，此处只是给threshold属性赋值，初始化数组的位置在resize()方法中。
这里直接将计算好的容量设置给了threshold，并没有乘以装载因子，在第一次put数据的时候会将threshold乘上装载因子
入参loadFactor：装载因子，设置装载因子，默认0.75。
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
只设置阈值，使用默认装载因子调用上面的重载构造。
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
全部使用默认设置
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
使用另一个Map构造HashMap
5. 关键方法解析
5.1 tableSizeFor(int cap)
第一个构造方法设置threshold时调用的方法
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
非常巧妙的方法：目的：初始化数组大小为大于cap且最接近cap的2的n次幂的值，即3->4，6->8，19->32。
解析：
- cap转换为二进制最高位肯定是1（我看谁想不到）
- n |= n >>> 1得到的结果最高两位肯定是1。
- 循环到n |= n >>> 16，最终得到高32位全是1，int只有32位。
- 开始的cap-1是处理边界条件，如果入参为8，本身就是2的n次幂，不减1，计算结果会是16，明显是错误的。
5.2 get(Object key)
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
调用getNode方法，入参为key的hash值和key本身。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
对hashCode进行一次扰动，即hash值等于key的HashCode异或HashCode右移16位，目的是将高16位右移加大低位的随机性。读一下方法注释，大致意思是，散列集本身都已经合理分布（无法从扩展中获得利益），而且hashMap使用树来解决容器的冲突，所以只需要进行简单扰动，以减少系统性能损耗。
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
first = tab[(n - 1) & hash]：n-1按位与hash，n是数组的长度即为2的x次幂，n-1换算为二进制数一定是一个全1的值，如，n=8，n-1二进制为111。按位与的结果，因为n-1高位为0，低位为1，所以只保留hash值的低位数据。即n-1按位与hash等同于hash%(n-1)。
即，通过key的HashCode计算的Hash值找到key的bucket位置。（重点理解）
first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k)))：key等于或者equals链表头的key，则返回链表头。
((TreeNode<K,V>)first).getTreeNode(hash, key)：如果是红黑树，则调用getTreeNode，遍历红黑树。
否则执行While循环，遍历链表找到对应的Node节点。
5.3 put(K key, V value)
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
调用putVal，传入key的hash,key,value。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 如果数组为空或者长度为0，调用resize方法初始化数组
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 如果不存在hash冲突，直接赋值
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 如果链表头结点p,key和put的key相同，赋值p节点引用到e
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 如果p是红黑树，调用putTreeVal
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 否则，遍历链表
for (int binCount = 0; ; ++binCount) {
// 找到尾部节点，赋值
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 连表长度大于等于8，转换为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// e经过上面的if判断已经被赋值为当前遍历的节点
// 如果e节点key和put的key相同跳出循环
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 存在已有key和传入的key相同
if (e != null) { // existing mapping for key
V oldValue = e.value;
// 入参onlyIfAbsent，是否替换已有值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
// 返回被替换掉的值
return oldValue;
}
}
++modCount;
// 长度大于阈值，扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
5.4 resize()
首先明确一点:
JDK8中Node数组长度永远是2的N次幂，
然后计算元素位置的方法是(length-1)&hash，
如4扩容到8，length-1化作二进制数即为11->111
按位与的结果就是高位多取了一位hash值，此值可能是0也可能是1，
0即该值在扩容后与扩容前的数组位置不变，1则表示该值扩容后的数组位置为原位置加原数组长度
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
// 第一次put时oldCap=0
if (oldCap > 0) {
// 已达到最大值，不扩容
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 扩容后小于最大值，且oldCap大于等于16，翻倍，阈值翻倍操作属于模糊计算
// 故存在oldCap大于等于16才翻倍的操作
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// 初始化时将计算好的capacity赋值到了threshold
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
// capacity和threshold都是zero，使用默认值
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// newCap>=MAXIMUM_CAPACITY或oldCap小于16或第一次put即if (oldThr > 0)这个if中
// 精准计算newThr
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// 赋值threshold
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
// 创建新的table
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
// 方法第一行代码已经将table保存在oldTab
table = newTab;
if (oldTab != null) {
// oldCap:老数组长度
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
// 该桶位置只有一个数据
if (e.next == null)
// 根据刚开始明确的信息，扩容就是把一个桶的数据分别放到两个桶，且是一一对应的，
// 所以原桶只有一个数据，扩容后要放的地方一定是空的。
newTab[e.hash & (newCap - 1)] = e;
// 桶位置是树
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
// 一桶拆两桶
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// oldCap，2的n次方的数，此处未减一，按位与==0放在原桶
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 放在原桶
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 放在原桶位置加上原数组长度的位置
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
红黑树的处理，也是遍历后放到两个桶里，不过会有一个链表和树转换的过程
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;
// Relink into lo and hi lists, preserving order
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;
// 遍历放到两个红黑树中
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next;
e.next = null;
if ((e.hash & bit) == 0) {
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
}
else {
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
// 判断是否长度小于6，小于的话转换回链表
if (loHead != null) {
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
if (hiHead != null) // (else is already treeified)
loHead.treeify(tab);
}
}
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
}
关联面试题
1. HashMap实现原理
答案参考2. 实现原理
2. HashMap底层数据结构
- JDK8之前HashMap的实现是数组+链表，它之所以有相当快的查询速度，是因为对key计算hashCode来确定在一维数组中存储的位置，而增删速度靠的是链表保证。
- JDK8中用数组+链表+红黑树的结构来优化，链表长度大于8时同时满足HashMap中元素个数大于64（小于64Hash会扩容）时则变为红黑树，长度小于6变回链表。
3. 什么事Hash表
- 散列表（Hash Table，也叫哈希表），是根据关键码值（key value）而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度，这个映射函数叫做散列函数，存储记录的数组叫做散列表。
- hash表里可以存储元素的位置称为桶（bucket）。
4. 什么事Hash冲突，如何解决
- 不同的key产生相同的hash地址
- 解决方案：
- 开放地址法：探测序列，查找一个空的单元插入。线性探测，再平方，伪随机。
- 链地址法：对于相同的值，使用链表进行连接。使用数组存储每一个链表。HashMap中使用的方案。
- 公共溢出区法：建立一个特殊存储空间，专门存放冲突的树。此方法适用于数据和冲突较少的情况。
- 再散列法：准备若干个hash函数，如果使用第一个hash函数发生了冲突，就使用第二个hash函数依次类推。
5. 核心成员变量有哪些
答案参考3. 核心成员变量
6. 为什么8换成红黑树，6使用链表
- TreeNode（红黑树中）占用空间是普通Node（链表中）的两倍，为了时间和空间的权衡。
- 节点的分布频率会遵循泊松分布，链表长度达到8个元素的概率为0.00000006
- 若是7，则当极端情况下（频繁插入和删除的都是同一个哈希桶）对一个链表长度为8的哈希桶进行频繁的插入和删除，同样也会导致频繁的树化<=>非树化。
7. 插入和获取的过程
插入数据
- 首先判断table成员是否初始化，如果没有，则调用resize
- 通过传入键值对的key的hashCode和容量，马上得到该映射所在的table数组下标。并通过数组的取下标操作，得到该哈希桶的的头结点
- 如果没有发生哈希碰撞（头结点为null），那么直接执行新增操作。
- 如果发生了哈希碰撞（头结点不为null），那么分两种情况
- 如果桶内某个元素‘==’返回true，或者equals判断相同，执行替代操作。
- 如果桶内所有元素判断都不相等，执行新增操作，可能是链表也可能是红黑树的插入。
- 链表新增后会有两个判断：
- 如果哈希桶是单链表结构，且桶内的数量超过了TREEIFY_THRESHOLD(8)，且size大于等于了MIN_TREEIFY_CAPACITY(64)，那么将该哈希桶装换为红黑树结构。
- 如果新增后size大于了threshold，那么调用resize。
- 首先大于阈值threadshold会自动2倍扩容
- 扩容后hash位置会从新计算，这样是比较浪费资源的
- 插入数据采用头插法插入数据
获取数据
- 调用key的hashcode方法，根据返回值定位到map里数组对应的下标
- 判断这个数组下标对应的头节点是不是为null，如果是，返回null
- 如果头结点不为null，判断这个引用对象的key值得equals方法，跟查询的key值对比，判断是否为true，如果是则返回之歌对象的value值，否则继续遍历下一个节点。
- 如果遍历完map中的所有节点都无法满足上面的判断则返回null
【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）