HashMap剖析之内部结构

前言

本文是基于 Java 8HashMap 进行分析,主要是介绍 HashMap 中的成员变量和类变量的用途,以及分析 HashMap数据结构。

变量分析

HashMap 中存在多个成员变量和类变量,搞清楚它们的用途有助于我们更深入了解 HashMap ,下面是它们的介绍:

/**
     * 默认的初始容量,必须为2的次幂
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 总所周知是16

    /**
     * 最大容量
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * 默认的负载因子
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /**
     * 将链表转化为红黑树的阈值,当链表节点数大于或等于该阈值-1则转化为红黑树
     */
    static final int TREEIFY_THRESHOLD = 8;

    /**
     * 将红黑树转化为链表的阈值,当红黑树的节点小于该阈值时转化为链表
     */
    static final int UNTREEIFY_THRESHOLD = 6;

    /**
     * 允许进行链表转化为红黑树的阈值,只有散列表大小大于或等于该值才能进行红黑树转化
     */
    static final int MIN_TREEIFY_CAPACITY = 64;
    /**
     * HashMap中存储数据的数组,也称为散列表。
     * 建议保持长度为2的次幂
     */
    transient Node<K,V>[] table;

    /**
     * 缓存entrySet()方法的值
     */
    transient Set<Map.Entry<K,V>> entrySet;

    /**
     * Map中键值对的个数
     */
    transient int size;

    /**
     * HashMap数据结构被改变的次数,一般是指散列表的长度改变、Node链表增加或者减少节点
     * 这个参数是用于快速失败机制
     */
    transient int modCount;

    /**
     * 下一次触发调整大小(resize()方法)的阈值,一般为容量乘以负载因子 
     */
    int threshold;

    /**
     * 散列表的负载因子,用于计算扩容的阈值
     */
    final float loadFactor;

数据结构

HashMap 使用 拉链法 解决哈希表中存在的 哈希冲突 问题,所以 HashMap 底层是用以 Node 组成的 链表 为元素的 数组 table 来存储键值对,每个 Node 就是一个键值对对象。 table 称呼为散列表。

table 对应的是 散列表 ,是因为无论是存储还是读取键值对的时候,都会对 key 进行 hash%table.length 运算来进行散列表的命中,然后操作命中的索引对应的 Node 链表(还是会比较 keyhash )。

以上为 Java 8 之前版本的 HashMap 的实现,而 Java 8 进行了优化:就是当链表节点数超过阈值 TREEIFY_THRESHOLD(8) 时,则会将 链表 转化为 红黑树

如果只是使用文字描述的话会很难理解,所以下面会通过一幅图展示:

HashMap剖析之内部结构

原文 

https://segmentfault.com/a/1190000018121296

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » HashMap剖析之内部结构

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址