JavaSE-Map接口,HashMap底层实现
1. Map接口框架(常用)
文章图片
|----Map:双列数据,存储key-value对的数据 —类似于高中的函数:y = f(x)
|----HashMap:作为Map的主要实现类;线程不安全的,效率高;存储null的key和value
|----LinkedHashMap:保证在遍历map元素时,可以按照添加的顺序实现遍历。
原因:在原有的HashMap底层结构基础上,添加了一对指针,指向前一个和后一个元素。
对于频繁的遍历操作,此类执行效率高于HashMap。
|----TreeMap:保证按照添加的key-value对进行排序,实现排序遍历。此时考虑key的自然排序或定制排序
底层使用红黑树
|----Hashtable:作为古老的实现类,jdk1.0;线程安全的,效率低;不能存储null的key和value
|----Properties:常用来处理配置文件。key和value都是String类型
面试题:
- HashMap的底层实现原理?
- HashMap 和 Hashtable的异同?
- CurrentHashMap 与 Hashtable的异同?
- Map结构理解
Map中的key:无序的、不可重复的,使用Set存储所有的key —> key所在的类要重写equals()和hashCode() (以HashMap为例)
Map中的value:无序的、可重复的,使用Collection存储所有的value —>value所在的类要重写equals()
一个键值对:key-value构成了一个Entry对象。
Map中的entry:无序的、不可重复的,使用Set存储所有的entry
【JavaSE-Map接口,HashMap底层实现】HashMap map = new HashMap():
在实例化以后,底层创建了长度是16的一维数组Entry[] table。
2.2 JDK8中
table:节点的数组
hashMap是基于哈希表对Map接口的实现,HashMap具有较快的访问速度,但存储是无序的
loadFactor:负载因子,默认0.75
threshold:所能容纳键值对的阈值=初始容量(DEFAULT_INITIAL_CAPACITY = 1 << 4) * 负载因子
size:hashMap中实际存在的键值对数量
modCount:HashMap内部结构发生变化的次数
TREEIFY_THRESHOLD:Bucket中链表长度大于该默认值,转化为红黑树:8
MIN_TREEIFY_CAPACITY:桶中的Node被树化时最小的hash表容量:64
- 采用 数组+链表+红黑树 的存储结构
- 内部类Node实现Map.Entry接口, 存储着 hash、key、value、next指针
当数组的某一个索引位置上的元素以链表形式存在的数据个数 > 8 且当前数组的长度 > 64时,此时此索引位置上的所数据改为使用红黑树存储; 链表时间复杂度O(n),红黑树时间复杂度O(log n) - hashMap中存入元素 put(k,v)
- 确定Node的存储位置:(key.hashCode() 与 key.hashCode()的高16位做异或运算)& table.length-1
- 如果此位置上的数据为空,此时的k-v添加成功。
如果此位置上的数据不为空,(意味着此位置上存在一个或多个数据(以链表形式存在)),比较k和已经存在的一个或多个数据的哈希值:
如果key1的哈希值与已经存在的数据的哈希值都不相同,此时key1-value1添加成功
如果key1的哈希值和已经存在的某一个数据(key2-value2)的哈希值相同,继续比较:调用key1所在类的equals(key2)方法,比较:
如果equals()返回false:此时key1-value1添加成功。
如果equals()返回true:使用value1替换value2
- 扩容resize():当键值对数量超出阈值时,扩容。默认的扩容方式:扩容为原来容量的2倍,并将原有的数据复制过来
- jdk8与jdk7的不同:
- new HashMap():底层没有创建一个长度为16的数组
- jdk 8底层的数组是:Node[],而非Entry[]
- 首次调用put()方法时,底层创建长度为16的数组
- jdk7底层结构只有:数组+链表。jdk8中底层结构:数组+链表+红黑树。
4.1 形成链表时,七上八下(jdk7:新的元素指向旧的元素。jdk8:旧的元素指向新的元素)
4.2 当数组的某一个索引位置上的元素以链表形式存在的数据个数 > 8 且当前数组的长度 > 64时,此时此索引位置上的所数据改为使用红黑树存储。 - jdk7在扩容resize()时,采用头插法;jdk8在扩容时采用尾插法
jdk7源码:
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}Entry[] newTable = new Entry[newCapacity];
boolean oldAltHashing = useAltHashing;
useAltHashing |= sun.misc.VM.isBooted() &&
(newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
boolean rehash = oldAltHashing ^ useAltHashing;
transfer(newTable, rehash);
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}/**
* Transfers all entries from current table to newTable.
*/
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry e : table) {
while(null != e) {
Entry next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
jdk7在扩容resize()时,采用头插法,在transfer()方法中,即扩容之后的数据迁移部分
在并发情况下:
线程1:扩容后rehash之后新数组中的Entry链表被反转
Q:HashMap容量为什么是2的幂?
A:在确定元素落在数组的位置的时候,计算方法是(n - 1) & hash,当n为2的幂时,(n - 1) & hash = hash % n,这样就可以用(n - 1) & hash的位运算来使计算更加高效
推荐阅读
- JAVA(抽象类与接口的区别&重载与重写&内存泄漏)
- 基于微信小程序带后端ssm接口小区物业管理平台设计
- 2020-04-07vue中Axios的封装和API接口的管理
- 调取接口时报404错误(ID:16)
- CICC(脑机接口,科幻几近成真())
- 接口|axios接口报错-参数类型错误解决
- 190403|190403 - Jmeter压测接口
- JavaScript|vue 基于axios封装request接口请求——request.js文件
- 微信小程序请求接口格式
- HashMap&ConcurrentHashMap&HashTable