李泽涛。

V1

2022/03/23阅读:53主题:极客黑

HashMap学习个人笔记

HashMap学习笔记

HashMap问题详解

HashMap初始化的时候为啥要指定大小

  • 初始化HashMap指定大小
Map<String, String> logMap = new HashMap<>(8);

  • 第一点 阿里Java开发手册(嵩山版)中建议我们初始化的时候指定大小,如果无法确认集合大小,指定默认值(16)即可。(这算一个开发规范)
  • 第二点 可以减少扩容,扩容意味着重建hash表(耗时)
  • 第三点 初始化大小计算公式
    • initialCapacity = (需要存储的元素个数/负载因子)+1
    • 负载因子默认为0.75f

[1]

为什么HashMap初始化的时候尽量取2的幂次方?

  • 标准说法:h & (length-1),长度length为2的整数次幂可以保证散列的均匀,提升效率;
  • 说实话,我看的一头雾水,然后我就开始分析。
    • h代表的是hash算法,也就是经过hash(散列)算法的运行,得到一个固定长度的输出,也就是散列值。(通俗点说,就是经过一系列算法得到一个值)
    • length 就是长度的意思
    • 假设我们长度设置为15,hash为8
      • 15-1=14 二进制就是1110
      • 8 二进制就是1000 做位运算与 都为1时才等于1
      • 1000&1110 = 1000 假设hash为9 二进制 1001
      • 1001&1110 = 1000
    • 假设我们长度设置为16,hash为8
      • 16-1 = 15 二进制就是1111
      • 8 二进制就是1000 做位运算与 都为1时才等于1
      • 1000&1111 = 1000 假设hash为9 二进制 1001
      • 1001&1111 = 1001
    • 不知道发现没有,当长度为奇数时,length-1一定是偶数,换算成二进制最后一位为0,按照位运算与&计算,最后一位永远不可能为1。
    • 这样最后一位永远不可能为1,会导致什么,会导致如果你是一个数组,你的下标只能是偶数,没有奇数,就是你的数组长度有8个,你只能放4个,另外4个怎么也放不了,造成了很大的浪费。 [2]

HashMap存储的结构是什么

  • 在jdk1.7的版本里使用的是数组+链表的数据结构
  • 在jdk1.8的版本里使用的是数组+链表+红黑树的数据结构

put的实现原理

  • 首先将<k,v>封装到Node对象当中
  • 然后它的底层会调用k的hashCode方法算出hash值
  • 通过哈希表函数/哈希算法,将hash值转换成数组的下标,下标位置上如果没有任何元素,则把Node对象添加到这个位置上。如果下标位置有链表,此时,我们就会拿着k跟链表上每个节点的k进行equals对比,如果对比都返回false,那么这个新节点将被添加到链表的尾部(如果是jdk1.7则会添加到链表头部),如果有个节点equals返回true,那么这个节点的value将被覆盖。

get的实现原理

  • 先调用k的hashCode方法算出hash值,再根据哈希算法转换成数组的下标。
  • 拿到下标以后,快速的定位到位置上,如果这个位置上什么都没有,返回null,如果这个位置上有单向链表,那么拿着k和链表上每个节点的k进行equals对比,如果都返回false,则返回null,否则有个节点对比返回true,则返回该个节点的value。 [3]

参考资料

[1]

ps: 建议initialCapacity尽量取2的幂次方,虽然不取2的幂次方效果也一致,initialCapacity=5和initialCapacity=8的效果是一样的,但建议使用initialCapacity=8。

[2]

ps: 按位与运算符(&)两个位都为1时才为1。

[3]

ps: 关注公众号【楼梯间的男孩】,我们一起学习,努力变为地中海。。

分类:

后端

标签:

Java

作者介绍

李泽涛。
V1