手撕 HashMap
手撕 HashMap
概述
我们先来看一张图,回顾一下之前学习的
ArrayList、LinkedList、HashMap
补充说明
数组和链表迭代的方式不同
ArrayList实现了
RandomAccess
接口,这是一个标记接口,标注是否可以随机访问 ArrayList使用数组实现,可以随机访问,经过测试:使用for循环遍历ArrayList更快,而LinkedList没有实现这个RandomAccess接口,不支持随机访问,使用迭代器遍历更快 RandomAccess接口的作用 就是用来判断选择哪个方式遍历
什么是Hash?
- 哈希:英文是Hash,也称为散列
- 基本原理就是把
任意长度
输入,转化为固定长度
输出 - 这个映射的规则就是
Hash算法
,而原始数据映射的二进制串
就是Hash值
Hash的特点
- 从Hash值不可以
反向推导
出原始数据 - 输入数据的
微小变化
会得到完全不同的Hash值相同的数据一定可以得到相同的值 - 哈希算法的执行效率要
高效
,长的文本也能快速计算Hash值 - Hash算法的
冲突
概率要小
由于Hash原理就是将输入空间的值映射成Hash空间内,而Hash值的空间远远
小于
输入的空间,根据抽屉原理,一定会存在不同的输入被映射成相同输出的情况
**抽屉原理:**桌子上有10个苹果,将其放在9个抽屉里面,那必有一个抽屉不少于2个苹果
HashMap 原理讲解
HashMap 的继承体系
- HashMap继承了AbstractMap,实现了
Cloneable接口、Serializable接口、Map<K,V>接口
Node 的数据结构分析
final int hash;
final K key;
V value;
Node<K,V> next;
底层数据结构
put数据原理分析
什么是Hash碰撞?
假如我有存储一个元素,发现其Key的Hash值还是1122,那么经过扰动之后,其位置还是2,所以此时,就有冲突,这个时候就要解决冲突。
解决Hash碰撞的方法
- 开放寻址法
- 拉链法 [HashMap就是使用了此方法]
什么是链化?
- 在JDK1.7之前,假如数据量很大,那么碰撞的概率也很大,此时,拉链法的链子就会很长,那么就会降低查找速度
- 所以在JDK1.8之后引入红黑树
HashMap的扩容原理
因为当数据表很多的时候,碰撞使得冲突和查找速度都上升,此时就要扩容
手撕源码
HashMap核心属性分析(threshold、loadFactor、size、modCount)
threshold
:扩容阈值loadFactor
:负载因子size
:map实际的元素个数modCount
:map修改元素的次数,如删除和增加,但是对同一个位置进行修改 value,不增加
构造方法分析
一共有4个构造函数
/**
* @param initialCapacity 初始化大小
* @param loadFactor 负载因子
*/
public HashMap(int initialCapacity, float loadFactor) {
// 其实就是做了一些校验
// initialCapacity 必须是大于0 ,最大值也就是 MAXIMUM_CAPACITY
if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY;
// loadFactor 必须大于0
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
/**
* 作用:返回一个大于等于当前值cap的一个数字,并且这个数字一定是2的次方数
* -------------- 有int n = cap - 1; 的情况 ------------------
* cap = 10
* n = 10 - 1 => 9
* >>> 表示无符号右移多少位
* 0b1001 | 0b0100 => 0b1101
* 0b1101 | 0b0011 => 0b1111
* 0b1111 | 0b0000 => 0b1111
* 0b1111 => 15
* return 15 1;
* -------------- 假设没有int n = cap - 1; 的情况 ------------------
* cap = 16
* n = 16;
* 0b10000 | 0b01000 => 0b11000
* 0b11000 | 0b00110 => 0b11110
* 0b11110 | 0b00001 => 0b11111
* =>0b11111 => 31
* return 31 1;
* <p>
* 0001 1101 1100 => 0001 1111 1111 1 => 0010 0000 0000 一定是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;
}
/**
* @param initialCapacity 初始化大小
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
核心知识点:为什么 table 的长度 一定是2的幂?
- 计算Hash值得算法,实际就是取模,hash%length,
- 计算机中直接求余效率不如位移运算,源码中做了优化hash&(length-1)
- 要想保证hash%length==hash&(length-1)
- 那么length必须是2的n次方;
HashMap put 方法分析 → putVal 方法分析(重点)
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* 作用:让key的hash值的高16位也参与路由运算
* 异或:相同则返回0,不同返回1
* ------------ 例子 -------------------
* >>> 16:表示无符号右移16位
* ^:相同返回0,不同返回1
* 假设 h = 0b 0010 0101 1010 1100 0011 1111 0010 1110
* 0b 0010 0101 1010 1100 0011 1111 0010 1110
* ^
* 0b 0000 0000 0000 0000 0010 0101 1010 1100
* => 0010 0101 1010 1100 0001 1010 1000 0010
* -------------------------------------
* 结论:
* 在 table 还不是很长的情况下,让高16位也参与进来,为了减少冲突和碰撞
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
/**
* put的 核心方法(重点)
*
* @param hash:key的hash值
* @param key:key
* @param value:value
* @param onlyIfAbsent:如果散列表中已经存在相同的key,就不要更改现有的值;
* 设置为true表示开启,false表示关闭
* @param evict:如果为false,则表处于创建模式
* @return
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
//tab:引用当前hashMap的散列表
//p:表示当前散列表的元素
//n:表示散列表数组的长度
//i:表示路由寻址的结果
Node<K, V>[] tab;
Node<K, V> p;
int n, i;
// 延迟初始化逻辑,第一次调用 putVal 的时候会初始化hashMap对象中最耗费内存的散列表
// 如果 table 为null,或者长度为0,就开始创建
if ((tab = table) == null || (n = tab.length) == 0)
// 第一次插入数据的时候才会初始化
n = (tab = resize()).length;
// 最简单的一种情况,寻址找到的桶位,刚好是 null ,这个时候,就直接将当前的 k-v => node 扔进去就可以了
// tab 和 n 在上一个 if 中被赋值
// 执行一次路由运算 (n - 1) & hash,得到hash的地址
// 如果 tab 中没有这个元素或者等于null
if ((p = tab[i = (n - 1) & hash]) == null)
// 创建一个新的Node 就把 k-v 封装成一个Node放在 tab 的i位置
tab[i] = newNode(hash, key, value, null);
// 此时可能是数组、可能是链表、可能是红黑树
else {
// e:不为null的话,就找到了一个与当前要插入的 k-v 一致的node元素
// k:表示临时的一个key
Node<K, V> e;
K k;
// 表示桶位中的该元素,与你当前插入元素的key完全一致,后续需要进行替换操作
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// p:已经树化了
else if (p instanceof TreeNode)//红黑树,下期讲。进QQ群:865-373-238
e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
// 是链表
else {
// 链表的情况,而且链表的头元素与我们要插入的key不一致
for (int binCount = 0; ; binCount) {
//条件成立的话,说明迭代到最后一个元素了,也没找到一个与你要插入的key一致的node
//说明需要加入到当前链表的末尾
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//条件成立的话,说明当前链表的长度已经达到树化的标准了,需要进行树化
if (binCount >= TREEIFY_THRESHOLD - 1)
//树化操作
treeifyBin(tab, hash);
break;
}
// 条件成立的话,说明找到了相同key的node元素,需要进行替换操作
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break;
// 循环
p = e;
}
}
// e不等于null,条件成立说明,找到了一个与你插入元素key完全一致的数据,需要进行替换
if (e != null) {
// 把新的值覆写
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null) e.value = value;
afterNodeAccess(e);
// 返回替换前的旧值
return oldValue;
}
}
// modCount:表示散列表结构被修改的次数,替换Node元素的value不计数
modCount;
// 插入新元素,size自增,如果自增后的值 大于 扩容阈值,则触发扩容。
if ( size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
HashMap resize 扩容方法分析(重点)
/**
* -------------- 非常重点 --------------
* 为什么需要扩容?
* 为了解决哈希冲突导致的链化影响查询效率的问题,扩容会缓解该问题。
*/
final Node<K, V>[] resize() {
// oldTab:引用扩容前的哈希表
Node<K, V>[] oldTab = table;
// oldCap:表示扩容之前table数组的长度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// oldThr:表示扩容之前的扩容阈值,触发本次扩容的阈值
int oldThr = threshold;
// newCap:扩容之后table数组的大小
// newThr:扩容之后,下次再次触发扩容的条件
int newCap, newThr = 0;
//条件如果成立说明 hashMap中的散列表已经初始化过了,这是一次正常扩容
if (oldCap > 0) {
//扩容之前的table数组大小已经达到 最大扩容阈值后,则不再扩容,且设置扩容条件为 int 最大值。
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// oldCap左移一位实现数值翻倍,并且赋值给newCap, newCap 小于 table数组最大值限制,且扩容之前的阈值 >= 16
// 这种情况下,则 下一次扩容的阈值 等于 当前阈值翻倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1;
}
//oldCap == 0,说明hashMap中的散列表是null
//1.new HashMap(initCap, loadFactor);
//2.new HashMap(initCap);
//3.new HashMap(map); 并且这个map有数据
else if (oldThr > 0)
newCap = oldThr;
// oldCap == 0,oldThr == 0
// 1.new HashMap();的时候
else {
newCap = DEFAULT_INITIAL_CAPACITY; // 16
newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 12
}
// newThr为0的时候,通过 (newCap * loadFactor) 计算出一个 newThr
if (newThr == 0) {
float ft = (float) newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ? (int) ft : Integer.MAX_VALUE);
}
// 更新扩容阈值为计算出来的 newThr
threshold = newThr;
// 创建一个很大的数组
@SuppressWarnings({"rawtypes", "unchecked"})
Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];
// 然后更新 table 的引用
table = newTab;
// oldTab不为null,说明hashMap本次扩容之前,table不为null
if (oldTab != null) {
// 迭代 一个一个位置去处理
for (int j = 0; j < oldCap; j) {
// 当前node节点
Node<K, V> e;
// 迭代遍历桶节点,如果节点不为空,才需要计算
// 但是桶里面的数据具体是哪种(单个数据、链表、树)并不确定,需要继续判断
if ((e = oldTab[j]) != null) {
// 把原来的数组数据置空,等待GC回收,原来的数据已经存在e里面
oldTab[j] = null;
// 第一种情况:当前桶位只有一个元素,从未发生过碰撞,这种情况直接计算出当前元素应存放在 新数组中的位置,然后
// 扔进去就可以了
if (e.next == null) newTab[e.hash & (newCap - 1)] = e;
// 第二种情况:当前节点已经树化,本期先不讲,下一期讲,红黑树
else if (e instanceof TreeNode) ((TreeNode<K, V>) e).split(this, newTab, j, oldCap);
// 第三种情况:桶位已经形成链表(注意细看)
else {
// 低位链表:存放在扩容之后的数组的下标位置,与当前数组的下标位置一致。
Node<K, V> loHead = null, loTail = null;
// 高位链表:存放在扩容之后的数组的下标位置为 (当前数组下标位置 扩容之前数组的长度)
Node<K, V> hiHead = null, hiTail = null;
// 当前链表的下一个元素
Node<K, V> next;
do {
next = e.next;
/**
* hash -> .... 1 1111
* hash -> .... 0 1111
* &
* 0b 10000
* => 结果只有两种情况:等于0 或者 不等于0
*/
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 get 方法分析
// 获得一个元素
public V get(Object key) {
Node<K, V> e;
// 先调用 hash(key)计算hash值,然后调用 getNode方法
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K, V> getNode(int hash, Object key) {
// tab:引用当前hashMap的散列表
// first:桶位中的头元素
// e:临时node元素
// n:table数组长度
Node<K, V>[] tab;
Node<K, V> first, e;
int n;
K k;
// 首先判断 table 不是null 且长度不为0,并且头元素不为null
if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
//第一种情况:定位出来的桶位元素 即为咱们要get的数据
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);
}
}
// 都没有,就返回null
return null;
}
HashMap remove方法分析
// 移除元素的方法
public V remove(Object key) {
Node<K,V> e;
// 调用hash方法,获得哈希值,然后调用removeNode
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
final Node<K, V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) {
// tab:引用当前hashMap中的散列表
// p:当前node元素
// n:表示散列表数组长度
// index:表示寻址结果
Node<K, V>[] tab;
Node<K, V> p;
int n, index;
// 判断 table 是否为空,是否长度为0,且对应的hash值是否存在数组里面,才继续向下走
if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) {
// 说明路由的桶位是有数据的,需要进行查找操作,并且删除
// node:查找到的结果
// e:当前node的下一个元素
Node<K, V> node = null, e;
K k;
V v;
// 第一种情况:当前桶位中的头元素 即为 你要删除的元素
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
node = p;
// 说明,当前桶位要么是链表,要么是红黑树
else if ((e = p.next) != null) {
// 判断当前桶位是否升级为 红黑树了
if (p instanceof TreeNode)
// 第二种情况:红黑树查找操作,下一期再说
node = ((TreeNode<K, V>) p).getTreeNode(hash, key);
else {
// 第三种情况:链表的情况
do {
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
node = e;
break;
}
// 循环遍历
p = e;
} while ((e = e.next) != null);
}
}
// 判断node不为空的话,说明按照key查找到需要删除的数据了
if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) {
// 第一种情况:node是树节点,说明需要进行树节点移除操作
if (node instanceof TreeNode)
((TreeNode<K, V>) node).removeTreeNode(this, tab, movable);
// 第二种情况:桶位元素即为查找结果,则将该元素的下一个元素放至桶位中
else if (node == p)
tab[index] = node.next;
// 第三种情况:将当前元素p的下一个元素 设置成 要删除元素的 下一个元素
else
p.next = node.next;
// 修改次数增加
modCount;
// 大小减1
--size;
afterNodeRemoval(node);
// 返回删除的node元素
return node;
}
}
// 如果都没有执行,那么就返回null
return null;
}
HashMap replace方法分析
// 根据 k 和 v 替换
@Override
public V replace(K key, V value) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) != null) {
V oldValue = e.value;
e.value = value;
afterNodeAccess(e);
return oldValue;
}
return null;
}
// 根据 k oldValue newValue 替换
@Override
public boolean replace(K key, V oldValue, V newValue) {
Node<K,V> e; V v;
if ((e = getNode(hash(key), key)) != null &&
((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {
e.value = newValue;
afterNodeAccess(e);
return true;
}
return false;
}
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgfhbbg
系列文章
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01