公明网站建设,成品网站是什么,江门住房城乡建设厅网站,公司的网站建设费用算什么费用文章目录1. HashMap概述2. 哈希冲突3. 树化与退化3.1 树化的意义3.2 树的退化4. 二次哈希5. put方法源码分析6. key的设计7. 并发问题参考 如何防止因哈希碰撞引起的DoS攻击_hashmap dos攻击_双子孤狼的博客-CSDN博客 为什么 HashMap 要用 h^(h #xff1e;#xff1e;#…
文章目录1. HashMap概述2. 哈希冲突3. 树化与退化3.1 树化的意义3.2 树的退化4. 二次哈希5. put方法源码分析6. key的设计7. 并发问题参考 如何防止因哈希碰撞引起的DoS攻击_hashmap dos攻击_双子孤狼的博客-CSDN博客 为什么 HashMap 要用 h^(h 16) 计算hash值槽位数必须是 2^n?_一行Java的博客-CSDN博客HashMap面试看这一篇就够了_苦味代码的博客-CSDN博客 1. HashMap概述
HashMap是Java中最常用的集合框架。
在JDK1.7的时候HashMap的底层由数组和链表组成。数组是HashMap的主体而链表是为了解决哈希冲突而存在的。 在JDK1.8的时候HashMap的底层由数组、链表和红黑树组成。红黑树的出现是为了解决因哈希冲突导致的链表长度过长影响HashMap性能的问题。红黑树搜索的空间复杂度为O(logn)而链表却是O(n)。
也就是当链表的长度达到一定长度后链表就会进行树化当然这是一种笼统说法具体细节待会深究。 2. 哈希冲突
哈希冲突是指对不同的关键字通过一个哈希函数进行计算得出相同的哈希值这样使得它们存在的数组时候发生了冲突。
解决哈希冲突通常有以下四种方法。
开放定址法
开放定址法也称为再散列地址法。基本思想就是如果pH(key)出现冲突时则以p为基础再次hashp1H(p),如果p1再次出现冲突则以p1为基础以此类推直到找到一个不冲突的哈希地址pi。
就是说当发生哈希冲突的时候对哈希值进行求哈希值只要哈希表足够大那么总能找到一个这样的空地址。
因此开放定址法所需要的hash表的长度要大于等于所需要存放的元素。
再哈希法
再哈希法也称双重散列多重散列。基本思想就是提供多个不同的哈希函数当R1H1(key1)发生冲突时再计算R2H2(key1)直到没有冲突为止。这样做虽然不易产生堆集但增加了计算的时间。
链地址法
链地址法也称拉链法将哈希值相同的元素构成一个同义词的单链表并将单链表的头指针存放在哈希表的第i个单元中查找、插入和删除主要在同义词链表中进行。链表法适用于经常进行插入和删除的情况。
建立公共溢出区
将哈希表分为公共表和溢出表当溢出发生时将所有溢出数据统一放到溢出区。
而HashMap采用的就是链地址法。
并且JDK1.7和JDK1.8的链表插入节点时采用的方式不一样
JDK1.7采用的是头插法。JDK1.8采用的是尾插法。 3. 树化与退化
树化是指将链表转化为红黑树的过程。
在JDK1.8的HashMap中树化的规则是这样的当链表长度超过树化阈值 8 时先尝试扩容来减少链表长度如果数组容量已经 64才会进行树化
所以HashMap并不是一开始就进行树化的。
阈值设置为8主要是因为泊松分布具体原因HashMap作者在源码中也有解释 意思就是说理想情况下使用随机的哈希码容器中节点分布在 hash 桶中的频率遵循泊松分布按照泊松分布的计算公式计算出了桶中元素个数和概率的对照表可以看到链表中元素个数为 8 时的概率已经非常小再多的就更少了所以原作者在选择链表元素个数时选择了 8是根据概率统计而选择的。
也就是说哈希 值如果足够随机则在 哈希表内按泊松分布在负载因子 0.75 的情况下长度超过 8 的链表出现概率是 0.00000006树化阈值选择 8 就是为了让树化几率足够小。 3.1 树化的意义
首先树化成红黑树可以避免DOS攻击防止链表超长时性能下降树化应当是偶然情况是保底策略。 DOS攻击是指恶意的攻击者通过使用以下精心构造的数据使得所有数据经过哈希函数之后都映射到了一个位置导致了大量数据出现了哈希冲突通过HashMap查询的效率从O(1)变成了O(n)。这样就有可能发生因为查询操作消耗大量 CPU 或者线程资源而导致系统无法响应其他请求的情况从而达到拒绝服务攻击DoS的目的。 其次哈希表的查找更新的时间复杂度是 O(1)而红黑树的查找更新的时间复杂度是 O(log2n)。
但是由于TreeNode 占用空间也比普通 Node 的大如非必要尽量还是使用链表。 3.2 树的退化
树的退化主要是发生在这两种情况下
HashMap在扩容时如果拆分树树元素个数小于等于6则会退化成链表remove 树节点时若 root、root.left、root.right、root.left.left 有一个为 null 也会退化为链表 4. 二次哈希
在JDK1.8的源码的put方法中会将key进行二次哈希
public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}static final int hash(Object key) {int h;return (key null) ? 0 : (h key.hashCode()) ^ (h 16);
}通过源码可以了解到首先会调用key对象的hashCode方法进行求哈希值然后将该哈希值的低16位与高16位进行异或运算这样做的目的是为了综合高位数据让哈希分布更为均匀减少哈希碰撞。
并且这么做可以在数组 table 的 length 比较小的时候也能保证考虑到高低Bit都参与到Hash的计算中同时不会有太大的开销。
操作值hashCode()1,794,106,052二进制01101010 11101111 11100010 11000100h 1600000000 00000000 01101010 111011115. put方法源码分析
查看put方法源码
transient NodeK,V[] table;public V put(K key, V value) {// 调用上文我们已经分析过的hash方法return putVal(hash(key), key, value, false, true);
}final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {NodeK,V[] tab; NodeK,V p; int n, i;if ((tab table) null || (n tab.length) 0)// 第一次put时会调用resize进行桶数组初始化n (tab resize()).length;// 根据数组长度和哈希值相与来寻址原理上文也分析过if ((p tab[i (n - 1) hash]) null)// 如果没有哈希碰撞直接放到桶中tab[i] newNode(hash, key, value, null);else {NodeK,V e; K k;if (p.hash hash ((k p.key) key || (key ! null key.equals(k))))// 哈希碰撞且节点已存在直接替换e p;else if (p instanceof TreeNode)// 哈希碰撞树结构e ((TreeNodeK,V)p).putTreeVal(this, tab, hash, key, value);else {// 哈希碰撞链表结构for (int binCount 0; ; binCount) {if ((e p.next) null) {p.next newNode(hash, key, value, null);// 链表过长转换为树结构if (binCount TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}if (e.hash hash ((k e.key) key || (key ! null key.equals(k))))// 如果节点已存在则跳出循环break;// 否则指针后移继续后循环p e;}}if (e ! null) { // existing mapping for key// 对应着上文中节点已存在跳出循环的分支// 直接替换V oldValue e.value;if (!onlyIfAbsent || oldValue null)e.value value;afterNodeAccess(e);return oldValue;}}modCount;if (size threshold)// 如果超过阈值还需要扩容resize();afterNodeInsertion(evict);return null;
}
put方法的大体思路如下
调用key的hashCode方法计算哈希值并据此计算出数组下标index如果发现当前的桶数组为null则调用resize()方法进行初始化如果没有发生哈希碰撞则直接放到对应的桶中如果发生哈希碰撞且节点已经存在就替换掉相应的value如果发生哈希碰撞且桶中存放的是树状结构则挂载到树上如果碰撞后为链表添加到链表尾如果链表超度超过TREEIFY_THRESHOLD默认是8则将链表转换为树结构数据put完成后如果HashMap的总数超过threshold就要resize
put方法中比较重要的一个知识点莫过于计算索引了。
首先先调用hash方法。 在hash方法中计算对象的hashCode方法再进行调用HashMap的hash()方法进行二次哈希 接着将hash方法返回的二次哈希值记为hash用(n - 1)也就是数组长度减一对hash进行与运算(n - 1) hash
这里使用n-1是因为以默认数组长度16为例子那么数组下标为0-15哈希值计算hash%(2^4)其本质就是和长度取余。也就等价于 (2^4 - 1) hash
在JDK1.8和JDK1.7中它们的put方法实现有所不同 链表插入节点时1.7 是头插法1.8 是尾插法 1.7 是大于等于阈值且没有空位时才扩容而 1.8 是大于阈值就扩容 1.8 在扩容计算 Node 索引时会优化 6. key的设计
HashMap 的 key 可以为 null但 Map 的其他实现就不一定了
其key应当符合下面的要求
作为 key 的对象必须实现 hashCode 和 equals并且 key 的内容不能修改不可变key 的 hashCode 应该有良好的散列性 7. 并发问题
扩容死链1.7 会存在
void transfer(Entry[] newTable, boolean rehash) {int newCapacity newTable.length;for (EntryK,V e : table) {while(null ! e) {EntryK,V 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;}}
}e 和 next 都是局部变量用来指向当前节点和下一个节点线程1绿色的临时变量 e 和 next刚引用了这俩节点还未来得及移动节点发生了线程切换由线程2蓝色完成扩容和迁移 线程2 扩容完成由于头插法链表顺序颠倒。但线程1 的临时变量 e 和 next 还引用了这俩节点还要再来一遍迁移 第一次循环 循环接着线程切换前运行注意此时 e 指向的是节点 anext 指向的是节点 be 头插 a 节点注意图中画了两份 a 节点但事实上只有一个为了不让箭头特别乱画了两份当循环结束是 e 会指向 next 也就是 b 节点 第二次循环 next 指向了节点 ae 头插节点 b当循环结束时e 指向 next 也就是节点 a 第三次循环 next 指向了 nulle 头插节点 aa 的 next 指向了 b之前 a.next 一直是 nullb 的 next 指向 a死链已成当循环结束时e 指向 next 也就是 null因此第四次循环时会正常退出 数据错乱1.71.8 都会存在
假设现在有两个线程A和B这两个线程都分别将数据C和D放进HashMap中并且C和D的二次哈希值都一样。
线程A和线程B同时执行到检查有无哈希冲突的那一段代码。A和B检查均无发现有哈希冲突。
假设线程A比较快于是线程A将tab[i]指向数据C。
这时候线程B将tab[i]指向数据D。
最终tab[i]指向数据D导致了数据C丢失
