HashMap源码分析（一）

存储结构

说明：本次讲解的HashMap是jdk1.8中的实现，其他版本可能有差异

内部是由Node节点数组组成，Node节点之间又由链表或红黑树组成。

图是网上找的，实在不想画

image.png

属性介绍

    //存储数据的数组，初次使用时初始化，分配的长度总是2的冥次方
    transient Node<K,V>[] table;

    /**
     * Holds cached entrySet(). Note that AbstractMap fields are used
     * for keySet() and values().
     */
    transient Set<Map.Entry<K,V>> entrySet;

    //容器中包含的所有元素数量
    transient int size;

	//代指HashMap结构被修改的次数，结构修改是指更改HashMap中映射的数量或以其他方式修改其内部结构的修改 
    transient int modCount;

    //下一次扩容的大小值 (capacity * load factor)
    int threshold;

    //扩容系数
    final float loadFactor;

构造方法

HashMap有4个构建方法，主要作用就是初始化存储数组容量、扩容系数、下一次触发扩容大小

public HashMap(int initialCapacity, float loadFactor) {
    	//初始容量，不能小于0，否则抛非法参数异常
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
    	//容器超限了，则默认设置为最大值，2^30次方
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
    	//扩容系数设置不对，也会抛出异常
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor; //设置扩容系数
        //根据设置的初始数组大小计算下次触发扩容时的大小，初始情况下threshold也表示数组的初始大小，这个可以通过resize()方法中看到
        this.threshold = tableSizeFor(initialCapacity);  
    }

    public HashMap(int initialCapacity) {
        //调用第一个构造方法，loadFactor默认0.75
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    public HashMap() {
        //只设置loadFactor，默认0.75，其他字段都默认值
        this.loadFactor = DEFAULT_LOAD_FACTOR; 
    }

    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false); //创建新的hashmap，并把原来的m内容填充进去
    }

散列算法

static final int hash(Object key) {
    int h;
    //h >>> 16 hash值右移16位，实际上就是将高16位通过右移到低16位，然后通过与原hash值异或处理，使高16位也参与到索引数组位置的计算当中，这样做的好处是为了同时保留高16位于低16位的特征，让哈希后的结果更均匀的分布，减少hash冲突，提升hashmap的运行效率。
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

HashMap是根据hash值，通过以下方式计算存储的位置：(数组长度 - 1) & (h ^ (h >>> 16))

(n-1) & hash判断元素存放的位置，n等于数组的长度，与运算相当于取余运算(计算效率较取余运算更高)。假如不做 (h >>> 16) 右移运算，那么hash仅是最后四位和1111运算(假如数组长度为16)那么hash高位的信息就会全部丢失（比如，多个key的hashcode最后四位都是0000那么就会全部存储在索引为0的桶中产生冲突），如果右移16位就会将高位的信息与低位的16位异或运算，保留了高位与低位的特征更能体现key的hashcode的特征，降低冲突的概率。

put方法

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

/**
     * Implements Map.put and related methods.
     *
     * @param hash key的hash值
     * @param key the key
     * @param value 要存放的value
     * @param onlyIfAbsent如果为true，那么容器中如果存在就不改变已存在的值；否则替换
     * @param evict 意为逐出，在LinkedHashMap中有用，可以想像成LRU算法中对过期数据的删除
     * @return previous value, or null if none
     */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //初次进来table为空
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length; //通过resize()方法初始化table数组，并得到数组长度
    //(n - 1) & hash  根据hash取模求出在数组中的位置，并判断该位置是否已经有值，当前判断是无值状态
    if ((p = tab[i = (n - 1) & hash]) == null)
        //该索引位置没有值，那么创建新node，并赋值在该索引位置上
        tab[i] = newNode(hash, key, value, null);
    else {
        //走到这里，证明当前索引位置已经有冲突了
        Node<K,V> e; K k;
        //如果hash和key的值同时相等，那么就认为是同一个值，直接覆盖原来索引位置下的节点（value值的覆盖取决于onlyIfAbsent或者原node的value是Null）
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            //走到这里，证明冲突的节点不是完全相同的，并且原节点已经是（红黑）树化的节点了，那新节点肯定也应该是TreeNode
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            //不是树，那就是链表，接下来执行链表的操作
            for (int binCount = 0; ; ++binCount) {
                //从链表头部开始遍历，一直到尾部，将新的node直接插入到尾部
                if ((e = p.next) == null) {
                    //尾部插入
                    p.next = newNode(hash, key, value, null);
                    //判断链表节点数是否大于等于TREEIFY_THRESHOLD（默认8），这里-1的原因，就是没算进新创建的节点，超过了，那么要（红黑）树化
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        //链表转红黑树，转换条件：1.链表节点数大于8；2.数组长度大于MIN_TREEIFY_CAPACITY（默认64）
                        treeifyBin(tab, hash); 
                    break;
                }
                //遍历链表的同时，判断有没有节点完全相同的，有的话，直接退出遍历
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // 存在相同的key
            V oldValue = e.value;
            //根据onlyIfAbsent的条件，判断是否覆盖原节点的值
            if (!onlyIfAbsent || oldValue == null)
                e.value = value; //覆盖原值
            afterNodeAccess(e); //这也是个钩子方法，hashmap中没有实现
            return oldValue; //返回原值
        }
    }
    //修改次数加1
    ++modCount;
    //size加1，并判断是否超过扩容触发条件，超过后重新扩容
    if (++size > threshold)
        resize(); //扩容
    //这是一个钩子方法，留待子类实现，比如在LinkedHashMap中就有使用
    afterNodeInsertion(evict);
    return null;
}
//树化方法
final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        //数组长度不足MIN_TREEIFY_CAPACITY（64）则不树化，只做扩容，避免数组节点都挤压（冲突）
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            TreeNode<K,V> hd = null, tl = null;
            do {
                TreeNode<K,V> p = replacementTreeNode(e, null);
                if (tl == null)
                    hd = p;
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }

