程序锅

  • 首页
  • 分类
  • 标签
  • 归档
  • 关于

  • 搜索
基础知识 Etcd LeetCode 计算机体系结构 Kubernetes Containerd Docker 容器 云原生 Serverless 项目开发维护 ELF 深入理解程序 Tmux Vim Linux Kernel Linux numpy matplotlib 机器学习 MQTT 网络基础 Thrift RPC OS 操作系统 Clang 研途 数据结构和算法 Java 编程语言 Golang Python 个人网站搭建 Nginx 计算机通用技术 Git

Java HashMap 的那么多为什么

发表于 2020-07-09 | 分类于 Java | 0 | 阅读次数 2816
  1. HashMap 的默认大小是 16,这个默认值是可以设置的。如果事先知道具体的例子,可以修改默认初始大小,减少动态扩容的次数,提高性能。修改默认初始大小的值时,比如你设置了 500,那么不会真就使用 500 这个值,而可能会使用 512 这种是 2 的幂的值。

    为什么要设置是 2 的幂的值?这个跟下面的 index 的值计算有关,请看第 4 点。

  2. 最大的装载因子为 0.75,当装载因子超过这个值是就会扩容,每次扩容都会扩容为原来的两倍大小。

    那么为什么装载因子是 0.75 呢?经研究显示,负载因子是0.75的时候,空间利用率比较高,而且避免了相当多的 Hash 冲突,使得底层的链表或者是红黑树的高度比较低,提升了空间效率(来自网上)。

    为啥是扩容为原来的两倍呢?这个具体请看第 4 点。

  3. 采用链表法来解决冲突,之后再 JDK1.8 中引入了红黑数,主要链表长度太长(默认超过8)时,链表就转换为红黑树。当少于 6 时,又将红黑树转换为链表,因为红黑树要维护平衡,比起链表性能上的优势并不会特别明显。

    那么为什么在少于 6 的时候而不是 8 的时候才将红黑树转换为链表呢?假设设计成大于 8 时链表转换为红黑树,小于 8 的时候又转换为链表。如果一个 hashmap 不停的插入、删除。hashmap 中的个数不停地在 8 徘徊,那么就会频繁的发生链表和红黑树之间转换,效率非常低。因此,6 和 8 之间来一个过渡值可以减缓这种情况造成的影响。

  4. 散列值的获取分两步走:

    // 1. hash 值的计算
    static final int hash(Object key) {
        int hash;
        return key == null ? 0 : (hash = key.hashCode()) ^ hash >>> 16;
    }
    
    // 2. 插入/查找的时候,计算 key 应该被映射到散列表的什么位置
    int index = hash(key) & (capacity - 1)
    

    其中方法 hashcode() 返回的是 Java 对象的 hash_code,这是一个 int 类型的值(32 位)。那么为什么在拿到这个值之后,还需要将自己右移 16 位与自己进行异或呢?因为容量较小的时候,在计算 index 那边,真正用到的其实就只有低几位,假如不融合高低位,那么假设 hashcode() 返回的值都是高位的变动的话,那么很容易造成散列的值都是同一个。但是,假如将高位和低位融合之后,高位的数据变动会最终影响到 index 的变换,所以依然可以保持散列的随机性。

    那么在计算 index 的时候,为什么不使用 hash(key) % capacity 呢?这是因为移位运算相比取余运算会更快。那么为什么 hash(key) & (capacity - 1) 也可以呢?这是因为在 B 是 2 的幂情况下: A % B = A & (B - 1)。如果 A 和 B 进行取余,其实相当于把 A 那些不能被 B 整除的部分保留下来。从二进制的方式来看,其实就是把 A 的低位给保留了下来。B-1 相当于一个“低位掩码”,而与的操作结果就是散列值的高位全部置为 0 ,只保留低位,而低位正好是取余之后的值。我们取个例子,A = 24,B =16,那么 A%B=8,从二进制角度来看 A =11000 ,B = 10000。A 中不能被 B 整除的部分其实就是 1000 这个部分。接下去,我们需要将这部分保留下来的话,其实就是使用 01111 这个掩码并跟 A 进行与操作,即可将1000 保留下来,作为 index 的值。而 01111 这个值又等于 B-1。所以 A &(B-1)= A%B。但是这个前提是 B 的容量是 2 的幂,那么如何保证呢?我们可以看到,在设置初始大小的时候,无论你设置了多少,都会被转换为 2 的幂的一个数。之外,扩容的时候也是按照 2 倍进行扩容的。所以 B 的值是 2 的幂是没问题的。

卷死我
dawnguo 微信支付

微信支付

dawnguo 支付宝

支付宝

  • 本文作者: dawnguo
  • 本文链接: /archives/28
  • 版权声明: 本博客所有文章除特别声明外,均采用CC BY-NC-SA 3.0 许可协议。转载请注明出处!
# 编程语言 # Java # 数据结构和算法
Kubernetes | Pod 的使用
数据结构和算法 | 哈希算法的设计要点、应用场景【高阶】
  • 文章目录
  • 站点概览
dawnguo

dawnguo

215 日志
24 分类
37 标签
RSS
Creative Commons
© 2018 — 2025 程序锅
0%