首页 > 其他分享 >【面试】【1】HashMap的扩容机制

【面试】【1】HashMap的扩容机制

时间:2022-08-15 21:15:38浏览次数:69  
标签:扩容 hash HashMap 链表 面试 因子 0.75

1、HashMap是一种数据存储的容器,当创建一个集合对象的时候,实际上就是在内存里面一次性的申请了一块内存空间,存储容量的大小是在创建集合的时候给指定的,HashMap的默认大小是16

2、当集合存储容量达到某个临界值的时候,就会动态扩容,临界值 = 扩容因子*容量大小,负载因子默认是0.75,也就是元素达到12的时候会触发扩容,扩容大小是原来的2倍;

3、HashMap本质上数组的结构,在扩容的时候需要新建一个更长的数组,然后将原来数组里面的数据copy到新数组就可以啦

 

为什么扩容因子是0.75?

1、扩容因子表示哈希表中值的填充程度

2、扩容因子越大,触发扩容的元素个数越多,虽然空间的整体利用率会比较高,但是hash冲突的概率也会比较高

3、扩容因子越小,触发扩容的元素个数越少,虽然hash冲突的概率降低,但是空间的整体利用率会降低,而且会增加扩容的频率

4、扩容因子是冲突的概率和空间利用率之间的平衡

5、HashMap采用链式寻址的方式来解决hash冲突,为避免链表过长带来时间复杂度增加的情况,所以链表长度大于等于7的时候,就会转为红黑树,从而提升检索的效率;当扩容因子为0.75的时候,链表长度达到8的可能性几乎为0

 

标签:扩容,hash,HashMap,链表,面试,因子,0.75
From: https://www.cnblogs.com/qingxuan0316/p/16589618.html

相关文章

  • Taurus.MVC 微服务框架 入门开发教程:项目部署:1、微服务应用程序常规部署实现多开,节点
    系列目录:本系列分为项目集成、项目部署、架构演进三个方向,后续会根据情况调整文章目录。本系列第一篇:Taurus.MVCV3.0.3微服务开源框架发布:让.NET架构在大并发的演进过......
  • centos7根分区扩容(减少home分区容量)
    由于安装centos时没有手动分区,导致/home分区过大。而在工作中基本使用docker来安装一些软件而安装docker的默认存储是在/var/lib/docker  时间长了,程序占用空间就大了......
  • Vue面试题-组件间通信方式
    父子组件:props(父传子)$emit/$on(子传父) $on已被Vue3废弃$parent/$children$children已被Vue3废弃ref隔代组件:透传:$attrs/$listeners$listners已被Vue3废......
  • 【java面试题】final
    【java面试题】final final的作用final的含义是最终的修饰类:表示类不可被继承修饰方法:表示方法不可被子类重写,但是可以重载修饰变量:表示变量一旦被赋值就不......
  • 【java面试题】 == 和 equals
    【java面试题】==和equals "=="比较的机制:==对比的是栈中的值基本数据类型是变量值,也就是inti=1;在栈中存放的是i=1,==比较的也是这个数值1引用类型是堆中......
  • 接口测试经典面试题:Session、cookie、token有什么区别?
    原文链接HTTP是一个没有状态的协议,这种特点带来的好处就是效率较高,但是缺点也非常明显,这个协议本身是不支持网站的关联的,比如https://ceshiren.com/和https://ceshiren.co......
  • 【java面试题】ArrayList和LinkedList的区别
    【java面试题】ArrayList和LinkedList的区别 ArrayList和LinkedList都实现了List接口,它们有一下的不同点:ArrayList是基于索引的数据接口,它的底层是数组,它可以以O(1)时......
  • 【java面试题】面向对象的特征
    【java面试题】面向对象的特征 面向对象编程是利用类和对象编程的一种思想,万物可归类,类是对于世界事物的高度抽象,万物皆对象,对象是具体的世界事物。面向对象的三大特征......
  • 面试突击74:properties和yml有什么区别?
    properties和yml都是SpringBoot支持的两种配置文件,它们可以看作是SpringBoot在不同时期的两款“产品”。在SpringBoot时代已经不需要使用XML文件格式来配置......
  • 搞定面试官 - 可以介绍一下在 MySQL 中你平时是怎么使用 COUNT() 的嘛?
    大家好,我是程序员啊粥。相信在大家的工作中,有很多的功能都需要用到count(*)来统计表中的数据行数。同时,对于一些大数据的表,用count都是瑟瑟发抖,往往会结合缓存等进行......