Java集合—Set(Collection子接口)及其子类(HashSet、LinkedHashSet)包括HashMap源码分析

Set接口是 Collection接口的子接口。
1、无序,即添加元素和去除元素的顺序不一致。
但是每次取出的顺序是一致的。
2、不允许重复元素,可以有null,但只能有一个。
3、实现类很多,主要介绍HashSet、LinkedHashSet 和 TreeSet。
常用方法
因为其为Collection的子接口,因此常用方法和Collection一致。
遍历方式
因为其是Collection的子接口,所以其遍历方法与Collection一致。
即:
  1. 使用迭代器Iterator
  2. 使用增强for

一、HashSet

  1. HashSet实现了Set接口
  2. HashSet底层上是HashMap,其底层为:数组+链表+红黑树
  3. 可以存放null,但是只能存放一个。
  4. HashSet不保证数据是有序的(即不保证存取顺序一致),取决于hash后,再确定索引的结果。
  5. 不能有重复的对象

源码

  • HashSet底层是HashMap
  • 添加一个元素时,先得到hash值,将其转变为索引值
  • 找到存储数据表table,判断该索引位置是否已经有存放的元素
    • 没有,则直接加入
    • 有,则调用 equals 比较,相同则放弃添加;不同,则添加到链表后面
  • 在Java8中,如果一条链表个数到达了TREEIFY_THRESHOLD(默认值为8),
           并且table>=MIN_TREEIFY_CAPACITY(默认64),就会转化成红黑树。
1、新建对象
    调用自身构造器,在构造器内调用HashMap()构造器。
    
  
2、add()添加对象
    执行add()方法,调用put()方法
    然后执行put()方法,调用hash()获取 key值 ,之后调用putVal()方法
    putVal()则是真的存放数据的方法。
①add()方法
    可见,add()方法直接调用 put()方法,传入两个参数,分别为key和value;
        key为我们add的数据;
        value为PRESENT,下面第二张图,可见其为一个静态的常量,为所用对象共有的
        因为其底层是HashMap,是键值对,其中key为HashSet要存放的数据,Value如果填Null,虽然节省空间,
        但是意味着无论是否添加成功,都返回Null,那么则无法判断是否添加成功,因此放了 PRESENT。
        可见, 返回null才是添加成功
    
    
②HashMap.put()方法:
    put()方法直接先调用hash()获取hash值,然后调用putVal()方法。
    
    hash()将我们 即将添加的值hashcode值 与 其hashcode无符号向右位移16位的值 按位异或。
    目的就是为了减少碰撞, 具体原因: h = key.hashCode()) ^ (h >>> 16)  
    
    hashcode()方法获取hash值:
        不同类不一样,一般都会重写。
    Object类:    
        Object的hashcode 方法是本地方法,也就是用 c 或 c++ 实现的,该方法直接返回对象的内存地址。
        注意其为native修饰。详情: Object顶级类(包含==和equals区别)
        
  
③HashMap.putval()方法:
源码前,先看:
    table为HashMap存放数据的数组,为Node类型的数组;
    
    Node为每个数据所存放的对象:
        hash:存放对象Key所对应的hash值
        key:存放数据对象
        value:每个对象都一样,就是①中所说的PRESENT,一个Object类型的常量对象。
        next:是下一个节点的引用。
    
    resize()数组扩容源码
final Node<K,V>[] resize() {
    //将table赋值给oldtab
    Node<K,V>[] oldTab = table;

    //oldcap存放旧table数组的大小
    //    如果旧数组为null,则oldcap为0
    //    如果旧数组不为null,则oldcap为其原来的大小
    int oldCap = (oldTab == null) ? 0 : oldTab.length;

    //oldthr存放扩容阈值,HashMap并不是数据满了才存放,而是达到阈值就进行扩容
    int oldThr = threshold;

    //newcap存放新的数组大小,newthr存放新的扩容阈值
    int newCap, newThr = 0;

    
    //oldcap大于0,即table扩容前不为null的情况
    if (oldCap > 0) {
        ...
    }

    //初始容量设置为阈值
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;

    //table为null的情况
    //newcap赋值为DEFAULT_INITIAL_CAPACITY,
    //newthr赋值为(int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY)
    //DEFAULT_INITIAL_CAPACITY为默认初始容量16,定义:static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    //DEFAULT_LOAD_FACTOR为默认缓存大小0.75,定义:static final float DEFAULT_LOAD_FACTOR = 0.75f;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }

    //修改newThr
    if (newThr == 0) {
        ...
    }

    //将newthr赋值给threshold,即缓存大小设置完毕
    threshold = newThr;

    @SuppressWarnings({"rawtypes","unchecked"})
    //因为table为数组,因此扩容需要新建立数组
    //然后将新数组赋给table
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;

    //如果旧数组table不为null,则需要将旧数组中的数据转移到新数组,具体先不研究
    if (oldTab != null) {
                . . .
    }
    
    //最后返回新的数组table
    return newTab;
}
    treeifyBin():判断对应链表是否需要树化
        先进行判断,如果数组长度小于MIN_TREEIFY_CAPACITY(默认64),则调用resize()进行扩容
        否则进行树化。
    
