此题可以组成如下连环炮来问
你看过HashMap源码嘛,知道原理嘛?
<李>为什么用数组+链表?
<李>哈希冲突你还知道哪些解决办法?
<李>我用LinkedList代替数组结构可以么?
<李>既然是可以的,为什么HashMap不用LinkedList,而选用数组吗?
针对这个问题,嗯,当然是必须看过HashMap源码。至于原理,下面那张图很清楚了:
HashMap采用条目数组来存储键-值对,每一个键值对组成了一个条目实体,条目类实际上是一个单向的链表结构,它具有一指针,可以连接下一个条目实体。
只是在JDK1.8中,链表长度大于8的时候,链表会转成红黑树!
数组是用来确定桶的位置,利用元素的关键的散列值对数组长度取模得到。
链表是用来解决哈希冲突问题,当出现哈希值一样的情形,就在数组上的对应位置形成一条链表每分钟:这里的散列值并不是指hashcode,而是将hashcode高低十六位异或过的。至于为什么要这么做,继续往下看。
比较出名的有四种:(1)开放定址法(2)链地址法(3)再哈希法(4)公共溢出区域法
ps:大家有兴趣拓展的,自己去搜一下就懂了,这个就不拓展了!
这里我稍微说明一下,此题的意思是,源码中是这样的
ps:条目就是一个链表节点。
那我用下面这样表示
是否可行吗?
答案很明显,必须是可以的。
因为用数组效率最高!
在HashMap中,定位桶的位置是利用元素的关键的哈希值对数组长度取模得到。此时,我们已得到桶的位置。显然数组的查找效率比大LinkedList。
(烟哥写到这里的时候,不禁觉得自己真有想法,自己把自己问死了,还好我灵机一动想出了答案)
因为采用基本数组结构,扩容机制可以自己定义,HashMap中数组扩容刚好是2的次幂,在做取模运算的效率高。
而ArrayList的扩容机制是1.5倍扩容,那ArrayList为什么是1.5倍扩容这就不在本文说明了。
二、HashMap在什么条件下扩容吗?
此题可以组成如下连环炮来问
HashMap在什么条件下扩容?
<李>为什么扩容是2的n次幂吗?
<李>为什么为什么要先高16位异或低16位再取模运算吗?
如果桶满了(超过负荷系数*电流容量),就要调整。
负荷系数为0.75,为了最大程度避免哈希冲突
电流容量为当前数组大小。
HashMap为了存取高效,要尽量较少碰撞,就是要尽量把数据分配均匀,每个链表长度大致相同,这个实现就在把数据存到哪个链表中的算法;这个算法实际就是取模,哈希%长度。
但是,大家都知道这种运算不如位移运算快。
因此,源码中做了优化hash&(长度为1)。
也就是说哈希%==hash&长度;(长度是1)
那为什么是2的n次方呢?
因为2的n次方实际就是1后面n个0,2的n次方1,实际就是n个1。
例如长度为8时候,3,(8 - 1)=3 2,(8 - 1)=2,不同位置上,不碰撞。
而长度为5的时候,3和2(5 - 1)=0,(5 - 1)=0,都在0上,出现碰撞了。
所以,保证容积是2的n次方,是为了保证在做(长度为1)的时候,每一位都能,1,也就是和1111年……1111111进行与运算。
我先晒一下,jdk1.8里的散列方法.1.7的比较复杂,咱就不看了。
HashMap这么做,只是为了降低哈希冲突的几率。
打个比方,当我们的长度为16的时候,哈希码(字符串“abcabcabcabcabc”的关键对应的哈希码)对(16:1)与操作,对于多个关键生成的hashCode,只要哈希码的后4位为0,不论不论高位怎么变化,最终的结果均为0。
如下图所示
而加上高16位异或低16位的“扰动函数”后,结果如下
