文档章节

hashMap为啥初始化容量为2的次幂

小树鹿鸣
 小树鹿鸣
发布于 2017/03/15 00:25
字数 265
阅读 58
收藏 0

hashMap源码获取元素的位置:

static int indexFor(int h, int length) {
    // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
    return h & (length-1);
}

解释:

h:为插入元素的hashcode length:为map的容量大小 &:与操作 比如 1101 & 1011=1001

这里是列表文本如果length为2的次幂 则length-1 转化为二进制必定是11111……的形式,在于h的二进制与操作效率会非常的快,而且空间不浪费;

这里是列表文本如果length不是2的次幂,比如length为15,则length-1为14,对应的二进制为1110,在于h与操作,最后一位都为0,而0001,0011,0101,1001,1011,0111,1101这几个位置永远都不能存放元素了,空间浪费相当大;

更糟的是这种情况中,数组可以使用的位置比数组长度小了很多,这意味着进一步增加了碰撞的几率,减慢了查询的效率!这样就会造成空间的浪费

本文转载自:

小树鹿鸣
粉丝 7
博文 4
码字总数 163
作品 0
福州
高级程序员
私信 提问
Java集合类之HashMap源码学习笔记

数组虽然可以随机访问,但插入和删除效率较低,链表虽然插入和删除效率较高,查找却只能通过遍历,而HashMap则基于数组加链表,完美结合了二者的优点,查找,更新,插入,删除几乎都可以达到O...

单线程程序员
2018/12/07
0
0
Java基础之HashTable与ConcurrentHashMap解析

HashTable和HashMap的区别 在面试的过程中,经常会被问到HashTable和HashMap的区别,下面就这些区别做一个简单的总结。 1、继承的父类不同 Hashtable继承自Dictionary类,而HashMap继承自Abs...

code_xzh
2018/05/30
0
0
HashMap源码详细分析

写在最前 分析基于JDK1.7 1. 基础 默认大小为16 默认加载因子为0.75 用Entry数组实现,Entry有key, value, next, hash三个字段。 HashMap的equals比较的都是key和value的equals方法 最大容量...

大道至简_Andy
2017/12/19
0
0
jdk1.6集合源码阅读之HashMap

本来ArrayList和LinkedList弄完,应该去查看set接口的一些实现了,比如HashSet和TreeSet的实现了,但是看了下HashSet的底层存储是HashMap,所以决定先看HashMap的源码,看完再看HashSet的源码...

双月通天
2016/08/26
30
0
Map大家族的那点事儿(4) :HashMap – 动态扩容与添加元素

原文出处:SylvanasSun's Blog 动态扩容 散列表以数组的形式组织bucket,问题在于数组是静态分配的,为了保证查找的性能,需要在Entry数量大于一个临界值时进行扩容,否则就算散列函数的效果...

SylvanasSun's Blog
2018/09/08
0
0

没有更多内容

加载失败,请刷新页面

加载更多

JS实现使用Math.random()函数生成n到m间的随机数字

Math.random()函数返回0和1之间的伪随机数,可能为0,但总是小于1,[0,1) 生成n-m,包含n但不包含m的整数: 第一步算出 m-n的值,假设等于w 第二步Math.random()*w 第三步Math.random()*w+n...

张兴华ZHero
20分钟前
3
0
入门了解Service Mesh + Istio?从本文开始

下周六,深圳,阔别已久的线下技术沙龙要和你见面啦! 现场有Rancher Labs研发经理demo刚刚发布的Rancher 2.3中的Istio、Windows容器、集群模板等功能及使用,还有k3s首次线下workshop,由R...

RancherLabs
22分钟前
3
0
Gradle 发布 Jar 到 Archiva 时提示不能 Overwriting released artifacts is not allowed

系统提示错误信息: Received status code 409 from server: Overwriting released artifacts is not allowed. 这是在 Archiva 默认的配置下如果你不是使用 snapshot 配置的话,是不允许对仓...

honeymoose
23分钟前
3
0
二维码插件之qrcode.min.js

文件链接百度云地址 https://pan.baidu.com/s/1nWiBuT4Z7WOAMoUEFL8PZg 入门 http://www.jq22.com/jquery-info294 使用jquery.qrcode.min.js实现前台二维码生成(带Logo) https://blog.csd......

木九天
33分钟前
3
0
开源 java CMS - FreeCMS2.8 自定义标签 commentPage

项目地址:http://www.freeteam.cn/ commentPage 根据参数提取评论对象。 参数 说明 siteid 站点id objtype 评论对象类型 objid 评论对象id membername 会员名称 isanonymous 是否匿名 1是 ...

freeteam
33分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部