• 为什么 hashMap 中长度必须是 2 的 n 次方幂?


    底层计算数组 index 的算法(实际就相当于 hash % n 运算,但是 % 运算对于计算机来说效率低,如果不考虑性能采用 % 运算,就不用考虑是 2 的 n 次方幂):(n - 1) & hash = index ,n 表示数组的长度

    经过测试可以减少 hash 冲突,均匀分配数组空间。

    举个例子:

    hash:2     n:8(2的3次方)

    计算公式: hash&(n - 1)

    2 &(8-1)

    0000 0010 2

    0000 0111 7

    ——————————

    0000 0010 2 索引

    hash:3     n:8(2的3次方)

    计算公式: hash&(n - 1)

    3 &(8-1)

    0000 0011 3

    0000 0111 7

    ——————————

    0000 0011 3 索引

    最终计算出来的索引都是不一样的,减少了 hash 冲突,现在把 n 数组长度改成 9 (非 2 的 n 次方)

        

    hash:2     n:9(非2的3次方)

    计算公式: hash&(n - 1)

    2 &(9-1)

    0000 0010 2

    0000 1000 8

    ——————————

    0000 0000 0 索引

    hash:3     n:9(非2的3次方)

    计算公式: hash&(n - 1)

    3 &(9-1)

    0000 0011 3

    0000 1000 8

    ——————————

    0000 0000 0 索引

    最终计算出来的索引都是一样的,发生 hash 冲突,所以这个计算公式是经过人家试验过发生概率最低的计算公式,别人总结出来的经验。

  • 相关阅读:
    #力扣:125. 验证回文串@FDDLC
    Docker 网络管理及资源控制
    数据库 事务
    Python中的多媒体处理库有哪些?
    平安城市解决方案-最新全套文件
    详解pyautogui模块
    linux 主机通信 ipv6 配置
    Git分布式版本控制工具(一)
    linux杀死进程的五种方法(kill)
    【计算机网络】socket
  • 原文地址:https://blog.csdn.net/qq_35971258/article/details/126584686