get方法

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

/**
     * Implements Map.get and related methods.
     *
     * @param hash hash for key
     * @param key the key
     * @return the node, or null if none
     */
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    //判断数组不为空
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        //hash计算得到数组索引位置对应的节点，判断当前节点是否与要获取的hash和key一致，是的话，直接返回，不是继续往下走
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            //找到下一个节点，这里要说明一下，即使节点树化后，依然会维持原有的链表状态
            if (first instanceof TreeNode)
                //从红黑树中取出节点
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                //遍历链表取出节点
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

remove方法

public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

   	/**
     * Implements Map.remove and related methods.
     *
     * @param hash hash for key
     * @param key the key
     * @param value the value to match if matchValue, else ignored
     * @param matchValue if true only remove if value is equal
     * @param movable if false do not move other nodes while removing
     * @return the node, or null if none
     */
final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    //判断数组不为空
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        //hash计算得到数组索引位置对应的节点，判断当前节点是否与要获取的hash和key一致，是的话，不用找了，已经找到了，并把node设置为当前找到的p，不是的话则继续往下走
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        else if ((e = p.next) != null) {
            //找到下一个节点，这里要说明一下，即使节点树化后，依然会维持原有的链表状态
            if (p instanceof TreeNode)
                //从红黑树中取出节点
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                 //遍历链表取出节点
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            if (node instanceof TreeNode)
                //红黑树节点，从树中删除，removeTreeNode方法针对节点数较少的情况，又会转会链表
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)
                //链表中第一个节点，直接移除，用next节点来填充
                tab[index] = node.next;
            else
                p.next = node.next; //找到的中间节点，则直接断链就行
            ++modCount; //增加修改次数
            --size; //大小减1
            afterNodeRemoval(node); //钩子方法
            return node;
        }
    }
    return null;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/124720.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

CocosCreator让一个物体跟随鼠标移动（两种方式 本地坐标系和世界坐标系）

CocosCreator让一个物体跟随鼠标移动（两种方式 本地坐标系和世界坐标系）

在 Cocos Creator 3.x 游戏运行时显示的画布大小就是屏幕区域&#xff0c;屏幕坐标是从画布的左下角为原点开始计算 在 Creator 3.x 里&#xff0c;屏幕和 UI 是完全区分开的&#xff0c;用户可以在没有 UI 的情况下点击屏幕获取触点信息。因此&#xff0c;获取屏幕触点&#…
阅读更多...
mac M2 anaconda 解决装不了python3.7

mac M2 anaconda 解决装不了python3.7

