HashMap的使用与底层结构剖析
标签: HashMap的使用与底层结构剖析 JavaScript博客 51CTO博客
2023-04-05 18:23:49 223浏览
目录
一、基础概念
二、先使用再了解
三、底层结构
1.HashMap结构(JDK1.8以前)
2.HashMap结构(JDK1.8以后)
四、HashMap实现
1.成员变量
2.put实现
3.get实现
4.remove实现
5.resize与rehash实现
五、源码
1.类属性与继承关系
2.构造函数
3.hash算法
4.HashMap 的容量
一、基础概念
首先说明几个概念:
- Colllection
Colllection接口为基本的接口,存储对象有List、Set、Quene。List为有序的允许重复的Collection,Set为无序不允许重复的Collection。
哈希表
哈希表也称散列表,根据关键码值key 进行访问的数据结构,也就是说,能够将关键码
映射到表中一个位置我们就可以去访问其记录value,加快查找的速度,这个映射函数
叫做散列函数,存放记录的数组叫做散列表
数组:寻址容易O(1),插入和删除困难O(N)
链表:寻址困难O(N),插入和删除容易O(1)
综合两者的特性,变成了一个寻址容易,插入删除也容易的数据结构
哈希表有多种不同的结构(实现),我们介绍的是最常用的结构-拉链法(链地址法)
- Map接口
Map,图,是一种存储键值对映射的容器,在Map中键可以是任意类型的对象,但是键 不允许重复的。
每一个键对应有一个值如 name(Tom)-age(13)
HashMap基于哈希表的Map接口的非同步实现,继承自AbstractMap,AbstractMap 是部分实现Map接口的抽象类。
jdk1.8之前 数组+链表
jdk1.8 数组+链表+红黑树
- Iterator
terator迭代器是每个集合都有的一个对象。
Java中的Iterator功能比较简单,并且只能单向移动:
(1) 使用方法iterator()要求容器返回一个Iterator。第一次调用Iterator的next()方法时,它返回序列的第一个元素。注意:iterator()方法是java.lang.Iterable接口,被Collection继承。
(2) 使用next()获得序列中的下一个元素。
(3) 使用hasNext()检查序列中是否还有元素。
(4) 使用remove()将迭代器新返回的元素删除。
Iterator是Java迭代器最简单的实现,为List设计的ListIterator具有更多的功能,它可以从两个方向遍历List,也可以从List中插入和删除元素。
二、先使用再了解
定义一个Map对象,测试如何初始化及下列各种方法的使用:
HashMap方法
方法 |
描述 |
删除 hashMap 中的所有键/值对 |
|
复制一份 hashMap |
|
判断 hashMap 是否为空 |
|
计算 hashMap 中键/值对的数量 |
|
将键/值对添加到 hashMap 中 |
|
将所有键/值对添加到 hashMap 中 |
|
如果 hashMap 中不存在指定的键,则将指定的键/值对插入到 hashMap 中。 |
|
删除 hashMap 中指定键 key 的映射关系 |
|
检查 hashMap 中是否存在指定的 key 对应的映射关系。 |
|
检查 hashMap 中是否存在指定的 value 对应的映射关系。 |
|
替换 hashMap 中是指定的 key 对应的 value。 |
|
将 hashMap 中的所有映射关系替换成给定的函数所执行的结果。 |
|
获取指定 key 对应对 value |
|
获取指定 key 对应对 value,如果找不到 key ,则返回设置的默认值 |
|
对 hashMap 中的每个映射执行指定的操作。 |
|
返回 hashMap 中所有映射项的集合集合视图。 |
|
keySet() |
返回 hashMap 中所有 key 组成的集合视图。 |
返回 hashMap 中存在的所有 value 值。 |
|
添加键值对到 hashMap 中 |
|
对 hashMap 中指定 key 的值进行重新计算 |
|
对 hashMap 中指定 key 的值进行重新计算,如果不存在这个 key,则添加到 hasMap 中 |
|
对 hashMap 中指定 key 的值进行重新计算,前提是该 key 存在于 hashMap 中。 |
package sefl.HashMap;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
public class test {
public static void main(String[] args) {
//1.声明HashMap对象
Map<String, Integer> map = new HashMap<>();
//2.添加数据 put
map.put("zhangsan", 90);
map.put("wangwu", 79);
map.put("lisi", 80);
//3.根据键获取值 get
System.out.println("根据键获取值:"+map.get("zhangsan"));
//4.获取Map中键值对的个数
System.out.println("map当中键值对的个数:"+map.size());
//5.判断Map集合是否包含键为key的键值对
System.out.println(map.containsKey("tom"));
System.out.println(map.containsKey("zhangsan"));
//6.判断Map集合是否包含值为value的键值对
System.out.println(map.containsValue(90));
System.out.println(map.containsValue(100));
//7、根据键删除Map中的健值对 remove
System.out.println(map.remove("zhangsan"));
System.out.println(map.remove("tom"));
//8、 返回Map集合中所有key组成的Set集合
System.out.println(map.keySet());
//9、返回Map集合中所有value组成的以Collection数据类型格式数据
System.out.println(map.values());
//10、获取HashMap中的所有键值对
Iterator<Map.Entry<String, Integer>> iterator = map.entrySet().iterator();
while(iterator.hasNext()){
Map.Entry<String, Integer> next = iterator.next();
System.out.println(next.getKey()+":: "+next.getValue());
}
//11、清空并输出打印
map.clear();
while(iterator.hasNext()){
Map.Entry<String, Integer> next = iterator.next();
System.out.println(next.getKey()+":: "+next.getValue());
}
}
}
测试结果:
三、底层结构
1.HashMap结构(JDK1.8以前)
如下图所示,在1.8版本之前,哈希表的结构是由数组+链表实现的,通常使用链地址法去解决哈希冲突,元素较少时,时间复杂度为O(1),但元素增多后,元素存于链表中,在链表上进行操作,时间复杂度为O(N)。
2.HashMap结构(JDK1.8以后)
在1.8版本以后,结构变为了数组+链表+红黑树。
红黑树的概念:
红黑树是一种自平衡二叉查找树 它在O(log2 N)的时间内做查找、添加、删除 红黑树和AVL树是二叉查找树的变体,红黑树的性能要好于AVL树
红黑树特点:
1) 每个节点是红色或黑色
2)根节点一定是黑色
3)每个叶子节点是黑色
4)如果一个节点是红色,则叶子节点必须是黑色
5)每个节点到叶子节点所经过的黑节点的个数必须是一样
四、HashMap实现
仿照源码,实现HashMap的结构以及一些重要函数如put,get,remove等。
1.成员变量
主要有三个参数,key,value,与散列值hash。
private int size; //表示map中有多少个键值对
private Node<K, V>[] table;
class Node<K, V> {
private K key;
private V value;
private Node<K, V> next;
private int hash;
public Node(int hash, K key, V value) {
this.hash = hash;
this.key = key;
this.value = value;
}
}
2.put实现
put方法主要用于将键值对放入哈希表中,其实现流程为:
- 1)key-> hash(key) 散列码 -> hash & table.length-1 index
- 2)table[index] == null 是否存在节点
- 3)不存在 直接将key-value键值对封装成为一个Node 直接放到index位置
- 4)存在 key不允许重复
- 5)存在 key重复 考虑新值去覆盖旧值
- 6)存在 key不重复 尾插法 将key-value键值对封装成为一个Node 插入新节点
public void put(K key, V value){
//key->Hash值->index
int hash = hash(key);//散列码
//table.length-1 & h->index确定插入位置
int index = table.length-1 & hash;
//当前index位置不存在节点
Node<K, V> firstNode = table[index];
if(firstNode == null){
//table[index]位置不存在节点 直接插入
table[index] = new Node(hash, key, value);
size++;
}
//key不允许有重复的
//查找当前链表中key是否已经存在
//当前位置存在节点 判断key是否重复
if(firstNode.key.equals(key)){
firstNode.value = value;
}else{
//遍历当前链表
Node<K, V> tmp = firstNode;
while(tmp.next != null && !tmp.key.equals(key)){
tmp = tmp.next;
}
if(tmp.next == null){
//表示最后一个节点之前的所有节点都不包含key
if(tmp.key.equals(key)){
//最后一个节点的key与当前所要插入的key是否相等,考虑新值覆盖旧值
tmp.value = value;
}else{
//如果不存在,new Node,尾插法插入链表当中
tmp.next = new Node(hash, key, value);
size++;
}
}else{
//如果存在,考虑新值覆盖旧值
tmp.value = value;
}
}
}
3.get实现
get方法返回指定键所映射的值,没有该key对应的值则返回null,其实现流程如下:
1)通过key获取到位置index
2)在index位置的所有节点中找与当前key相等的key,不存在返回null,存在返回对应value
public V get(K key){
//获取key所对应的value
//key->index
int hash = hash(key);
int index = table.length-1 & hash;
//在index位置的所有节点中找与当前key相等的key
Node<K,V> firstNode = table[index];
//当前位置点是否存在节点 不存在
if(firstNode == null){
return null;
}
//判断第一个节点
if(firstNode.key.equals(key)){
return firstNode.value;
}else{
//遍历当前位置点的链表进行判断
Node<K,V> tmp = firstNode.next;
while(tmp != null && !tmp.key.equals(key)){
tmp = tmp.next;
}
if(tmp == null){
return null;
}else{
return tmp.value;
}
}
}
4.remove实现
remove方法用于删除Map集合中键为key的数据并返回其所对应value值,实现流程:
1)通过key获取到位置index
2)index位置没有节点返回null
3)找到与key对应的key所在位置,将链表向前覆盖进行删除,同时返回key对应的value
public V remove(K key){
//key->index
//当前位置中寻找当前key所对应的节点
int hash = hash(key);
int index = table.length-1 & hash;
Node<K,V> firstNode = table[index];
if(firstNode == null){
//表示table桶中的该位置不存在节点
return null;
}
//删除的是第一个节点
if(firstNode.key.equals(key)){
table[index] = firstNode.next;
size--;
return firstNode.value;
}
//相当于在链表中删除中间某一个节点
while(firstNode.next != null){
if(firstNode.next.key.equals(key)){
//firstNode.next是所要删除的节点
//firstNode是它的前一个节点
//firstNode.next.next是它的后一个节点
firstNode.next = firstNode.next.next;
size--;
return firstNode.next.value;
}else{
firstNode = firstNode.next;
}
}
return null;
}
5.resize与rehash实现
resize用于对哈希表进行2倍扩容。
public void resize(){
//HashMap的扩容
//table进行扩容 2倍的方式 扩容数组
Node<K, V>[] newTable = new Node[table.length*2];
//index -> table.length-1 & hash
//重哈希
for(int i=0; i<table.length; i++){
rehash(i, newTable);
}
this.table = newTable;
}
在容量进行扩充后,需要对哈希表进行重哈希操作。
如上图所示,一开始数组长度为4,,0,4,8分别于table.length取余后得到index均在0号位置,1,2,6,3,也同样如此,在进行二倍扩容后,以4为例,扩容器前在0号位置,扩容后到了4号位置,因为需要对哈希表中的元素进行重哈希操作,并且发现扩容后元素位置有个特点,要么它还在原位置,要么在原位置+扩容后的长度的位置上。
实现如下:
将每一个元素都进行重新计算,rehash需要两个参数,一个index位置,一个新数组newTable。先获取当前结点在原数组中的index,若为空则直接return。若不为空,将原位置看做低位,原位置+扩容长度的位置看成高位, 根据新数组的长度重新计算散列值,若新位置与旧位置相等,说明在低位,如果lowHead为空,就是第一次插入,将当前结点既当头又当尾,否则就尾插法插到tail后面。while结束后,要将tail的next置null,然后将head放在高低位对应的位置,即原位或原位+扩容长度位置。
public void rehash(int index, Node<K,V>[] newTable){
//相当于对原先哈希表中每一个有效节点 进行 重哈希的过程
Node<K,V> currentNode = table[index];
if(currentNode == null){
return;
}
Node<K,V> lowHead = null; //低位的头
Node<K,V> lowTail = null;//低位的尾
Node<K,V> highHead = null;//高位的头
Node<K,V> highTail = null;//高位的尾
while(currentNode != null){
//遍历index位置的所有节点
int newIndex = hash(currentNode.key) & (newTable.length-1);
if(newIndex == index){
//当前节点链到lowTail之后
if(lowHead == null){
lowHead = currentNode;
lowTail = currentNode;
}else{
lowTail.next = currentNode;
lowTail = lowTail.next;
}
}else{
//当前节点链到highTail之后
if(highHead == null){
highHead = currentNode;
highTail = currentNode;
}else{
highTail.next = currentNode;
highTail = highTail.next;
}
}
currentNode = currentNode.next;
}
//要么在原位置 (低位位置)
if(lowHead != null && lowTail != null){
lowTail.next = null;
newTable[index] = lowHead;
}
//要么跑到原位置 + 扩容前长度 (高位位置)
if(highHead != null && highTail != null){
highTail.next = null;
newTable[index + table.length] = highHead;
}
}
}
五、源码
1.类属性与继承关系
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
// 序列号
private static final long serialVersionUID = 362498820763181265L;
// 默认的初始容量是16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认的填充因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 当桶(bucket)上的结点数大于这个值时会转成红黑树;+对应的table的最小大小为64,即MIN_TREEIFY_CAPACITY ;这两个条件都满足,会链表会转红黑树
static final int TREEIFY_THRESHOLD = 8;
// 当桶(bucket)上的结点数小于这个值时树转链表
static final int UNTREEIFY_THRESHOLD = 6;
// 桶中结构转化为红黑树对应的table的最小大小
static final int MIN_TREEIFY_CAPACITY = 64;
// 存储元素的数组,总是2的幂次倍
transient Node<k,v>[] table;
// 存放具体元素的集
transient Set<map.entry<k,v>> entrySet;
// 存放元素的个数,注意这个不等于数组的长度。
transient int size;
// 每次扩容和更改map结构的计数器
transient int modCount;
// 临界值 当实际大小(容量*填充因子)超过临界值时,会进行扩容
int threshold;
// 填充因子
final float loadFactor;
}
HashMap继承自父类(AbstractMap),实现了Map、Cloneable、Serializable接口。其中,Map接口定义了一组通用的操作;Cloneable接口则表示可以进行拷贝,在HashMap中,实现的是浅层次拷贝,即对拷贝对象的改变会影响被拷贝的对象;Serializable接口表示HashMap实现了序列化,即可以将HashMap对象保存至本地,之后可以恢复状态。
其中链表转红黑树,并不是达到8个Node节点的阈值就进行转换,而是要判断一下整个数据结构中的Node数量是否大于64,大于才会转,小于就会用扩容数组的方式代替红黑树的转换。在源码的putVal中,当 binCount >= TREEIFY_THRESHOLD - 1时,会调用 treeifyBin(tab, hash)方法,就是链表转红黑树方法,当 tab.length)< MIN_TREEIFY_CAPACITY ,会扩容数组大小。
2.构造函数
public HashMap(int initialCapacity, float loadFactor) {
// 初始容量不能小于0,否则报错
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
// 初始容量不能大于最大值,否则为最大值
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
// 填充因子不能小于或等于0,不能为非数字
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// 初始化填充因子
this.loadFactor = loadFactor;
// 初始化threshold大小
this.threshold = tableSizeFor(initialCapacity);
}
其中tableSizeFor(initialCapacity)返回大于initialCapacity的最小的二次幂数值,>>> 操作符表示无符号右移,高位取0。
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;
}
3.hash算法
在jdk1.8中:
首先获取对象的hashCode()值,然后将hashCode值右移16位,然后将右移后的值与原来的hashCode做异或运算,返回结果。(其中h>>>16,在JDK1.8中,优化了高位运算的算法,使用了零扩展,无论正数还是负数,都在高位插入0)。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
在putVal源码中,通过(n-1)&hash获取该对象的键在hashmap中的位置。(其中hash的值就是(1)中获得的值)其中n表示的是hash桶数组的长度,并且该长度为2的n次方,这样(n-1)&hash就等价于hash%n。因为&运算的效率高于%运算。其中 n:hash槽数组大小;i:Node在数组中的索引值。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
...
if ((p = tab[i = (n - 1) & hash]) == null)//获取位置
tab[i] = newNode(hash, key, value, null);
...
}
4.HashMap 的容量
源码中HashMap的容量为2的幂次方,为什么要这样设置呢?
例如:
不采用2的幂次方,假设数组长度是10
1010 & 101010100101001001000 结果:1000 = 8
1010 & 101000101101001001001 结果:1000 = 8
1010 & 101010101101101001010 结果: 1010 = 10
1010 & 101100100111001101100 结果: 1000 = 8
这样做的结果会使不同的key值进入到相同的插槽中,形成链表,性能急剧下降。因此要保将& 中的二进制位全置为 1,也就是2的幂次方,才能最大限度的利用 hash 值,并更好的散列。如果是 1010,有的散列结果是永远都不会出现的,比如 0111,0101,1111,1110…,只要 & 之前的数有 0, 对应的 1 肯定就不会出现(因为只有都是1才会为1),大大限制了散列的范围。
好博客就要一起分享哦!分享海报
此处可发布评论
评论(0)展开评论
展开评论