HashMap的容量是有限的。当经过多次元素插入,使得HashMap达到一定饱和度时,Key映射位置发生冲突的几率会逐渐提高。

这时候,HashMap需要扩展它的长度,也就是进行Resize

影响发生Resize的因素有两个:

1.Capacity

HashMap的当前长度。HashMap的长度是2的幂。

2.LoadFactor

HashMap负载因子,默认值为0.75f。

衡量HashMap是否进行Resize的条件如下: 

HashMap.Size   >=  Capacity * LoadFactor

Resize:

1.扩容

创建一个新的Entry空数组,长度是原数组的2倍。

2.ReHash

遍历原Entry数组,把所有的Entry重新Hash到新数组。为什么要重新Hash呢?因为长度扩大以后,Hash的规则也随之改变。

让我们回顾一下Hash公式:

index =  HashCode(Key) &  (Length - 1)

当原数组长度为8时,Hash运算是和111B做与运算;新数组长度为16,Hash运算是和1111B做与运算。Hash结果显然不同。

 

Resize后的HashMap:

ReHash的Java代码如下:

/**
* Transfers all entries from current table to newTable.
*/
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,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;
}
}
}

  然而HashMap 高并发下可能会形成链表环。

  那如何判断链表有环呢?

快慢指针法

首先创建两个指针1和2(在java里就是两个对象引用),同时指向这个链表的头节点。然后开始一个大循环,在循环体中,让指针1每次向下移动一个节点,让指针2每次向下移动两个节点,然后比较两个指针指向的节点是否相同。如果相同,则判断出链表有环,如果不同,则继续下一次循环。

例如链表A->B->C->D->B->C->D,两个指针最初都指向节点A,进入第一轮循环,指针1移动到了节点B,指针2移动到了C。第二轮循环,指针1移动到了节点C,指针2移动到了节点B。第三轮循环,指针1移动到了节点D,指针2移动到了节点D,此时两指针指向同一节点,判断出链表有环。

此方法也可以用一个更生动的例子来形容:在一个环形跑道上,两个运动员在同一地点起跑,一个运动员速度快,一个运动员速度慢。当两人跑了一段时间,速度快的运动员必然会从速度慢的运动员身后再次追上并超过,原因很简单,因为跑道是环形的。

最新文章

  1. 百度api短信开发
  2. H5开发之Eclipes 编码乱码问题
  3. spot 5、ALOS监督分类波段组成
  4. VS2015中使用Git
  5. python_如何去除字符串中不想要的字符?
  6. 关于CSRF
  7. Python面试笔记四
  8. 关注Yumiot公众号,了解最新的物联网资讯
  9. Dynamics 365 Online-Virtual Entities
  10. python虚拟环境virtualenv简介
  11. linux每日命令(8):mv命令
  12. js中对象如何添加新属性?
  13. 电脑组装DIY
  14. springboot的日志框架slf4j (使用logback输出日志以及使用)
  15. Android 建立手机与手表数据同步机制总结
  16. 如何利用启明星Portal门户系统的Page模块构建工作流表单
  17. as modern frameworks have warmed people to the idea of using builder-type patterns and anonymous inner classes for such things
  18. 从golang-gin-realworld-example-app项目学写httpapi (七)
  19. php 统计二维数组中某个相等值的总个数,并且组合成一个新的数组 转发
  20. android入门 — AlertDialog对话框

热门文章

  1. 人机大战之AlphaGo的硬件配置和算法研究
  2. 50. Pow(x, n) (编程技巧)
  3. 从xml文件中读取注释
  4. Android之动态图片
  5. 修改linux命令行提示符
  6. Apache 目录权限
  7. 十天学Linux内核之第八天---构建Linux内核
  8. 过滤器实现 (cookie认证)
  9. [Web Service] Tutorial Basic Concepts
  10. C++:如何正确的定义一个接口类
  11. [JSON] 前后台如何通过$.ajax()传输JSON数据
  12. Cmder 常用配置
  13. 软件工程_1st weeks
  14. vue全家桶+Koa2开发笔记(8)--开发网页
  15. Windows10系统的Linux子系统中安装MySQL数据库心得
  16. 在C#中使用WMI查询进程的用户信息
  17. Xamarin 技术解析
  18. 搭建属于自己的NuGet服务器
  19. C++解析(8):C++中的新成员
  20. bzoj 2530 [Poi2011]Party 构造