今天发现一个很奇怪的问题 但是我一换成 conda create -n DCA python3.8.12就是成功的 这个就很奇怪, 解决如下 https://towardsdatascience.com/how-to-manage-conda-environments-on-an-apple-silicon-m1-mac-1e29cb3bad12 998 conda search pythonconda search python …
阅读更多...
半导体（芯片）制造工艺流程简单说

半导体（芯片）制造工艺流程简单说

半导体行业是国民经济支柱性行业之一&#xff0c;是信息技术产业的重要组成部分&#xff0c;是支撑经济社会发展和保障国家安全的战略性、基础性和先导性产业&#xff0c;其发展程度是衡量一个国家科技发展水平的核心指标之一&#xff0c;属于国家高度重视和鼓励发展的行业。 …
阅读更多...
ant design pro of vue怎么使用阿里iconfont

ant design pro of vue怎么使用阿里iconfont

一 使用离线iconfont 首先需要生成图所有图标对应的js文件。如下图所示&#xff0c;将生成的js代码复制&#xff0c;在项目中创建一个js文件&#xff0c;将代码粘贴进去。这里我将js文件放在了src/assets/iconfont下面 然后&#xff0c;在main.js中引入文件&#xff0c;并进…
阅读更多...
Java代码是怎么运行的？

Java代码是怎么运行的？

Java代码是怎么运行的&#xff1f; 运行流程 将Java程序转换成Java虚拟机所能识别的指令序列&#xff0c;也称Java字节码。之所以这么取名&#xff0c;是因为Java字节码指令的操作码&#xff08;opcode&#xff09;被固定为一个字节。 Java虚拟机可以由硬件实现&#xff0c;…
阅读更多...
IP协议相关技术

IP协议相关技术

文章目录 IP协议相关技术仅凭IP无法完成通信DNSARP IP协议相关技术 仅凭IP无法完成通信 人们在上网的时候其实很少直接输入某个具体的IP地址。 在访问Web站点和发送、接收电子邮件时&#xff0c;我们通常会直接输入Web网站的地址或电子邮件地址等那些由应用层提供的地址&…
阅读更多...
麒麟v10 安装jenkins

麒麟v10 安装jenkins

1.想安装哪个版本&#xff1f; https://pkg.jenkins.io/redhat-stable/ 我们查看我们想要哪个版本&#xff1a; 4年前安装的是 Jenkins2.279 版本 现在在docker 上安装的是Version 2.425 版本 2.碰到到的问题 1.安装老版本的Jenkins&#xff0c;会出现安装的插件不兼容&…
阅读更多...
viple入门（四）

viple入门（四）

&#xff08;1&#xff09;行打印 主要用于在运行窗口中显示数据&#xff0c;打印完成后&#xff0c;自动换行。 注意事项&#xff1a;不可同时打印两个数据&#xff0c;例如 解决方案1&#xff1a;使用或并&#xff0c;使得每次进入行打印的数据只有一个&#xff0c;缺点&am…
阅读更多...
文件管理技巧：如何利用文件名关键字进行整理

文件管理技巧：如何利用文件名关键字进行整理

在日常生活和工作中&#xff0c;我们经常需要处理大量的文件&#xff0c;这些文件可能包含各种类型的信息&#xff0c;如文本、图像、视频、音频等。如何有效地管理和整理这些文件&#xff0c;以便我们能够快速找到所需的文件&#xff0c;是一个非常重要的问题。本文将介绍一种…
阅读更多...
Linux shell编程学习笔记22： () $() (()) 的用法小结

Linux shell编程学习笔记22： () $() (()) 的用法小结

最近学习Linux Shell编程&#xff0c;对 () (()) [] [[]]等符号的用法还是有点分不太清楚&#xff0c;于是决定再梳理一下。今天先整理 () $() (()) 的用法。 1 单小括号() 1.1 子shell&#xff08;命令组&#xff09; 括号中的命令将会新开一个子shell顺序执行&#xff0c;所…
阅读更多...
用vite搭建一个vue3 + ts项目

用vite搭建一个vue3 + ts项目

搭建项目 参考连接https://www.jianshu.com/p/1ce93c7e15a0 练手项目参考 https://www.xuexiluxian.cn/ 1.安装pina vue3 pinia的安装和使用 2.安装router npm install vue-router -S Vue3: Vue-router路由的使用
阅读更多...
什么是跨境电商独立站？有什么优势和劣势？

什么是跨境电商独立站？有什么优势和劣势？