putVal()源码如下:
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {

    //tab为table
    //n用来存放table长度;
    //p用来存放table中将要存放的位置的对象
    //i用来存放table中将要存放位置的下标
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    
    //将table赋给tab,判断是否为null或者判断length是否为0
    //若table不为空,则跳过该段代码,否则进入resize()方法
    //将长度赋给n
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;

    //计算出待存放位置,即i位置的table[i]为null
    //1.将 n-1 和 传进来的hash 进行按位与,并将其赋值给 i
    //2.将tab[i],即按位与得到下标的位置在数组中的对象赋值给p
    //3.如果p为null,说明该位置还没有存放,则新建一个结点存放进去,结点信息在上面
    //4.然后该结点赋值给tab[i]
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    //计算出待存放位置不为空,即 待存储数据的hash值 与 之前存储过的数据hash值 一致,
    //是否存入新数据如下:
    else {
        //创建辅助变量
        Node<K,V> e; K k;
        //如果 p.hash即数组当前位置的链表的第一个元素的hash值 与 hash即待插入的新元素的hash值相同
        //且满足下面条件之一:(将p.key赋给k)
        //    k == key 即 第一个元素的key 和 带加入元素的key 是同一个对象
        //    key != null && key.equals(k) 即 key非空 且 key 和 kequals相同,即内容相同
        //则将 p 赋值给 e,p就是当前数组当前位置的链表的第一个元素
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        //如果p是一颗红黑树,就以红黑树添加元素的方式进行比较并添加新的对象
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        //如果不满足上述两种情况,即值不同,且p还不是红黑树
        //则当前p为一个链表
        //就进行循环
        else {
            for (int binCount = 0; ; ++binCount) {
                //遍历到了尾部,追加新节点到尾部
                //先判断p.next是否为null
                //如果为null则直接将新结点存入,并退出循环
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    //如果新增加元素后 > TREEIFY_THRESHOLD(默认为8)-1=7,即有了8个结点,
                    //则调用treeifyBin()进行判断是否树化,方法在上面
                    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;
            }
        }
        //如果e不等于null,则说明原来存在与带加入节点hash值相同,但是value值不同节点
        //然后用新的value代替旧的value
        //则返回旧value
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            //空方法,没实现,LinkedHashMap的时候有用到
            afterNodeAccess(e);
            return oldValue;
        }
    }

    //modCount即操作数+1
    ++modCount;

    //size即数组大小+1
    //+1之后的size如果大于了threshold,则需要扩容
    //注意,此处是size>threshold,而size每次增加是在加入一个结点之后;
    //意味着并不是数组table用到了threshold个,而是结点达到threshold个。
    if (++size > threshold)
        resize();

    //该函数在HashMap中是一个空函数
    //该函数由HashMap的子类实现,用来实现排序存放等。
    afterNodeInsertion(evict);
    
    //最后返回null为添加成功
    return null;
}

二、LinkedHashSet

  1. LinkedHashSet是HashSet的子类。
  2. LinkedHashSet底层是 LinKedHashMap,维护了一个 数组 + 双向链表
  3. LinkedHashSet根据元素的hashcode决定元素的存储位置,同时使用链表维护元素的次序,使得元素看起来是以插入顺序保存的。
  4. LinkedHashSet不允许添加重复元素。

源码

  • LinkedHashSet维护一个hash表和双向链表
    • 该类有两个属性head 和 tail ,用来表示头节点和尾节点
  • 每一个节点还有 pre 和 next 属性,用来形成双向链表
  • 添加一个元素时,先求hash值,再求索引,确定其在table中的位置
    • 如果没有重复,跟HashSet一样加入,之后再加入双向链表
    • 有重复则不加入
  • 因此,遍历时使用链表,就会呈现和添加顺序一样的遍历顺序了。
  • 存放的节点不是Node了,而是
