hashmap分析,java hashmap原理 面试
如何解决写爬虫IP受阻的问题？立即使用。
HashMap是一个由数组和链表组成的复杂结构。哈希值确定键值在数组中的位置。当哈希值相同时，以链表的形式存储。当链表的长度达到设定的阈值时，就会被树化。这样做是为了确保数据安全和数据相关操作的效率。
HashMap的性能取决于hashcode的有效性，所以hashCode和equals的基本约定规则就显得尤为重要，比如：equals相等，hashCode必须相等；重写hashCode，重写equals；HashCode需要一致，状态改变返回的哈希值仍然需要一致；对称，反射和传输的平等
HashMap 与 Hashtable、TreeMap 的区别
HashMap:基于数组的异步哈希表，支持空键或空值，是键值对访问数据场景的首选。
Hashtable:基于数组的同步哈希表，不支持空键或空值，因为同步会影响性能，很少使用。
TreeMap:基于红黑树提供顺序访问的Map，与HashMap相比节省了空间，但其数据操作(检查、添加和删除)时间复杂度为：O(log(n))，与HashMap不同。支持空值。当键为空且没有实现比较器接口时，会出现NullPointerException。实现比较器接口，判断空对象，实现正常存储。
HashMap、Hashtable和TreeMap都以键值对的形式存储或操作数据元素。HashMap和TreeMap继承自AbstractMap类，Hashtable继承自Dictionary类，都实现了Map接口。
HashMap 源码解析
散列表()
public HashMap(int initial capacity，float loadFactor){
//.
this.loadFactor=负载系数；
this . threshold=tablesize for(initial capacity)；
HashMap初始化的时候只设置了一些初始值，但是处理数据的时候会逐渐变得复杂，比如。put()方法。
HashMap.put()
公共V put(K键，V值){
返回putVal(hash(key)，key，value，false，true)；
}
final V putVal(int hash，K key，V value，boolean onlyIfAbsent，
布尔逐出){
//定义新的选项卡数组和节点对象
NodeK，V[]tab；NodeK，V p；int n，I；
//如果原表为空或者没有存储元素，需要先初始化tab。
if((tab=table)==null (n=tab . length)==0)
n=(tab=resize())。长度；
//当数组中对应的位置为空时，将新元素放入数组
if ((p=tab[i=(n - 1) hash])==null)
tab[i]=newNode(hash，key，value，null)；
//如果对应位置不为空，则处理哈希冲突。
否则{
NodeK，V e；K k
//1-公共元素判断：更新数组中对应的位置数据。
if (p.hash==hash
((k=p.key)==key (key！=null key.equals(k))))
e=p；
//2-红黑树判断：当P是树的节点时，将节点插入树中。
else if(p TreeNode的实例)
e=((TreeNodeK，V)p)。putTreeVal(this，tab，hash，key，value)；
//3-链表判断：插入节点
否则{
for(int bin count=0；binCount) {
//找到尾节点并插入
if ((e=p.next)==null) {
p.next=newNode(hash，key，value，null)；
//判断链表的长度是否达到树化阈值，如果达到，则对链表进行树化。
第一个if(bin count=tree ify _ THRESHOLD-1)//-1
treeifyBin(tab，hash)；
打破；
}
//更新链表中对应的位置数据。
如果(例如，哈希==哈希
((k=e.key)==key (key！=null key.equals(k))))
打破；
p=e；
}
}
//如果此映射存在，则覆盖它
如果(e！=null) { //键的现有映射
V oldValue=e.value
//确定是否允许覆盖以及值是否为空。
如果(！onlyIfAbsent oldValue==null)
e.value=值；
//回调以允许LinkedHashMap后操作
afterNodeAccess(e)；
返回旧值；
}
}
//更新修改次数
modCount
//检查数组是否需要扩展。
if(大小阈值)
resize()；
//回调以允许LinkedHashMap后操作
afterNodeInsertion(驱逐)；
返回null
}当表格为空时，会通过resize()进行初始化，resize()有两个作用，一个是创建并初始化表格，另一个是在表格的容量不满足需求时进行扩展：
if(大小阈值)
resize()；具体的键值对存储位置计算方法是：
if ((p=tab[i=(n - 1) hash])==null)
//给数组分配一个新元素
tab[i]=newNode(hash，key，value，null)；
否则{
NodeK，V e；K k
//如果新插入的节点和表中的节点P的哈希值和键值相同
if (p.hash==hash
((k=p.key)==key (key！=null key.equals(k))))
e=p；
//如果是红黑树节点，插入红黑树。
else if(p TreeNode的实例)
e=((TreeNodeK，V)p)。putTreeVal(this，tab，hash，key，value)；
否则{
for(int bin count=0；binCount) {
//如果这个单链表只有一个头节点，就新建一个节点。
if ((e=p.next)==null) {
p.next=newNode(hash，key，value，null)；
//当链表长度大于8时，将链表变成红黑树。
第一个if(bin count=tree ify _ THRESHOLD-1)//-1
treeifyBin(tab，hash)；
打破；
}
如果(例如，哈希==哈希
((k=e.key)==key (key！=null key.equals(k))))
打破；
//及时更新P
p=e；
}
}
//如果此映射存在，则覆盖它
如果(e！=null) { //键的现有映射
V oldValue=e.value
//确定是否允许覆盖以及值是否为空。
如果(！onlyIfAbsent oldValue==null)
e.value=值；
afterNodeAccess(e)；//回调以允许LinkedHashMap后操作
返回旧值；
}
}注意。put()方法。它不是键的hashCode，而是将键的hashCode的高阶数据移位到低阶位进行异或运算，这样一些计算出来的hash值主要与高阶位不同的数据就不会因为HashMap中hash寻址时忽略容量以上的高阶位而被忽略，这样就可以有效避免这类情况下的hash冲突。
静态最终int哈希(对象键){
int h；
return (key==null)？0:(h=key . hashcode())^(h 16)；
}HashMap.resize()
final NodeK，V[] resize() {
//将当前底层数组赋给oldTab，为数据迁移做准备。
NodeK，V[]old tab=table；
//获取当前数组的大小，等于或小于0表示数组需要初始化，大于0表示数组需要扩展。
int oldCap=(oldTab==null)？0:old tab . length；
//获取容量扩展的阈值(容量*负载系数)
int oldThr=threshold
//定义并初始化新的数组长度和目标阈值
int newCap，new thr=0；
//确定是初始化数组还是扩展数组。如果等于或小于0，则需要初始化数组；如果大于0，则需要扩展数组。如果(oldCap 0)=true，则意味着容量扩展而不是初始化。
if (oldCap 0) {
//判断数组长度是否最大，maximum _ capacity=(2 ^ 30)
if (oldCap=MAXIMUM_CAPACITY) {
//阈值设置为最大值
阈值=整数。MAX _ VALUE
返回oldTab
}
else if((new cap=old cap 1)MAXIMUM _ CAPACITY
oldCap=DEFAULT _ INITIAL _ CAPACITY)
//目标阈值扩展2倍，数组长度扩展2倍。
new thr=old thr 1；//双阈值
}
//指示数组需要初始化而不是扩展。
else if (oldThr 0)
//说明调用HashMap的参数化构造函数，因为无参数构造函数不初始化threshold。
newCap=oldThr
//表示数组需要初始化而不是扩展，零初始阈值表示使用默认值。
否则{
//说明调用了HashMap的无参数构造函数。
new cap=DEFAULT _ INITIAL _ CAPACITY；
//计算目标阈值
new thr=(int)(DEFAULT _ LOAD _ FACTOR * DEFAULT _ INITIAL _ CAPACITY)；
}
//当目标阈值为0时，需要重新计算。公式为：容量(新容量)*负载系数。
if (newThr==0) {
float ft=(float)newCap * load factor；
new thr=(newCap MAXIMUM _ CAPACITY ft(float)MAXIMUM _ CAPACITY？
(int)ft:整数。MAX _ VALUE)；
}
//根据上述计算结果更新阈值。
threshold=newThr
//将新数组赋给基础数组
@SuppressWarnings({rawtypes ， unchecked})
NodeK，V[] newTab=(NodeK，V[])新节点[newCap]；
table=newTab
//-
//此时数组的初始化或扩展已经完成，但原数组中的数据还没有迁移到新数组(扩展后的数组)中。以下代码完成了从原始阵列到新阵列的数据迁移过程。
//-
//判断原始数组中是否有存储的数据，如果有，开始迁移数据。
if (oldTab！=null) {
//开始数据的循环迁移。
for(int j=0；j oldCapj) {
NodeK，V e；
//将数组中这个下标的数据赋给Node类型的变量E，判断不为空
if ((e=oldTab[j])！=null) {
old tab[j]=null；
//1-普通元素判断：判断数组中这个下标是否只存储一个元素，如果是，说明是普通元素，开始转移。
if (e.next==null)
new tab[e . hash(newCap-1)]=e；
//2-红黑树判断：判断这个下标是否是红黑树，如果是，进行数据迁移。
else if(e TreeNode的实例)
((TreeNodeK，V)e)。split(this，newTab，j，old cap)；
//3-链表判断：如果这个下标包含的数据既不是普通元素，也不是红黑树，那么它只能是一个用于数据传递的链表。
else { //保持顺序
NodeK，V loHead=null，loTail=null
NodeK，V hiHead=null，hiTail=null
NodeK，V next
做{
next=e.next
if ((e.hash oldCap)==0) {
if (loTail==null)
loHead=e；
其他
lotail . next=e；
loTail=e；
}
否则{
if (hiTail==null)
hiHead=e；
其他
hitail . next=e；
hiTail=e；
}
} while ((e=next)！=null)；
如果(loTail！=null) {
loTail.next=null
new tab[j]=loHead；
}
如果(hiTail！=null) {
hiTail.next=null
new tab[j old cap]=hiHead；
}
}
}
}
}
//初始化或扩展后返回新数组。
返回newTab
}容量和负载系数决定了阵列容量。多余空间过多会造成空间浪费，使用过多会影响操作性能。
如果你能清楚地知道HashMap将要访问的键值对的数量，你可以考虑预先设置一个合适的容量。具体数值可以根据扩容条件简单估算。根据前面的代码分析，我们知道它需要满足计算条件：荷载系数*容量元素个数。
因此，需要满足预设容量，该容量大于估计的单元数/负载因子，并且是2的幂。
但需要注意的是：
如果没有特殊要求，不要轻易更改，因为JDK自己的默认负载系数非常适合常见场景。如果确实需要调整，建议不要设置超过0.75的值，因为这样会显著增加冲突，降低HashMap的性能。如果负载系数过小，根据上述公式，预设的容量值也会进行调整，否则可能会导致更频繁的扩容，增加不必要的开销，自身的接入性能也会受到影响。
HashMap.get()
public V get(对象键){
NodeK，V e；
return (e=getNode(hash(key)，key))==null？null:e . value；
}
final NodeK，V getNode(int hash，Object key) {
NodeK，V[]tab；NodeK，V优先，e；int n；K k
//将表赋给变量页签，判断非空页签的工厂部分大于0。通过位运算得到取模结果，确定链表的第一个节点赋值并判断不为空。
if ((tab=table)！=null (n=tab.length) 0
(first=tab[(n - 1) hash])！=null) {
//判断第一个节点的哈希值。如果键的哈希值(相同地址等于)都为真，则表示第一个节点是目标节点，直接返回。
if (first.hash==hash //始终检查第一个节点
((k=first.key)==key (key！=null key.equals(k))))
先退；
//如果第一个节点不是目标节点，且有后续节点，则继续向后搜索。
if ((e=first.next)！=null) {
//1-Tree:判断该节点是否为树节点，如果是，则遍历树结构查找该节点，结果可能为空。
TreeNode的第一个实例)
先返回((TreeNodeK，V))。getTreeNode(hash，key)；
//2-链表：如果这个节点不是树节点，说明它是一个链表。遍历链表查找节点，结果可能为空。
做{
如果(例如，哈希==哈希
((k=e.key)==key (key！=null key.equals(k))))
返回e；
} while ((e=e.next)！=null)；
}
}
返回null
}HashMap 为什么会被树化
为了确保数据安全和相关的操作效率
因为在元素放置的过程中，如果一个对象有冲突哈希，放在同一个桶中，就会形成链表。我们知道链表查询是线性的，会严重影响访问性能。
然而，在现实世界中，构造哈希冲突的数据并不复杂。恶意代码可以利用这些数据与服务器进行大量的交互，造成服务器上大量的CPU占用，构成哈希碰撞拒绝服务攻击。类似的攻击也发生在国内一线互联网公司。以上是Java HashMap透析的细节。请多关注我们的其他相关文章！
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。