数据结构之【 HashMap 】
HashMap是在开发过程中必用的存储结构,也是面试过程中经常问到的技能点。本章在这里介绍下HashMap在JDK8中的底层原理以及记录下常见的面试问题。
名称解释
-
Hash:
-
一般翻译为 散列,直译为 哈希
-
Hashing: 散列法
-
把任意长度的输入通过散列算法变换成固定长度的输出,该输出就是散列值。是一种典型的“空间换时间”的做法。
-
负载因子
-
比如我们存储70个元素,但我们可能为这70个元素申请了100个元素的空间。70/100=0.7,这个数字称为负载因子
-
哈希冲突(碰撞)
-
由于哈希算法被计算的数据是无限的,而计算后的结果范围有限,因此总会存在不同的数据经过计算后得到的值相同,这就是哈希冲突
- 解决方案:开放寻址法、拉链法。HashMap处理方案就是拉链法
数据结构存储图示
![Image [43].png](https://gateway.tinyice.cn/file/pic/141480096832782336.png)
源码说明(JDK1.8)
类声明
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {...}
类属性
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认的初始化容量 2^4=16
static final int MAXIMUM_CAPACITY = 1 << 30; // 最大容量 2^30=1073741824
static final float DEFAULT_LOAD_FACTOR = 0.75f; // 默认负载因子 0.75
static final int TREEIFY_THRESHOLD = 8; // 存储结构转链表结构转换为树状结构的阈值 =8
static final int UNTREEIFY_THRESHOLD = 6; // 存储结构由树状结构转换为链表结构的阈值=6
static final int MIN_TREEIFY_CAPACITY = 64; // 树状结构的最小容量=64
int threshold; // 阈值,当实际大小(容量*负载因子)大于该值时会进行扩容
final float loadFactor; // 负载因子
transient int size; // 存储元素总数
transient int modCount; // 被修改的次数(用于fast-fail机制)
初始化
// 使用指定初始容量以及负载因子来初始化,参数均可使用默认值
public HashMap(int initialCapacity, float loadFactor) {
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity); // 返回比输出值大的最近的2的整数次幂运算值,例如11的最近是16
}
// 使用Map数据来初始化
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
hash算法
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
-
散列值理论上是一个int型,如果直接拿散列值作为下标访问HashMap主数组的话,考虑到2进制32位带符号的int表值范围从-2147483648到2147483648。前后加起来大概40亿的映射空间。只要哈希函数映射得比较均匀松散,一般应用是很难出现碰撞的。
-
是一个Native方法,使用和当前线程相关的随机数和其他值最终通过Marsaglia's xorshift scheme随机算法产生一个随机数Object.hashCode()
-
hashCode无符号右移16位,即先将32位的int的低位舍弃,高位补0,然后再与hashCode进行(位)异或运算,使得高位不受影响,低位与高位进行运算(这部分为扰动,真正参与运算的还是低位)
Put
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true); // 先对key进行了一次Hash运算
}
链表节点属性
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
...
}
树状节点属性:是链表节点的子类
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
...
}
// LinkedHashMap.Entry与HashMap.Node是继承关系
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
具体细节
/**
* @param hash key的hash值
* @param key the key
* @param value the value to put
* @param onlyIfAbsent true时,表示不修改已存在的值
* @param evict false时,表示是在初始化HashMap
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// table数组为空,需要resize()
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 确定key要插入的数组位置的元素p,如果不存在则直接放入,(n - 1) & hash==hash%n ,前者效率更高
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 插入的位置元素已存在,则说明发生了hash碰撞(1.key是一样的,覆盖value,2,key不一样,存储在链表或者树中)
else {
Node<K,V> e; K k;
// 检查数组节点p是否和新插入的节点相等(比较key)
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 如果不相等
// 判断数组节点是否为树节点,如果是则按照树状节点规则插入
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 不是,则按照链表节点规则插入
else {
// 死循环,通过break来终止,这里为寻找下一个链表节点的过程
for (int binCount = 0; ; ++binCount) {
// 判断当前节点的下一个节点是null的,则占位,如果发现需要转为树结构,则转换,binCount统计链表长度,从0开始
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 下一个节点不是空,则判断是否和新节点相等(key比较),相等则该位置为要找的位置
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
// 下一个节点变为当前节点,继续循环
p = e;
}
}
// 要放入的位置确定后,判断位置上的元素是否存在,如果存在则判断是否替换
if (e != null) {
V oldValue = e.value;
// 满足替换条件才替换
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 判断是否需要扩容
if (++size > threshold)
resize();
// 插入后的后续处理,HashMap默认=false,不需要
afterNodeInsertion(evict);
return null;
}
比较Key的方法
p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))
-
hash值必须相等
-
且
-
比较key地址相等 或者 key!=null 时,比较key内容相等
get
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 从数组中获取对应位置元素不为null则继续查找
if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {
// 根节点就是要找的节点,则返回
if (first.hash == hash && ((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;
}
-
树状转换
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// 未达到树状结构的最少容量时(默认64),只扩容不转换
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
// 转换
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
数据结构验证
hash定位
public int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
数据准备
String[] arr1 = new String[]{"cg80", "lo8u", "pqdi", "bbam", "hhc5", "pnem", "u955", "p4z7"};
String[] arr2 = new String[]{"cg80", "lo8u", "pqdi", "bbam", "hhc5", "pnem", "u955", "p4z7", "phr0"};
String[] arr3 = new String[]{"cg80", "lo8u", "pqdi", "bbam", "hhc5", "pnem", "u955", "p4z7", "phr0", "suv8", "u4pu"};
String[] arr4 = new String[]{"cg80", "lo8u", "pqdi", "bbam", "hhc5", "pnem", "u955", "p4z7", "phr0", "suv8", "u4pu", "p63n"};
String[] arr5 = new String[]{"cg80", "lo8u", "pqdi", "bbam", "hhc5", "pnem", "u955", "p4z7", "phr0", "suv8", "u4pu", "p63n", "jaua", "zth9", "maxe"};
String[] arr6 = new String[]{"cg80", "lo8u", "pqdi", "bbam", "hhc5", "pnem", "u955", "p4z7", "phr0", "suv8", "u4pu", "p63n", "jaua", "zth9", "maxe", "wymp"};
arr1是8个字符串,arr2是9个字符串,arr1数据在size=16时,全部落到index=2处
arr2的数据在size=16同样会落在index=2处,此时因为链表长度>8结构转变,因为此时总容量=16小于树状结构最小容量64,因此只扩容1倍=32
arr2数据在size=32时,部分落到index=2处,部分落到index=18处
for (String key : arr2) {
System.out.println(String.format("%s\tsize=16,index=%s \t ", key, hash(key) % 16));
}
-------------------------------------------------------
cg80 size=16,index=2
lo8u size=16,index=2
pqdi size=16,index=2
bbam size=16,index=2
hhc5 size=16,index=2
pnem size=16,index=2
u955 size=16,index=2
p4z7 size=16,index=2
phr0 size=16,index=2
Map<String, Integer> map1 = new HashMap<>(16, 1);
for (String key : arr1) {
map1.put(key, 0);
}
Map<String, Integer> map2 = new HashMap<>(16, 1);
for (String key : arr2) {
map2.put(key, 0);
}
链表内存验证
arr3是arr2的链表满长度情况,index=18处的数据长度=8,,arr4则是arr3数据在index=18的数据长度=9时情况,此时再次触发扩容(szie=32<64不会转为树)
for (String key : arr4) {
System.out.println(String.format("%s\t size=32,index=%s \t", key, hash(key) % 32));
}
-------------------------------------------------------
cg80 size=32,index=18
lo8u size=32,index=18
pqdi size=32,index=18
bbam size=32,index=2
hhc5 size=32,index=2
pnem size=32,index=18
u955 size=32,index=18
p4z7 size=32,index=18
phr0 size=32,index=2
suv8 size=32,index=18
u4pu size=32,index=18
p63n size=32,index=18
Map<String, Integer> map3 = new HashMap<>(16, 1);
for (String key : arr3) {
map3.put(key, 0);
}
Map<String, Integer> map4 = new HashMap<>(16, 1);
for (String key : arr4) {
map4.put(key, 0);
}
arr5则是arr4的满员状态,此时index=50的数据长度=8,arr6则是arr5的数据在index=50的数据长度=9时情况,此时链表长度=8触发扩容,size=64.触发树状结构转换
for (String key : arr6) {
System.out.println(String.format("%s\t size=64,index=%s", key, hash(key) % 64));
}
-------------------------------------------------------
cg80 size=64,index=50
lo8u size=64,index=50
pqdi size=64,index=50
bbam size=64,index=2
hhc5 size=64,index=2
pnem size=64,index=18
u955 size=64,index=50
p4z7 size=64,index=50
phr0 size=64,index=2
suv8 size=64,index=18
u4pu size=64,index=18
p63n size=64,index=18
jaua size=64,index=50
zth9 size=64,index=50
maxe size=64,index=50
wymp size=64,index=50
Map<String, Integer> map5 = new HashMap<>(16, 1);
for (String key : arr5) {
map5.put(key, 0);
}
Map<String, Integer> map6 = new HashMap<>(16, 1);
for (String key : arr6) {
map6.put(key, 0);
}
树状数据转换,只针对index=50这个节点,红黑树图示
红黑树内存验证
常见问题
为什么使用HashMap
-
HashMap是非synchronized的键值对存储结构,速度快,效率高
-
HashMap支持键和值为null存储
-
HashMap不保证元素的顺序
HashMap中null的使用
- key可以为null,但只能有一个,index=0,后续会覆盖前者
- value可以为nul,数量不限制
查找效率
-
在数组中 O(1)
-
在链表中 O(N)
-
在树中 O(log N)
为什么采用红黑树而不是AVL树(平衡二叉树)?
-
区别
-
红黑树特点
-
每个结点要么是红的要么是黑的。
-
根结点是黑的。
-
每个叶结点(叶结点即指树尾端NIL指针或NULL结点)都是黑的。
-
如果一个结点是红的,那么它的两个儿子都是黑的。
-
对于任意结点而言,其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。
-
-
平衡二叉树特点
-
它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树
-
-
-
原因
-
二者在查找是都是通过二分法查找,效率差不多
-
插入与删除是红黑树效率较高,因为AVL树要求绝对的平衡,为保证绝对平衡,进行旋转的次数较多
-
存在问题
-
在自动调整大小时存在线程安全问题
-
在ForEach遍历时不能删除元素,正确方式为采用Iterator
为什么使用包装类作为键而不是基本类型
-
因为包装类重写了hashCode和equals方法,保证了键的不变性,在查询元素时能查找到正确的元素对象
使用对象作为键需要注意什么
-
注意保证键的不变性,即对象的hashCode和equals方法返回值是确定的
多线程时如何存储
-
使用HashTable或者ConcurrentHashMap
-
HashTable是HashMap的synchronized版本,不支持null的键或者值,底层是数组+链表,没有红黑树。ConcurrentHashMap是HashTable的改进版本
-
ConcurrentHashMap JDK7之前采用锁分离技术,默认将Hash表分为16段,对每段单独加锁,支持16个线程同时访问,支持读取并发,采用fail-fast迭代器,迭代中删除元素抛异常,JDK8之后使用synchronized+cas技术。原因在于分段锁浪费空间且实际中锁竞争情况出现很少。
-
HashTable是采用锁表技术,对每个操作都加锁保证安全,同一时刻只有一个线程能访问,效率低下,大部分情况可以使用ConcurrentHashMap替代,未采用fail-fast迭代器
扩容为什么是2的整数倍
-
保证Node的hash尽量的一致性
-
当n扩容后仍保持2^m时,Node落地点的下标
会更优化i=(n - 1) & hash
为什么负载因子0.75,链表转红黑树阈值=8,红黑树转链表=6
- 作为一般规则,默认的负载因子(0.75)提供了良好的性能权衡时间和空间成本。值越高,空间开销越小,但增加查找成本
- 阈值=8,是因为Hash下标的落地点遵循泊松分布,在负载因子=0.75前提下,忽略计算方差,λ=0.5时,阈值=8的概率为0.00000006,再高概率小于百万分之一,此时性能已经满足需求
- 阈值=6,是因为=8时链表转为树,再由树转链表这阈值一定小于8,所以=6
使用的是头插法还是尾插法
JDK7之前都是头插法,JDK8之后都是尾插法。因为JDK7中HashMap使用的是数组+链表的数据结构,使用头插法效率高,但是容易出现逆序和链表闭环的问题。JDK8中HashMap使用的是数组+链表+红黑树的数据结构,使用尾插法效率更高。