文档章节

Java中HashMap扩容机制思考

o
 osc_g8254g7s
发布于 2019/08/19 21:54
字数 618
阅读 3
收藏 0

精选30+云产品,助力企业轻松上云!>>>

1. HashMap在什么条件下扩容

判断HashMap的数组Size大小如果超过loadFactor*capacity,就要扩容。

相关的类属性:

  • capacity:当前数组容量,始终保持 2^n,可以扩容,扩容后数组大小为当前的 2 倍。

  • loadFactor:负载因子,默认为 0.75

    loadFactor加载因子是控制数组存放数据的疏密程度,loadFactor越趋近于1,那么 数组中存放的数据(entry)也就越多,也就越密,也就是会让链表的长度增加,loadFactor越小,也就是趋近于0,数组中存放的数据(entry)也就越少,也就越稀疏。

    loadFactor太大导致查找元素效率低,太小导致数组的利用率低,存放的数据会很分散。loadFactor的默认值为0.75f是官方给出的一个比较好的临界值

    给定的默认容量为 16,负载因子为 0.75。Map 在使用过程中不断的往里面存放数据,当数量达到了 16 * 0.75 = 12 就需要将当前 16 的容量进行扩容,而扩容这个过程涉及到 rehash、复制数据等操作,所以非常消耗性能。

  • threshold:扩容的阈值

    threshold = capacity * loadFactor,当Size>=threshold的时候,那么就要对数组扩增了。

2. HashMap 的长度为什么是2的幂次方

为了能让 HashMap 存取高效,尽量减少碰撞,把数据分配均匀,利用扰动函数hash方法对key进行处理得到Hash值Hash 值的范围值-2147483648到2147483647,前后加起来大概40亿的映射空间,只要哈希函数映射得比较均匀松散,一般应用是很难出现碰撞的。但问题是一个40亿长度的数组,内存是放不下的。所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算,得到的余数才能用来要存放的位置也就是对应的数组下标。这个数组下标的计算方法是“ (n - 1) & hash”。(n代表数组长度)

取余(%)操作中如果除数是2的幂次则等价于与其除数减一的与(&)操作(也就是说 hash%length==hash&(length-1)的前提是:length 是2的 n 次方),且采用二进制位操作 &,相对于%能够提高运算效率,这就解释了 HashMap 的长度为什么是2的幂次方。

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
HashMap源码学习笔记

最近忙于各种事情,只能陆陆续续也看了一些东西,Java的HashMap应该算比较基础的东西,也是最近在看<>,其中也有HashMap的数据结构,又回去看了一下Java本身实现,这篇也就再记录一下。 Java...

陶源0111
2018/08/18
0
0
HashMap源码学习笔记

最近忙于各种事情,只能陆陆续续也看了一些东西,Java的HashMap应该算比较基础的东西,也是最近在看<>,其中也有HashMap的数据结构,又回去看了一下Java本身实现,这篇也就再记录一下。 Java...

陶源
2018/08/18
0
0
关于Java两点需要更新的知识

关于Java两点需要更新的知识 HashMap的初始容量 背景 很多人可以把HashMap的原理描述的很溜。比如JDK1.7之前,底层数据结构是数组+链表。JDK1.8之后,出于效率上的考虑,在数组长度大于64,链...

优惠券活动
05/27
0
0
Java面试题---基础篇

经常阅读一些牛人的基础博以及相关个人经历,你才发现自己真的不够努力,人生路漫漫,希望本人以及看客能走出一条自己不后悔的人生路,骚年 加油!!! 回归正题 一 java基础知识点 1)java面向对象的...

osc_apej9ed1
2018/06/20
2
0
java集合最新面试总结

故不积跬步,无以至千里,千里之行始于足下。动起来童鞋们 (二)Java 中常见集合 集合这方面的考察相当多,这部分是面试中必考的知识点。 1)说说常见的集合有哪些吧? 答:Map 接口和 Coll...

osc_vsdge2u3
2019/03/11
1
0

没有更多内容

加载失败,请刷新页面

加载更多

macz技巧分享—macOS高端使用技巧

Macos 的占有量不如 Windows,两者之间当操作方式也有很大的不同,当很多人熱悉 Windows 的操作之后,再接触 macos,觉得难上手,其实是习惯问题。如果你学习一些技巧,会觉得 macos 其实也不...

mac小叮当
35分钟前
11
0
手把手教你如何用黑白显示器显示彩色!

来源:大数据文摘 本文约1000字,建议阅读6分钟。 本文为你介绍如何通过黑白显示器上也能显示出彩色。 原来在黑白显示器上也能显示出彩色啊!通过在监视器上覆盖拜耳滤色镜,并拼接彩色图像,...

osc_jklrr90y
35分钟前
18
0
key-value结构排序:给定一个字符串,统计每个字符出现频率,先按value降序,再按key升序

对于key-value结构的排序 第一种:lambda表达式 第二种:函数 第三种:类对()的重载,仿函数形式 #include <iostream>#include <vector>#include <unordered_map>#include <string>#in......

osc_gwtkg2dc
36分钟前
0
0
BlockChain:2020年7月10日世界人工智能大会WAIC《链智未来 赋能产业区块链主题论坛——2020全球区块链创新50强》

BlockChain:2020年7月10日世界人工智能大会WAIC《链智未来 赋能产业区块链主题论坛——2020全球区块链创新50强》 目录 世界人工智能大会WAIC《链智未来 赋能产业区块链主题论坛——2020全球...

osc_vew1u0h0
38分钟前
0
0
BlockChain:2020年7月10日世界人工智能大会WAIC《链智未来 赋能产业区块链主题论坛》(三)

BlockChain:2020年7月10日世界人工智能大会WAIC《链智未来 赋能产业区块链主题论坛》(三) 目录 2020年7月10日世界人工智能大会WAIC《链智未来 赋能产业区块链主题论坛》 演讲嘉宾 演讲内容 ...

osc_8o71811p
38分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部