1、构造器:
    可见构造器是直接调用父类的有参构造器,默认初始容量为16,阈值为0.75。
    注意, HashSet()中创建的对象是LinkedHashMap(),而不是HashMap()。
    
    
2、add()添加元素:
    与HashSet类似,也是直接调用LinkedHashMap的add()方法
    然后调用 HashMap 的put()方法,因为LinkedHashMap并未重写该方法
    再调用 HashMap 的putVal()方法
    
    
putVal()方法:
    与HashSet一样,但是在 newNode()时,使用的是LinkedHaspMap的方法:
        先创建一个Entry对象。
        然后调用父类构造方法构造Node。
            注意:Entry继承了HashMap的内部类Node
        再调用linkNodeLast()方法将该节点链接在链表当中。
    
    
    
    与HashSet不同的还有在最后 afterNodeInsertion(evict)是实现了的
    
    

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

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

相关文章

使用Ollama和Open WebUI管理本地开源大模型的完整指南

&#x1f3e1;作者主页&#xff1a;点击&#xff01; &#x1f916;AI大模型部署与应用专栏&#xff1a;点击&#xff01; ⏰️创作时间&#xff1a;2024年5月27日12点20分 &#x1f004;️文章质量&#xff1a;96分 目录 ✨️Open-WebUI介绍 优点 &#x1f4a5;部署教程…

Reddit是什么?跨境独立站卖家如何用Reddit营销?

在互联网时代&#xff0c;社交媒体营销已成为品牌推广的重要手段。Reddit&#xff0c;作为一个充满活力的社区平台&#xff0c;正逐渐受到越来越多跨境独立站卖家的关注。如果你在独立站引流方面遇到瓶颈&#xff0c;不妨了解一下Reddit这个平台。本文将介绍Reddit是什么&#…

天诚公租房/人才公寓WiFi人脸识别物联网智能门锁解决方案

人才是引领城市高质量发展的重要因素&#xff0c;城市要想吸纳人才的保障便是人才公寓。近年来&#xff0c;全国各地一二三线城市都在大力建设人才公寓&#xff0c;集聚菁英人才&#xff0c;倾力打造人才高地。 一、人才公寓如火如荼建设 2023年底&#xff0c;山东德州提出三年…

排序进阶----插入排序,希尔排序

各位看官们好&#xff0c;接下来鄙人想与大家分享的实现被称为六大排序之一的插入排序。其实关于这六大排序在我们最开始就已经接触过了。我们在最开始学习c语言的时候&#xff0c;我们要学习到其中之一的冒泡排序。虽然现在看起来冒泡排序确实是没有太大的实际效果&#xff0c…

【第一节】从C语言到C++

目录 一、面向对象编程 1.早期概念 2.发展与普及 3. 现代发展 二、从C语言到C 1.关于堆内存的使用 2.关于函数重载 3.关于默认参数 4.引用 5.引用参数 6.作用域符号 三、C的输入输出机制 一、面向对象编程 面向对象编程&#xff08;Object-Oriented Programming&am…

Midjourney进阶必看 | 垫图效果的必备技能

还在纠结Midjourney垫图效果不佳&#xff1f;快看看是不是这5点没有做好&#xff01; 前言一、内容形式要一致二、用文本描述强调画面内容三、尝试不同的--iw参数四、用--no参数去除隐藏干扰项五、记得多生成几次 总结 前言 图像提示词&#xff0c;也就是垫图&#xff0c;是Mi…

Verilog实战学习到RiscV - 1 : Yosys 综合

Yosys 综合 实例 一般 FPGA IDE 的第一步都是RTL 综合&#xff08;Synthesis&#xff09;。之后就能看到数字电路图了。然后可以做RTL 级的仿真模拟。 直接上代码&#xff0c;这里我们看一个简单的加法器来学习。 module adder(input [7:0] a,input [7:0] b, input …

Java | Leetcode Java题解之第103题二叉树的锯齿形层序遍历

题目&#xff1a; 题解&#xff1a; class Solution {public List<List<Integer>> zigzagLevelOrder(TreeNode root) {List<List<Integer>> ans new LinkedList<List<Integer>>();if (root null) {return ans;}Queue<TreeNode> n…

el-tabs中的下拉框被覆盖解决方法

解决方法&#xff1a; ::v-deep .el-tabs__content{// overflow:hidden 会导致 分页下拉框超出部分会被.el-tabs__content隐藏overflow: visible; }

基础—SQL—DML(数据操作语言)修改和删除

