HashMap剖析之内部结构

时间: 2019-02-02阅读: 647标签: java

前言

本文是基于Java 8的HashMap进行分析,主要是介绍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链表(还是会比较key和hash)。

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

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



站长推荐

1.云服务推荐: 国内主流云服务商,各类云产品的最新活动,优惠券领取。地址:阿里云腾讯云华为云

2.广告联盟: 整理了目前主流的广告联盟平台,如果你有流量,可以作为参考选择适合你的平台点击进入

链接: http://www.fly63.com/article/detial/1967

关闭

lucene的suggest(搜索提示功能的实现)

首先引入依赖,既然要进行智能联想,那么我们需要为提供联想的数据建立一个联想索引(而不是使用原来的数据索引),既然要建立索引,那么我们需要知道建立索引的数据来源。我们使用一个扩展自InputIterator的类来定义数据来源

九大顶级 Java 框架

Java 创建于 1995 年,目前有 134861 个网站使用 Java,如 ESPN、SnapDeal、阿里巴巴等。在其 24 年的发展历程中,Java 已经证明了自己是用于自定义软件开发的顶级通用编程语言

优化 if-else 代码的八种方案

代码中如果if-else比较多,阅读起来比较困难,维护起来也比较困难,很容易出bug,接下来,本文将介绍优化if-else代码的八种方案。

JSP和JSF之间的区别是什么?

JSP和JSF这两种技术都基于Java,主要用于基于Web的应用程序。那么它们之间有什么区别?下面本篇文章就来给大家简单比较一下JSP和JSF,介绍JSP和JSF之间的区别有哪些,希望对大家有所帮助。

采用Java的ServerSocket进行编码一个简单的HTTP服务器

诸如tomcat等web服务器中间件简化了我们web的开发成本,但有时候我们或许并不需要这么一个完备的服务器,只是希望做一个简单地处理或者做特殊用途的服务器。

拦截器和过滤器的区别

拦截器功在对请求权限鉴定方面确实很有用处,在我所参与的这个项目之中,第三方的远程调用每个请求都需要参与鉴定,所以这样做非常方便,而且他是很独立的逻辑,这样做让业务逻辑代码很干净

JVM 发生 OOM 的 8 种原因、及解决办法

Java 堆空间:发生频率:5颗星造成原因1、无法在 Java 堆中分配对象 2、吞吐量增加 3、应用程序无意中保存了对象引用,对象无法被 GC 回收 4、应用程序过度使用 finalizer

泛型

泛型:软件工程中,我们不仅要创建一致的定义良好的API,同时也要考虑可重用性。 组件不仅能够支持当前的数据类型,同时也能支持未来的数据类型,这在创建大型系统时为你提供了十分灵活的功能。

select * from user 这条SQL语句,背后藏着哪些不可告人的秘密?

执行完这条语句后,我们就会得到 id 为 1 的用户信息。那么对于这一条 SQL 语句,MySQL服务器做了哪些处理呢?这篇文章我们就一起打卡 MySQL 数据库中对 SQL 语句的处理逻辑。

自定义HttpMessageConverter接受JSON数据

Spring默认使用Jackson处理json数据。实际开发中,在业界中,使用非常受欢迎的fastjson来接受json数据。创建一个项目,在web目录下新建一个assets/js目录,加入jquery和json2的js文件,在lib下加入fastjson的jar文件。

点击更多...

内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!