目录
(一)Map接口
(1)Map接口是什么
Map是一种专门用来进行搜索的容器或者数据结构,其搜索的效率与其具体的实例化子类有关,如TreeMap和HashMap
下图为Map接口与HashMap与TreeMap关系
(2)Map接口的特性
(3)Map接口中的方法
(二)HashMap
(1)HashMap与Map接口的关系
HashMap继承了Map接口,并重写了Map接口中的方法
下图中为HashMap的继承关系
(2)HashMap的底层结构
2.1哈希表
HashMap的底层结构是哈希表(散列表,哈希桶),哈希表通常采用“数组+链表+红黑树”的结构来实现。具体来说,哈希表是一个数组,数组的每个元素都是一个指针,指向一个链表的头节点。这个链表用于存储所有哈希码(哈希值)相同的键值对。
哈希表大概是如图所示结构
一般HashMap的初始容量和扩容都是2的次幂,这样可以有效减少hash冲突,具体原因与HashMap中的hash()算法有关。
下图计算出 h 之后再与数组长度-1进行与运算,计算出储存下标的位置。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);//>>>16后相异或也是为了减少hash冲突
}
2.2哈希函数,关键字,Hash码
给定一个函数H(key),对一个给定的x,带入函数后得到的值为y,
那么这个函数是哈希函数,这个x是关键字,y是哈希码
例:将哈希函数设置为hash(key) = key %10,那么这个函数叫做哈希函数,key叫做关键字,hash(key)叫做哈希码 。
2.3向hash表插入/搜索
(3)冲突
3.1冲突概念
例:两个关键字 2 和 12他们两个是不相等的,但通过哈希函数hash(key) = key%10 ,计算出的哈希码是相同的,这种现象成为哈希冲突。
3.2冲突避免
3.2.1设计合理的哈希函数
常见的哈希函数设计有: 直接定制法,除留余数法,折叠法,数学分析法等.....
3.2.2负载因子
负载因子概念: 负载因子是散列表装满程度的标志因子,由于表是定长,负载因子随着填入表中元素的个数成正比,填入的越多,负载因子越高
负载因子计算:负载因子 = 填入表中元素的个数 / 哈希表的长度。
负载因子与冲突率关系图
可见冲突率随负载因子的升高而升高,所以当冲突率达到一个无法忍受的程度时,我们需要通过降低负载因子来变相的降低冲突率,已知哈希表中已有的关键字个数是不可变的,那我们能调整的就只有哈希表中的数组的大小。
3.2.3HashMap中的扩容机制
在Java的HashMap中,默认情况下,HashMap的负载因子为0.75f。这意味着,当HashMap中的元素数量达到容量(初始容量或扩容后的容量)的75%时,HashMap会进行扩容操作。
下面是HashMap的扩容机制部分源码,我在其中加入了详细的注释,需要注意的是,新的数组容量不是原来旧数组容量的2倍,而是旧的扩容阈值的2倍,扩容是根据扩容阈值扩容的
比如负载因子是0.75,如果旧数组大小是16,那么旧扩容阈值是16*0.75 = 12,那么触发扩容操作时新的数组容量为12*2 = 24而不是16*2 = 32。
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;//当前HashMap的table数组
int oldCap = (oldTab == null) ? 0 : oldTab.length;//当前数组的长度
int oldThr = threshold;//扩容阈值,当数组中的数超过这个值会发生扩容
int newCap, newThr = 0;//新的数组容量和扩容阈值
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {//如果旧数组大于数组最大容量1>>30(2的30次方)
threshold = Integer.MAX_VALUE;
return oldTab;//返回旧的数组
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)//确保新的容量没有超过HashMap允许的最大容量并且旧的容量大于等于默认初始容量
newThr = oldThr << 1; //将新阈值设置为旧阈值二倍
}
else if (oldThr > 0) //如果旧阈值大于0
newCap = oldThr;//将旧阈值赋值给新的数组容量(注意这是已经扩大过2倍的旧阈值)
else { // zero initial threshold signifies using defaults
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);
}
3.3冲突解决
如果发生了冲突之后,我们怎么解决冲突呢,冲突解决有两大方法,闭散列和开散列。
(1)闭散列:
也叫开放定址法,当发生哈希冲突时,如果哈希表未被装满,说明在哈希表中必然还有空位置,那么可以把key存放到冲突位置中的“下一个” 空位置中去。那么如何寻找下一个空位置。
(2)开散列
1.树化
原因:如果链化阈值也设置为8,那么在元素数量在7和8之间波动时,链表和红黑树之间会发生频繁的转换,这不仅会浪费CPU资源,还会影响性能。
(三)总结
这篇文章讲到了
1.Map接口的特性
2.Map接口的方法
3.哈希表,哈希函数,关键字,哈希码
4.冲突的概念,冲突的避免(设计哈希函数,调整负载因子,适时扩容),冲突的解决(闭散列,开散列)