说在前面
HashMap提供了所有可选的map操作,key和values可以为null。HashMap和Hashtable类似,不同之处在于HashMap是非同步的,允许空值,一个HashMap实例有两个参数影响它的性能:初始容量和装载因子。 决定扩容时机;所有集合视图方法返回的迭代器都有fail-fast机制:如果map在iterator创建之后结构进行了改变(除了通过迭代器自身remove方法),则会抛出ConcurrentModificationException。
transient修饰符的作用是使该变量在序列化的时候不会被储存。但是hashmap中的变量table是储存了容器中所有的元素,在序列化中不被储存,那么反序列化后hashmap对象中岂不是个空容器?原因,table里存的只是引用,就算在序列化中储存到硬盘里,反序列化后table变量里的引用已经没有意义了。至于hashmap是如何在序列化中储存元素呢?原来是它通过重写Serializable接口中的writeObject方法和readObject方法实现的。https://blog.csdn.net/weixin_34346099/article/details/91940085
在new一个ArrayList对象时,默认是开辟一个长度为10的对象数组,如果只存入几个对象(不到默认的10个),如果采用默认序列化,则会将其余为null也序列化到文件中。
如果声明为transient类型,就能让虚拟机不会自行处理我们的这个数组,这才有了ArrayList的write/readObject方法。通过这种方式避免了浪费资源去存储没有的数据。
hashMap还依赖hashCode进行定位,hashCode每个JVM的实现可能不一样导致默认序列化后找不到数据
说说hashMap:从数据结构 初始化 -> put -> 树化 -> resize -> get -> remove退化为链表
1、hashmap的主要参数都有哪些?
transient Node<K, V>[] table:存储元素的数组,核心的数据结构,即所谓的数组+链表的部分。默认懒加载,默认初始容量capacity为16(也可以为8/4/2/1),最大的容量2^30,必须为2的次方
(n - 1) & hash 减一取余保证数组所有下标都存在有结果的可能性;
transient int size:存放元素的实际个数
transient int modCount:被修改的次数 fast-fail机制,在iterate迭代时用到。
int threshold:扩容阈值=capacityloadfactory,当实际大小size超过阈值时,会进行扩容 160.75=12 容量为16时,12时进行扩容
final float loadFactor:加载因子 默认为0.75(final成员变量表示常量,只能被赋值一次,赋值后值不再改变。可显式初始化或在构造器初始化)
transient Set<Map.Entry<K, V>> entrySet:transient Collection<V> values:持有一个缓存的键值对set 用来keySet() 和 values()方法快速返回,故keySet返回的不是一个新对象,而是在hashmap中存储的对象,增删改keySet返回的对象会影响hashMap,容易出问题。
static final int TREEIFY_THRESHOLD = 8:单个桶内数据为8个时转化为红黑树
static final int MIN_TREEIFY_CAPACITY = 64:树化的最小容量,如果单个桶链表长度达到了8个,容量未到64,则扩容
static final int UNTREEIFY_THRESHOLD = 6:默认红黑树退化为链表的阀值
2、Hashmap的数据结构是什么样子的?自己如何实现一个hashmap?
存储的数据结构为Node<K,V>数组,Node<K,V>是链表+红黑树结构(为解决hash碰撞)。数组的优点是通过数组下标查找O(1),链表的优势在于插入节点与删除节点以及解决hash碰撞,红黑树的优势在于优化查询速度,解决hash碰撞。Node<K, V> 继承自 Map.Entry<K, V>
/**
* 在这里可以看到,在Entry类中存在next,所以,它又是链表的形式,当table容量大于等于64时,单个桶内链表长度大于* 8时转化为红黑树,这就是hashmap的主要数据结构。
*/
static class Node<K, V> implements Map.Entry<K, V> {
final int hash;
final K key;
V value;
Node<K, V> next;
}
3、hash计算规则是什么?
/**
* 扰动函数:目的是让散列分布地更加均匀
* K为null时固定存储在 0 索引处
* key的hash值低16位不变,低16位与高16位异或作为key的最终hash值。
* (h >>> 16,表示无符号右移16位,高位补0,任何数跟0异或都是其本身,因此key的hash值高16位不变。)
* 这样的作用 下标计算方式 index = (n-1) & hash; 将key的hash值高16位加入hash,提高数据离散性,减少
* hash碰撞,
* 将原本低16位(可能是低4位,比如容量是16时 1111 & hash )相同的数据,可能通过低16位与高16异或,使数据不
* 再碰撞
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
盗图: key在table中的位置:tab[i = (n - 1) & hash]
,n是容量,与运算求得位置实际和取余一致。因为n保证是2的次幂,n-1保证是1111…,与运算的范围在 0~1111...之间。这种类型的运算,能够更加的节约计算机资源。
4、说说hashmap的存取过程?
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* 实际put的方法
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K, V>[] tab;
Node<K, V> p;
int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
//为空时扩容,所以hashMap是懒加载的,存数据时初始化数租
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
//hash桶位置没有数据,直接插入
tab[i] = newNode(hash, key, value, null);
else {
Node<K, V> e;
K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//已经存在相同的key 覆盖
e = p;
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) {
//新增数据
//遍历所有已有数据 发现没有相同的key 则进行尾插法
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1)
//链表数据长度 >= 8 , 方法内部校验容量是否大于64,大于64才树化,否则扩容
treeifyBin(tab, hash);
break;
}
//已经存在相同的key 覆盖
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//校验结果key不相同时,进行下个数据的比较
p = e;
}
}
if (e != null) {
//这个key已经存在 覆盖,将新值存储,返回旧值
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
//修改次数加一,控制并发 iterate遍历时会前后校验该值,在遍历过程中该值变化,则抛出异常 fail-fast机制
++modCount;
//数据元素个数加一,大于扩容阀值(容量 * 加载因子)时扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
//1.8新增的一些方法
/**
* putIfAbsent方法,只有在key不存在或者key为null的时候,value值才会被覆盖
*
* if (!onlyIfAbsent || oldValue == null) e.value = value;
* putIfAbsent()调用了putVal(),第四个参数onlyIfAbsent传true,表示只有无此key时才put。如putIfAbsent()的key不存在,和put()逻辑相同。如果已存在,onlyIfAbsent延迟到putVal()的 if (e != null)时才做判断。
*/
public V putIfAbsent(K key, V value) {
return putVal(hash(key), key, value, true, true);
}
/**
* key存在时,val和旧value的操作后的新值,不存在直接放入val
*
* map.merge(k, val, (oldVal, newVal) -> oldVal + newVal);
* 如果key存在,则执行lambda表达式,放入操作后的值,表达式返回最终put的val。
* 如果key不存在,则直接put newVal
*/
public V merge(K key, V value,
BiFunction<? super V, ? super V, ? extends V> remappingFunction) ...
/**
*
* map.compute(k, (key, oldVal) -> oldVal + key); == put(key,oldVal + key)
* 如果key存在,根据已知的(k,v)算出新的v并put。
* 如果key不存在,那么oldVal为null,lambda中涉及到oldVal的计算会报空指针,这点需要注意,并自行处理。
* 这个方法只有在key需要参与value的运算时使用才有意义
*/
public V compute(K key,
BiFunction<? super K, ? super V, ? extends V> remappingFunction) ...
/**
* 当key不存在时才执行操作
* compute()有空指针的风险。所以用computeIfAbsent()来规避
*/
public V computeIfAbsent(K key,
Function<? super K, ? extends V> mappingFunction) ...
/**
* 当key存在的时才执行操作
* compute()的补充。其他和compute()相同
*/
public V computeIfPresent(K key,
BiFunction<? super K, ? super V, ? extends V> remappingFunction) ...
public V get(Object key) {
Node<K, V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
* 实际get的方法
*/
final Node<K, V> getNode(int hash, Object key) {
Node<K, V>[] tab;
Node<K, V> first, e;
int n;
K k;
//校验数据不为空,且key的hash桶位有值
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))))
//如果第一个节点的key相等 则返回
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;
}
4.计算扩容时的容量方法
/**
* 设置 容量
* 返回大于输入参数且最近的2的整数次幂的数
* n = 01xxx...xxx
* 对n右移1位:001xx...xxx,再位或:011xx...xxx
* n = 011xx...xxx
* 对n右移2为:00011...xxx,再位或:01111...xxx
* n = 01111...xxx
* n = 01111...xxx | 000001111
* n = 011111111
* 此时前面已经有四个1了,再右移4位且位或可得8个1
* n = 011111111 | 000000000
* 同理,有8个1,右移8位肯定会让后八位也为1。
* n = 011111111
* 综上可得,该算法让最高位的1后面的位全变为1。
* <p>
* 最后再让结果n+1,即得到了2的整数次幂的值了。
*/
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;
}
5、说说hashmap如何处理碰撞的,或者说说它的扩容?
先说说hash碰撞吧,由于hashmap在存值的时候并不是直接使用key的hashcode,而是通过扰动函数算出了一个新的hash值,这个计算出的hash值可以减少一定的碰撞。还有一种解决碰撞的方式就是扩容,扩容其实很好理解,就是将原来桶的容量扩为原来的两倍,这样争取散列的更均匀,扩容会将桶A中的数据分散在桶A或桶A+oldCapacity中。
扩容时机:
1)size>threshold 扩容
2)单个桶中数据达到8个,容量不到64,扩容
如何扩容:左移一位
扩容消耗:new一个新数组,旧数组数据循环放入新数组并且需要重新计算这些数据在新table数组中的位置
/**
* 扩容 左移一位
*/
final Node<K, V>[] resize() {
Node<K, V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
} else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 左移一位 扩容为原来的2倍
newThr = oldThr << 1;
} else if (oldThr > 0)
// 使用有参构造器时,构造器中将容量放在threshold记录 ,初始化走这
newCap = oldThr;
else {
//无参构造器走这
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
//设置 临界值
float ft = (float) newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ?
(int) ft : Integer.MAX_VALUE);
}
//设置 新的临界值 newCap * loadFactor
threshold = newThr;
//Node数组创建一个新的 旧数组中的数据复制进新数组
Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K, V> e;
if ((e = oldTab[j]) != null) {//该hash桶中有数据处理逻辑
oldTab[j] = null;
if (e.next == null)
//桶的位置只有一个数据 复制进新数组
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
//桶的位置是一个红黑树,进行红黑树的拆分,
//拆分原则:红黑树中的数据要么还在该桶中,要么在该索引+旧容量的位置 红黑树长度小于等于6时 树结构退化为链表
((TreeNode<K, V>) e).split(this, newTab, j, oldCap);
else {
//桶的位置是链表结构
//lo低位 原下标位置 j
Node<K, V> loHead = null, loTail = null;
//hi高位 高下标位置 j + oldCap
Node<K, V> hiHead = null, hiTail = null;
Node<K, V> next;
//遍历链表
do {
next = e.next;
//校验数据在低位还是高位
//校验逻辑 e.hash & oldCap ,相当于校验新加的位 & e.hash 是否为0
//例子 :hash = xxxx ... 1010 1100
// oldCap 64 = 1 0000;
// newCap 128 = 10 0000;
// j = (oldCap - 1)&hash = 1111 & (.. 1010 1100 ) = 1100;
// 1010 1100 & 1 0000 = 0 相当于在低位
// 结合hash定位桶下标的位置 (newCap - 1)&hash = 1100
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;
}
总结
HashMap是基于hashing的原理,我们使用put(key, value)存储对象到HashMap中,使用get(key)从HashMap中获取对象。HashMap采用的是数组+链表+红黑树的数据结构,数组的优势在于根据下标查询效率为O(1),链表的优势在于插入和删除节点比较快,但是重点在于解决hash碰撞,红黑树的优势在于hash碰撞数据过多时,更好的优化查询效率。当我们初始化HashMap时,HashMap采用懒加载,put时默认初始化容量为16,当我们给put()方法传递键值时,我们先对键调用hashCode()扰动方法,防止使用者的hash算法太烂,同时让数据的高16位参与进下标的运算,更好的减少碰撞,返回的hashCode和n-1进行与操作,用于找到bucket位置来储存Entry对象,这里的n是hashMap里数组的长度,之所以用n-1是因为让所有hash槽位置都可以有数据,因为n-1的二进制位都是1。现在我们找到数据的槽位,如果该槽位有数据且不超过8个,则进行链表的转换,放在尾部,1.7是放在头部,1.8对此进行优化,避免并发时出现死循环,但是HashMap不适用于并发场景,如果该槽位数据超过8个,且HashMap内部存储数据的数组长度大于等于64时将该槽位的数据转换为红黑树进行存储,数组长度不足64则进行扩容,还有如果原本就是红黑树,则当该槽位数据小于等于6时将红黑树转换为链表。当实际存储的数据超过阀值时进行扩容,这个阀值是数组长度乘以加载因子,默认加载因子是0.75,其实扩容还有一种触发时机就是当单槽位数据超过8个但是数组长度不到64时进行扩容。扩容时新容量为旧容量左移一位,然后复制一个新数组,将旧数组的数据计算下标位置放入新数组,这里计算新下标位置的情况有两种,一种是原槽位,一种是原槽位+旧数组长度的槽位,原因是因为扩容时为旧容量左移一位,左移一位后就只判断数据的hashCode和新增的那一位相与后是否为1,为1的话就在原槽位+旧数组长度的位置,为0的话就是原槽位。还有get数据,需要key的hashCode和equals都相等才返回该数据,这里就要求HashMap的key对象必须重写hashCode和equals方法。如果只重写equals不重写hashCode则hashCode是该对象的地址值,会导致数据相同查不到,数据相同可以存储多份,这样hashMap的意义就没有了;只重写hashCode不重写equals方法则会导致地址值相同的数据才视为相同,会导致数据相同查不到,数据相同可以存储多份。
因为扩容会有数组复制操作,较影响性能,所以如果知道存储数据的长度,最好初始化时给定长度,而且由于hash碰撞,用时重写hashCode时尽可能让较多字段参与进运算。
有错误请指正,在此谢过各位大佬。
彩蛋
modCount用处
/**
* Iterator ==> 解释modcount
* <>注意⚠️ : 下面的HashIterator 不是HashMap内部的方法,把这个类移到这是为了解释 modCount 的作用</>
* <p>
* 在ArrayList,LinkedList,HashMap等等的内部实现增,删,改中我们总能看到modCount的身影,modCount字面意思就是修改次数,但为什么要记录modCount的修改次数呢?
* 大家发现一个公共特点没有,所有使用modCount属性的全是线程不安全的,这是为什么呢?说明这个玩意肯定和线程安全有关系喽,那有什么关系呢
* <p>
* 阅读源码,发现这玩意只有在本数据结构对应迭代器中才使用,以HashMap为例:
*/
private abstract class HashIterator<E> implements Iterator<E> {
/**将要返回的下一个Entry*/
Entry<K, V> next;
/**For fast-fail 机制*/
int expectedModCount;
/**当前 桶位置*/
int index;
/** 当前 Entry*/
Entry<K, V> current;
HashIterator() {
/**
* 迭代器迭代之前 记录 modCount 数值 可以理解成HashMap的版本号,每修改一次加一,
* 记录迭代器遍历之前的版本号 modCount 数值
*/
expectedModCount = modCount;
Node<K,V>[] t = table;
current = next = null;
index = 0;
if (t != null && size > 0) {
//赋值next 递增数组下标 找到第一个有数据的桶下标 以及该数据
do {} while (index < t.length && (next = t[index++]) == null);
}
}
public final boolean hasNext() { return next != null; }
final Node<K,V> nextNode() {
Node<K,V>[] t;
Node<K,V> e = next;
//迭代器遍历之前HashMap的版本号和现在的版本号不同
//modCount当前值和遍历之前的值不同时,抛出并发修改异常
if (modCount != expectedModCount) throw new ConcurrentModificationException();
if (e == null) throw new NoSuchElementException();
if ((next = (current = e).next) == null && (t = table) != null) {
//赋值next 递增数组下标 找到下一个有数据的桶下标 以及该数据
do {} while (index < t.length && (next = t[index++]) == null);
}
return e;
}
public final void remove() {
Node<K,V> p = current;
if (p == null) throw new IllegalStateException();
//迭代器遍历之前HashMap的版本号和现在的版本号不同
//modCount当前值和遍历之前的值不同时,抛出并发修改异常
if (modCount != expectedModCount) throw new ConcurrentModificationException();
current = null;
K key = p.key;
removeNode(hash(key), key, null, false, false);
//自己迭代器修改,修改版本号
expectedModCount = modCount;
}
}
部分面试题
1.HashMap的痛点在哪儿?hash碰撞,扩容耗性能,不支持并发。
2.HashMap中hash函数怎么实现的?
1)高16bit与低16位做异或运算得到hash值,让hashCode的高16位和低16位都参与运算。
2)(n-1)&hash函数 -->得到下标
3.解决哈希冲突有如下的方法:
A. 开放地址法:当前位置冲突了,那我就去找相邻的下一个位置,H=(H(kyt)+d) MOD m ,m为哈希表表长。
(1)d=1,2,3------> m-1 时,称谓线性探测再散列
(2)d=12,-12---->+(-)k^2时,称为二次线性再散列。
(3)d为伪随即序列时,称为伪随即序列再散列。
B .再哈希法 在地址冲突时计算另一个哈希函数地址,直到不再发生冲突。
C .链地址法:将所有哈希地址冲突的记录存储在同一个线性链表中
D 公共溢出区法:将所有哈希地址冲突的记录都填入到溢出表中
4.hashMap线程安全问题
1)在多线程同时操作hashMap的时候,put方法没有设置同步方法,所以不是线程安全的,HashMap在并发执行put操作1.7是会引发死循环的,因为多线程会导致HashMap的Entry链表形成环,一旦成环,Entry的Next节点永远不能为空,产生死循环
2)多线程下HashMap中的字段size存储的实际数量可能造成不准确。
3)读写不一致等情况,而且HashMap不应用于并发情况。
4)HashTable是线程安全的,但是在并发情况下效率低下,原因是所有访问hashTable的线程都必须竞争同一把锁,jdk提供了ConcurrentHashMap:线程安全且高效的HashMap,使用的是CAS+分段锁。
5.为什么String, Interger这样的wrapper类适合作为键?
String, Interger这样的wrapper类是final类型的,具有不可变性,而且已经重写了equals()和hashCode()方法了。其他的wrapper类也有这个特点。不可变性是必要的,因为为了要计算hashCode(),就要防止键值改变,如果键值在放入时和获取时返回不同的hashcode的话,那么就不能从HashMap中找到你想要的对象。
6.HashMap 的遍历方式及其性能对比?
/**主要三种方式:*/
//for-each map.keySet() -- 只需要K值的时候,推荐使用
for (String key : map.keySet()) {
map.get(key);
}
//for-each map.entrySet() -- 当需要V值的时候,推荐使用
for (Map.Entry<String, String> entry : map.entrySet()) {
entry.getKey();
entry.getValue();
}
//for-each map.entrySet().iterator()
Iterator<Map.Entry<String, String>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
Map.Entry<String, String> entry = iterator.next();
entry.getKey();
entry.getValue();
}
其他面试题通过源码解答