一、引言 接着上次博客&#xff0c;这次讲解DML语句中的修改数据和删除数据操作。 二、DML—修改数据 UPDATE 表名 SET 字段名1值1 ,字段名2值2 , ...[ WHERE 条件]; 注意&#xff1a;修改语句的条件可以有&#xff0c;也可以没有。如果没有条件&#xff0c;则会修改整张表的…

MySQL 解决登录报错 - 错误1130- Host xxx is not allowed to connect to this server

1、原因 没有给远程连接权限 2、解决 2.1 打开命令行提示符界面输入命令cd C:\Program Files\MySQL\MySQL Server 8.0\bin\ 2.2 连接 MySQL 数据库 输入命令 mysql -u root -p &#xff0c;然后输入密码 回车登录 2.3 查看当前表中的数据库 show databases;查看当前使用的数…

每天写两道(二)LRU缓存、数组中最大的第k个元素

146.LRU 缓存 . - 力扣&#xff08;LeetCode&#xff09; 请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类&#xff1a; LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存int get(int key) 如果关键字 key 存在于缓存…

在Anki中按某个字段满足的条件查找笔记

Anki中可以使用deck、tag、card、note、is、prop、added、rated、nid、cid等关键字按照牌组、标签、卡片、卡片类型、状态、属性、添加时间、回答时间、对象id等对卡片进行筛选&#xff0c;但是没有提供按卡片字段进行筛选的关键字&#xff0c;那么&#xff0c;怎么按卡片字段是…

C++ (week5):Linux系统编程3:线程

文章目录 三、线程1.线程的基本概念①线程相关概念②我的理解 2.线程的基本操作 (API)(1)获取线程的标识&#xff1a;pthread_self(2)创建线程&#xff1a;pthread_create()(3)终止线程①pthread_exit()&#xff1a;当前线程终止&#xff0c;子线程主动退出②pthread_cancel()&…

安卓ADB通过WIFI无线连接手机[通过无线安装APK]

安卓ADB通过无线连接手机 本文摘录于&#xff1a;https://www.cnblogs.com/zhuxibo/p/14261117.html只是做学习备份之用&#xff0c;绝无抄袭之意&#xff0c;有疑惑请联系本人&#xff01; 别人给的操作确实可行,我这里实操记录如下: AdministratorpiaoranPC MINGW64 /e/Wor…

大模型部署框架 FastLLM 简要解析

0x0. 前言 本文主要是对FastLLM做了一个简要介绍&#xff0c;展示了一下FastLLM的部署效果。然后以chatglm-6b为例&#xff0c;对FastLLM模型导出的流程进行了解析&#xff0c;接着解析了chatglm-6b模型部分的核心实现。最后还对FastLLM涉及到的优化技巧进行了简单的介绍。 0…

Java 阻塞队列与生产者消费者模型

一、阻塞队列 阻塞队列是⼀种特殊的队列&#xff0c;其也遵守队列 "先进先出" 的原则&#xff1b; 阻塞队列是⼀种线程安全的数据结构&#xff0c;并且具有以下特性&#xff1a; 当队列满的时候&#xff0c;继续入队列就会阻塞&#xff0c;直到有其他线程从队列中…

成都市酷客焕学新媒体科技有限公司:助力品牌打破困境!

在数字化浪潮的推动下&#xff0c;营销策略对品牌的发展愈发关键。成都市酷客焕学新媒体科技有限公司&#xff0c;作为短视频营销领域的佼佼者&#xff0c;凭借其卓越的策略和实力&#xff0c;助力众多品牌在信息海洋中脱颖而出&#xff0c;实现品牌的显著增长。 酷客焕学专注于…

抖音和快手哪个好?来全面了解一下他们的区别!

快手和抖音虽然是短视频领域的两大主流平台&#xff0c;但是两者也存在本质的区别&#xff0c;从产品定位、用户群体到视频风格、变现模式&#xff0c;它们的特征都不一样。 &#xff08;一&#xff09;两个平台核心区别&#xff1a; 1. 核心用户不一样&#xff1a;抖音以1、…

【最优化方法】实验四 约束最优化方法的MATLAB实现

实验的目的和要求&#xff1a;通过本次实验使学生较为熟练使用MATLAB软件&#xff0c;并能利用该软件进行约束最优化方法的计算。 实验内容&#xff1a; &#xff11;、罚函数法的MATLAB实现 &#xff12;、可行方向法的MATLAB实现 学习建议&#xff1a; 本次实验就是要通…