首页 > 其他 > 详细

HashMap 数据结构分析

时间:2018-07-24 18:42:44      阅读:156      评论:0      收藏:0      [点我收藏+]
这篇文章主要说清楚HashMap底层数据结构,以及底层数组大小为什么是2的整数次幂。
注:该源码基于JDK8
 
1、HashMap 数据结构?
HashMap 底层数组结构刚开始是数组+链表实现,但是当链表上的节点多余一定值(8)的时候,将链表换成红黑树。
2、我们从 put(K key, V value) 源码角度来看数据结构
 
技术分享图片
 
 
技术分享图片
 
 
技术分享图片
 
解释:
hash:为插入元素的hashcode
n:为map的容量大小
&:与操作 比如 1101 & 1011=1001
如果n为2的次幂 则n-1 转化为二进制必定是...1111的形式,与hash的二进制与操作计算速度会非常快,而且空间不浪费;如果n不是2的次幂,比如n为15,则n-1为14,对应的二进制为1110,在和hash与操作,最后一位都为0,而0001,0011,0101,1001,1011,0111,1101 这几个位置永远都不能存放元素,不但浪费空间,而且数组可以使用的位置比数组长度小了很多,增加了碰撞的几率,减慢了查询的效率。
 
技术分享图片
 
 
 

HashMap 数据结构分析

原文:https://www.cnblogs.com/tspeking/p/9361789.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!