你是否有过这样的经历&#xff1a;当你在网上浏览一些商品时&#xff0c;发现有些网站的域名很奇怪&#xff0c;比如.com、.net、.co等&#xff0c;而且网站的界面和设计也和国内的电商平台不太一样。 你可能会好奇&#xff0c;这些网站是什么&#xff1f;它们是怎么做的&…
阅读更多...
学习笔记|Pearson皮尔逊相关系数|Spearman斯皮尔曼相关系数|和Kendall肯德尔tau-b相关系数|分析流程|-SPSS中双变量相关性分析系数

学习笔记|Pearson皮尔逊相关系数|Spearman斯皮尔曼相关系数|和Kendall肯德尔tau-b相关系数|分析流程|-SPSS中双变量相关性分析系数

目录 学习目的软件版本原始文档基础概念皮尔逊相关系数基本假设&#xff08;适用条件&#xff09;&#xff1a;系数的范围及意义实例1. 读数据&#xff1a;2.正态性检验&#xff1a;3.异常值检验&#xff08;体重&#xff09;&#xff1a;4.分析&#xff1a; 斯皮尔曼相关系数基…
阅读更多...
Git的入门详细教程

Git的入门详细教程

&#x1f3c5;我是默&#xff0c;一个在CSDN分享笔记的博主。&#x1f4da;&#x1f4da; ​​ &#x1f31f;在这里&#xff0c;我要推荐给大家我的专栏《git》。&#x1f3af;&#x1f3af; &#x1f680;无论你是编程小白&#xff0c;还是有一定基础的程序员&#xff0c;这…
阅读更多...
企业级，搭建接口自动化测试框架思路分析，8年测试老鸟整理...

企业级，搭建接口自动化测试框架思路分析，8年测试老鸟整理...

目录&#xff1a;导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09; 前言 在选择接口测试自…
阅读更多...
Vue3 学习笔记

Vue3 学习笔记

vue3 官网&#xff1a;简介 | Vue.js (vuejs.org) 1. 环境搭建与启动 npm create vuelatest 这一指令将会安装并执行 create-vue&#xff0c;它是 Vue 官方的项目脚手架工具 之后&#xff0c;你将会看到一些诸如 TypeScript 和测试支持之类的可选功能提示&#xff1a; ✔ …
阅读更多...
学习笔记|SPSS|描述变量|按照3倍标准差剔除异常值|标准化值另存为变量|剔除个案|Zscore|箱图|Zscore取值范围

学习笔记|SPSS|描述变量|按照3倍标准差剔除异常值|标准化值另存为变量|剔除个案|Zscore|箱图|Zscore取值范围

目录 学习目的软件版本原始文档概述服从正态分布-按照3倍标准差剔除异常值读数据数据概览描述变量 正态性检验异常值检验及剔除 非正态分布-根据Zscore取值范围确定基础数据数据概览正态性检验Tips&#xff1a;箱图圆圈的含义 异常值检验及剔除描述变量&#xff0c;并将标准化值…
阅读更多...
C语言C位出道心法(三):共用体|枚举

C语言C位出道心法(三):共用体|枚举

C语言C位出道心法(一):基础语法 C语言C位出道心法(二):结构体|结构体指针|链表 一: C语言共用体数据类型认知 二:C语言枚举基本数据类型认知 忙着去耍帅,后期补充完整.............
阅读更多...
Verilog刷题[hdlbits] ：Alwaysblock2

Verilog刷题[hdlbits] ：Alwaysblock2

题目&#xff1a;Alwaysblock2 For hardware synthesis, there are two types of always blocks that are relevant: 对于硬件综合&#xff0c;有两种相关的always块&#xff1a; Combinational: always () 组合型&#xff1a;always ()Clocked: always (posedge clk) 时钟型…
阅读更多...
Python实现图片与PDF互相转换

Python实现图片与PDF互相转换

目录 图片转PDF文件夹所有图片转为1个PDF文件夹指定图片转为1个PDF文件夹所有图片分别转为PDF举例 PDF转图片指定PDF转为图片文件夹所有PDF转为图片举例 图片转PDF 之前的一篇博客《Python合并拼接图片》&#xff0c;可对图片进行合并拼接 使用前需要安装PyMuPDF库&#xff0c…
阅读更多...
最新文章

Copyright @ 2022~2023