HashMap剖析之内部结构

arashicage 发布于2019-08-19 11:33 / 1170人阅读

摘要：前言本文是基于的进行分析，主要是介绍中的成员变量和类变量的用途，以及分析的数据结构。以上为之前版本的的实现，而进行了优化就是当链表节点数超过阈值时，则会将链表转化为红黑树。

前言

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

变量分析

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

    /**
     * 默认的初始容量，值为2的4次方
     */
    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的N次幂
     */
    transient Node[] table;

    /**
     * 缓存entrySet()方法的值
     */
    transient Set> entrySet;

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

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

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

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

数据结构

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

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

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

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

GPU云服务器云服务器 java数据结构剖析 hashmap存储结构内部结构电脑主机内部结构

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/77435.html

Java面试重难点剖析

摘要：高并发访问数据库优化方法方法总结执行的过程简单理解及的区别之区别详解备忘笔记线程本地存储的原理和实现分类和原理系列三参数设置分析虚拟内存机制搜索算法集锦关于树的一些总结中种数据结构的使用场景介绍如何解决包冲突问题中如何将所有引用的包打包到 1、高并发访问数据库优化方法 2、 java finalize方法总结、GC执行finalize的过程 3、简单理解Socket及TCP/IP、Ht...

sushi 2019-08-20 15:43 评论0 收藏0
Java面试重难点剖析

摘要：高并发访问数据库优化方法方法总结执行的过程简单理解及的区别之区别详解备忘笔记线程本地存储的原理和实现分类和原理系列三参数设置分析虚拟内存机制搜索算法集锦关于树的一些总结中种数据结构的使用场景介绍如何解决包冲突问题中如何将所有引用的包打包到 1、高并发访问数据库优化方法 2、 java finalize方法总结、GC执行finalize的过程 3、简单理解Socket及TCP/IP、Ht...

longmon 2019-08-14 18:06 评论0 收藏0
LinkedHashMap就这么简单【源码剖析】

摘要：习惯在微信看技术文章，想要获取更多的资源的同学，可以关注微信公众号。为了大家方便，刚新建了一下群，大家也可以去交流交流。谢谢支持了希望能多介绍给其他有需要的朋友前言声明，本文用得是jdk1.8 前面已经讲了Collection的总览和剖析List集合以及散列表、Map集合、红黑树还有HashMap基础了： Collection总览 List集合就这么简单【源码剖析】 Map集合、...

avwu 2019-08-15 15:23 评论0 收藏0
HashMap就是这么简单【源码剖析】

前言声明，本文用得是jdk1.8 前面已经讲了Collection的总览和剖析List集合以及散列表、Map集合、红黑树的基础了： Collection总览 List集合就这么简单【源码剖析】 Map集合、散列表、红黑树介绍本篇主要讲解HashMap，以及涉及到一些与hashtable的比较~ 看这篇文章之前最好是有点数据结构的基础： Java实现单向链表栈和队列就是这么简单二叉树就...

entner 2019-08-15 15:21 评论0 收藏0
Java面试通关要点汇总集

摘要：本文会以引出问题为主，后面有时间的话，笔者陆续会抽些重要的知识点进行详细的剖析与解答。敬请关注服务端思维微信公众号，获取最新文章。原文地址：梁桂钊的博客博客地址：http://blog.720ui.com 这里，笔者结合自己过往的面试经验，整理了一些核心的知识清单，帮助读者更好地回顾与复习 Java 服务端核心技术。本文会以引出问题为主，后面有时间的话，笔者陆续会抽些重要的知识点进...

gougoujiang 2019-08-15 14:26 评论0 收藏0