HashMap负载因子为什么是0.75
待写
HashMap负载因子为什么是0.75?
HashMap有一个初始容量大小,默认是16
static final int DEAFULT_INITIAL_CAPACITY = 1 << 4; // aka 16
为了减少冲突概率,当HashMap的数组长度达到一个临界值就会触发扩容,把所有元素rehash再放回容器中,这是一个非常耗时的操作。
而这个临界值由负载因子和当前的容量大小来决定:
DEFAULT_INITIAL_CAPACITY*DEFAULT_LOAD_FACTOR
即默认情况下数组长度是16*0.75=12时,触发扩容操作。
所以使用hash容器时尽量预估自己的数据量来设置初始值。
那么,为什么负载因子要默认为0.75,在HashMap注释中有这么一段:
Ideally, under random hashCodes, the frequency of
* nodes in bins follows a Poisson distribution
* (http://en.wikipedia.org/wiki/Poisson_distribution) with a
* parameter of about 0.5 on average for the default resizing
* threshold of 0.75, although with a large variance because of
* resizing granularity. Ignoring variance, the expected
* occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
* factorial(k)). The first values are:
*
* 0: 0.60653066
* 1: 0.30326533
* 2: 0.07581633
* 3: 0.01263606
* 4: 0.00157952
* 5: 0.00015795
* 6: 0.00001316
* 7: 0.00000094
* 8: 0.00000006
* more: less than 1 in ten million
*
在理想情况下,使用随机哈希吗,节点出现的频率在hash桶中遵循泊松分布,同时给出了桶中元素的个数和概率的对照表。
从上表可以看出当桶中元素到达8个的时候,概率已经变得非常小,也就是说用0.75作为负载因子,每个碰撞位置的链表长度超过8个是几乎不可能的。
hash容器指定初始容量尽量为2的幂次方。
HashMap负载因子为0.75是空间和时间成本的一种折中。
泊松分布:https://blog.csdn.net/ccnt_2012/article/details/81114920
最新文章
- Android JavaMail
- MySQL的create table as 与 like区别
- VS2012 配置 OpenCV3.0
- j2ee log4j集中式日志解决方案logpool v0.3
- dede 调用四级导航
- 剑指Offer21 二叉树的层序遍历
- Extension Method[上篇]
- Musical Theme - poj 1743(求最大不重叠重复子串)
- React使用笔记1-React的JSX和Style
- Thinkphp常用标签
- emacs format
- 几种功能类似Linux命令汇总
- xml中CDATA包含问题
- 初学Python—列表和元组
- [Web 前端] 如何构建React+Mobx+Superagent的完整框架
- UVa 11636 你好 世界!(贪心)
- 如何分析Java虚拟机死锁
- SAP接口设计的扩展性考虑
- C# winform实现右下角弹出窗口结果的方法
- bzoj 2653 二分答案+可持久化线段树
热门文章
- Xcode 和 VisualC++输出流的差别的理解
- Python学习之路基础篇--01Python的基本常识
- s21day10 python笔记
- JS效果
- spring中使用@PostConstruct和@PreConstruct注解
- mysql插中文出现错误 ";incorrect string value:\x.....
- Windows下好用的git客户端--GitExtentions
- Linux(centos 7)配置tomcat8、JDK1.8、lighttpd、ngnix、mysql
- 初识TypeScript
- Kafka 如何读取offset topic内容 (__consumer_offsets)(转发)