专栏首页码字搬砖解析 hashMap 源码之位运算

解析 hashMap 源码之位运算

计算索引

tab[i = (n - 1) & hash])

当 n == 2^x 的时候,(n - 1) & hash 与 hash % n 是等价的,但 (n - 1) & hash ( 位运算 )效率更高,因为 % 是通过 加法跟移位 来实现的

计算 hash 值

 // 扰动函数
    // 增加 hash 值的任意性,让高位参与到运算中来
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

让高位参与运算,增加 hash 值的随意性

计算 tableSize

/**
     * Returns a power of two size for the given target capacity.
     */
    // 大于等于 cap 的 最小的 2 的幂次方
    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

什么意思呢? 我们假设 cap 分别为 3,127,5,64,*

3    0000 0011
-1   0000 0010
>>>1 0000 0001 
|    0000 0011 
>>>2 0000 0000 
|    0000 0000 
....
结果不变 1

 127   0111 1111 
 -1    0111 1110 
 >>>1  0011 1111 
 |     0111 1111 
 >>>2  0001 1111 
 |     0111 1111 
 ....
 结果不变 128


 5    0000 0101
 -1   0000 0100 
 >>>1 0000 0010 
 |    0000 0110 
 >>>2 0000 0001 
 |    0000 0111 
 >>>3 0000 0000 
 |    0000 0111 
 ....
结果不变 8

//这就是为什么要减一 
64    0100 0000 
-1    0011 1110 
>>>1  0001 1111 
|     0011 1111 
>>>2  0000 1111 
|     0011 1111 
....
结果不变 64


更一般的
     01** ****
-1   01** ****

>>>1 001* ****
|    011* ****
>>>2 0001 1***
|    0111 1***
>>>4 0000 0111 
|    0111 1111 
....
结果不变
      0*** ****
-1    0*** ****
>>>1  00** ****    
|     0*** ****
>>>2  000* ****
|     0*** ****
....
结果不变

其实最终的结果就是返回

大于等于 cap 的 最小的 2 的幂次方 此处一定为 2 的幂次方,与 (n - 1) & hash 相呼应

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 解析 hashMap 源码之基本操作 get

    通过已经计算好的 hash 值,得到 table 的索引位置并来判断链表的第一个元素是不是要查找的节点,如果不是会查找树,最后会遍历链表

    shengjk1
  • Flink SQL 自定义 Sink

    内部要做 Flink SQL 平台,本文以自定义 Redis Sink 为例来说明 Flink SQL 如何自定义 Sink 以及自定义完了之后如何使用 基于...

    shengjk1
  • JVM内存模型之堆

    内容 作为我们程序员最关系的部分:堆,也是占用JVM内存最大的一块。主要用来存放对象实例、数组等,也是GC发生最多的地方。java堆可以处在物理上不连续的内...

    shengjk1
  • 【专知荟萃04】自动问答QA知识资料全集(入门/进阶/论文/代码/数据/综述/专家等)(附pdf下载)

    点击上方“专知”关注获取更多AI知识! 【导读】主题荟萃知识是专知的核心功能之一,为用户提供AI领域系统性的知识学习服务。主题荟萃为用户提供全网关于该主题的精华...

    WZEARW
  • gVim编辑器——基本设置、常用命令、代码片段

    gVim是一款强大的编辑器,可以满足大部分语言的编程需要。尤其是其自带的模板定制功能对于Verilog来说非常受用。然而gVim有很多操作是不同于其他编辑器的,...

    FPGA开源工作室
  • 员工考勤记录

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • 普通程序员,几个月如何成功转型AI?

    IT派 - {技术青年圈} 持续关注互联网、大数据、人工智能领域 动辄50万的毕业生年薪,动辄100万起步价的海归AI高级人才,普通员到底应不应该转型AI工程...

    IT派
  • 这三个普通程序员,几个月就成功转型AI,他们的经验是...

    动辄50万的毕业生年薪,动辄100万起步价的海归AI高级人才,普通员到底应不应该转型AI工程师,普通程序员到底应该如何转型AI工程师? 以下,AI科技大本营精选...

    AI科技大本营
  • 资源 |“从蒙圈到入坑”,推荐新一波ML、DL、RL以及数学基础等干货资源

    编译| AI科技大本营(rgznai100) 参与 | suiling 此前营长曾发过一篇高阅读量、高转发率,高收藏量的文章《爆款 | Medium上6900...

    AI科技大本营
  • day07(数据类型的相互转换 ,字符编

    py3study

扫码关注云+社区

领取腾讯云代金券