Java集合(二)

1. Map

1.1 HashMap 和 Hashtable 的区别

  • 线程是否安全: HashMap 是非线程安全的,Hashtable 是线程安全的,因为 Hashtable 内部的方法基本都经过synchronized 修饰。(如果你要保证线程安全的话就使用 ConcurrentHashMap 吧!);
  • 效率: 因为线程安全的问题,HashMap 要比 Hashtable 效率高一点。另外,Hashtable 基本被淘汰,不要在代码中使用它;
  • 对 Null key 和 Null value 的支持: HashMap 可以存储 null 的 key 和 value,但 null 作为键只能有一个,null 作为值可以有多个;Hashtable 不允许有 null 键和 null 值,否则会抛出 NullPointerException
  • 初始容量大小和每次扩充容量大小的不同: ① 创建时如果不指定容量初始值,Hashtable 默认的初始大小为 11,之后每次扩充,容量变为原来的 2n+1。HashMap 默认的初始化大小为 16。之后每次扩充,容量变为原来的 2 倍。② 创建时如果给定了容量初始值,那么 Hashtable 会直接使用你给定的大小,而 HashMap 会将其扩充为 2 的幂次方大小(HashMap 中的tableSizeFor()方法保证,下面给出了源代码)。也就是说 HashMap 总是使用 2 的幂作为哈希表的大小,后面会介绍到为什么是 2 的幂次方。
  • 底层数据结构: JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化,当链表长度大于阈值(默认为 8)时,将链表转化为红黑树(将链表转换成红黑树前会判断,如果当前数组的长度小于 64,那么会选择先进行数组扩容,而不是转换为红黑树),以减少搜索时间(后文中我会结合源码对这一过程进行分析)。Hashtable 没有这样的机制。

HashMap 中带有初始容量的构造函数:

    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);
    }
     public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

下面这个方法保证了 HashMap 总是使用 2 的幂作为哈希表的大小。

    /**
     * Returns a power of two size for the given target capacity.
     */
    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

 1.2 HashMap 和 HashSet 区别

如果你看过 HashSet 源码的话就应该知道:HashSet 底层就是基于 HashMap 实现的。(HashSet 的源码非常非常少,因为除了 clone()writeObject()readObject()HashSet 自己不得不实现之外,其他方法都是直接调用 HashMap 中的方法。

方法都是直接调用 HashMap 中的方法。

HashMapHashSet
实现了 Map 接口实现 Set 接口
存储键值对仅存储对象
调用 put()向 map 中添加元素调用 add()方法向 Set 中添加元素
HashMap 使用键(Key)计算 hashcodeHashSet 使用成员对象来计算 hashcode 值,对于两个对象来说 hashcode 可能相同,所以equals()方法用来判断对象的相等性

1.3 HashMap 和 TreeMap 区别

TreeMap 和HashMap 都继承自AbstractMap ,但是需要注意的是TreeMap它还实现了NavigableMap接口和SortedMap 接口。

实现 NavigableMap 接口让 TreeMap 有了对集合内元素的搜索的能力。

实现SortedMap接口让 TreeMap 有了对集合中的元素根据键排序的能力。默认是按 key 的升序排序,不过我们也可以指定排序的比较器。示例代码如下:

/**
 * @author shuang.kou
 * @createTime 2020年06月15日 17:02:00
 */
public class Person {
    private Integer age;

    public Person(Integer age) {
        this.age = age;
    }

    public Integer getAge() {
        return age;
    }


    public static void main(String[] args) {
        TreeMap<Person, String> treeMap = new TreeMap<>(new Comparator<Person>() {
            @Override
            public int compare(Person person1, Person person2) {
                int num = person1.getAge() - person2.getAge();
                return Integer.compare(num, 0);
            }
        });
        treeMap.put(new Person(3), "person1");
        treeMap.put(new Person(18), "person2");
        treeMap.put(new Person(35), "person3");
        treeMap.put(new Person(16), "person4");
        treeMap.entrySet().stream().forEach(personStringEntry -> {
            System.out.println(personStringEntry.getValue());
        });
    }
}

person1
person4
person2
person3 

可以看出,TreeMap 中的元素已经是按照 Person 的 age 字段的升序来排列了。

上面,我们是通过传入匿名内部类的方式实现的,你可以将代码替换成 Lambda 表达式实现的方式:

TreeMap<Person, String> treeMap = new TreeMap<>((person1, person2) -> {
  int num = person1.getAge() - person2.getAge();
  return Integer.compare(num, 0);
});

综上,相比于HashMap来说 TreeMap 主要多了对集合中的元素根据键排序的能力以及对集合内元素的搜索的能力。

1.4 HashSet 如何检查重复?

当你把对象加入HashSet时,HashSet 会先计算对象的hashcode值来判断对象加入的位置,同时也会与其他加入的对象的 hashcode 值作比较,如果没有相符的 hashcodeHashSet 会假设对象没有重复出现。但是如果发现有相同 hashcode 值的对象,这时会调用equals()方法来检查 hashcode 相等的对象是否真的相同。如果两者相同,HashSet 就不会让加入操作成功。 

 在 JDK1.8 中,HashSetadd()方法只是简单的调用了HashMapput()方法,并且判断了一下返回值以确保是否有重复元素。直接看一下HashSet中的源码:

// Returns: true if this set did not already contain the specified element
// 返回值:当 set 中没有包含 add 的元素时返回真
public boolean add(E e) {
        return map.put(e, PRESENT)==null;
}

而在HashMapputVal()方法中也能看到如下说明:

// Returns : previous value, or null if none
// 返回值:如果插入位置没有元素返回null,否则返回上一个元素
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
...
}

也就是说,在 JDK1.8 中,实际上无论HashSet中是否已经存在了某元素,HashSet都会直接插入,只是会在add()方法的返回值处告诉我们插入前是否存在相同元素。

1.5 HashMap 的底层实现

1.5.1 JDK1.8 之前

JDK1.8 之前 HashMap 底层是 数组和链表 结合在一起使用也就是 链表散列。HashMap 通过 key 的 hashcode 经过扰动函数处理过后得到 hash 值,然后通过 (n - 1) & hash 判断当前元素存放的位置(这里的 n 指的是数组的长度),如果当前位置存在元素的话,就判断该元素与要存入的元素的 hash 值以及 key 是否相同,如果相同的话,直接覆盖,不相同就通过拉链法解决冲突。

所谓扰动函数指的就是 HashMap 的 hash 方法。使用 hash 方法也就是扰动函数是为了防止一些实现比较差的 hashCode() 方法 换句话说使用扰动函数之后可以减少碰撞。

JDK 1.8 HashMap 的 hash 方法源码:

JDK 1.8 的 hash 方法 相比于 JDK 1.7 hash 方法更加简化,但是原理不变。

    static final int hash(Object key) {
      int h;
      // key.hashCode():返回散列值也就是hashcode
      // ^:按位异或
      // >>>:无符号右移,忽略符号位,空位都以0补齐
      return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  }

对比一下 JDK1.7 的 HashMap 的 hash 方法源码.

static int hash(int h) {
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).

    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

相比于 JDK1.8 的 hash 方法 ,JDK 1.7 的 hash 方法的性能会稍差一点点,因为毕竟扰动了 4 次。

所谓 “拉链法” 就是:将链表和数组相结合。也就是说创建一个链表数组,数组中每一格就是一个链表。若遇到哈希冲突,则将冲突的值加到链表中即可。

1.5.2 JDK1.8 之后

相比于之前的版本, JDK1.8 之后在解决哈希冲突时有了较大的变化,当链表长度大于阈值(默认为 8)(将链表转换成红黑树前会判断,如果当前数组的长度小于 64,那么会选择先进行数组扩容,而不是转换为红黑树)时,将链表转化为红黑树,以减少搜索时间。

TreeMap、TreeSet 以及 JDK1.8 之后的 HashMap 底层都用到了红黑树。红黑树就是为了解决二叉查找树的缺陷,因为二叉查找树在某些情况下会退化成一个线性结构。 

我们来结合源码分析一下 HashMap 链表到红黑树的转换。

1、 putVal 方法中执行链表转红黑树的判断逻辑。

链表的长度大于 8 的时候,就执行 treeifyBin (转换红黑树)的逻辑。

// 遍历链表
for (int binCount = 0; ; ++binCount) {
    // 遍历到链表最后一个节点
    if ((e = p.next) == null) {
        p.next = newNode(hash, key, value, null);
        // 如果链表元素个数大于等于TREEIFY_THRESHOLD(8)
        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;
}

 2、treeifyBin 方法中判断是否真的转换为红黑树。

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    // 判断当前数组的长度是否小于 64
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        // 如果当前数组的长度小于 64,那么会选择先进行数组扩容
        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);
    }
}

将链表转换成红黑树前会判断,如果当前数组的长度小于 64,那么会选择先进行数组扩容,而不是转换为红黑树。

1.6 HashMap 的长度为什么是 2 的幂次方

为了能让 HashMap 存取高效,尽量较少碰撞,也就是要尽量把数据分配均匀。我们上面也讲到了过了,Hash 值的范围值-2147483648 到 2147483647,前后加起来大概 40 亿的映射空间,只要哈希函数映射得比较均匀松散,一般应用是很难出现碰撞的。但问题是一个 40 亿长度的数组,内存是放不下的。所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算,得到的余数才能用来要存放的位置也就是对应的数组下标。这个数组下标的计算方法是“ (n - 1) & hash”。(n 代表数组长度)。这也就解释了 HashMap 的长度为什么是 2 的幂次方。

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

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

相关文章

[多线程]阻塞队列和生产者消费者模型

目录 1.阻塞队列 1.1引言 1.2Java标准库中的阻塞队列 1.3自主通过Java代码实现一个阻塞队列(泛型实现) 2.生产者消费者模型 1.阻塞队列 1.1引言 阻塞队列是多线程部分一个重要的概念,它相比于一般队列,有两个特点: 1.线程是安全的 2.带有阻塞功能 1) 队列为空,出队列就会阻…

鸿蒙HarmonyOS从零实现类微信app效果——基础界面搭建

最近鸿蒙HarmonyOS开发相关的消息非常的火&#xff0c;传言华为系手机后续将不再支持原生Android应用&#xff0c;所以对于原Android应用开发对应的Harmony版本也被一系列大厂提上了日程。作为一个名义上的移动端开发工程师&#xff08;(⊙o⊙)…&#xff0c;最近写python多过A…

应急响应-挖矿病毒处理

应急响应-挖矿病毒处理 使用top​命令实时监控占用CPU资源的是哪个进程&#xff0c;结果可以看到是2725这个进程。 ​​ 再使用netstat -anltp命令查看网络连接状态&#xff0c;定位到对应的PID号后&#xff0c;就拿到了远程地址 ​​ 拿到远程IP&#xff0c;结果是VPN入口…

JVM 运行时内存(三)

Java 堆从 GC 的角度还可以细分为: 新生代(Eden 区、From Survivor 区和 To Survivor 区)和老年代。 1. 新生代 是用来存放新生的对象。一般占据堆的 1/3 空间。由于频繁创建对象&#xff0c;所以新生代会频繁触发MinorGC 进行垃圾回收。新生代又分为 Eden 区、ServivorFrom、…

人工智能_机器学习059_非线性核函数_poly核函数_rbf核函数_以及linear核函数效果对比---人工智能工作笔记0099

人工智能_机器学习059_非线性核函数介绍---人工智能工作笔记0099 那么我们应该如何调整这个SVC的参数,也就是我们应该使用哪种核函数,比较合适呢?这取决于我们的数据,适合使用哪个核函数,正好我们有 提供的score = accuracy_score(y_test,y_pred) 这样的评分函数,我们可以根据…

B2B公司如何寻找意向客户的联系方式?

在B2B公司的营销过程中&#xff0c;少不了寻找意向客户的阶段&#xff0c;这也是销售过程中非常重要的一步。 很多新人都是拿到客户联系方式&#xff0c;就直接打电话拜访&#xff0c;俗话说不打没有准备的仗&#xff0c;因此在拜访客户之前就应该做好功课&#xff0c;充分了解…

AI医疗交流平台【Docola】申请823万美元纳斯达克IPO上市

来源&#xff1a;猛兽财经 作者&#xff1a;猛兽财经 猛兽财经获悉&#xff0c;总部位于美国的AI医疗交流平台Docola近期已向美国证券交易委员会&#xff08;SEC&#xff09;提交招股书&#xff0c;申请在纳斯达克IPO上市&#xff0c;股票代码为 (DOCO) &#xff0c;Docola计划…

【五分钟】熟练使用numpy的histogram函数(干货!!!)

histogram函数重要参数详解 def histogram(a, bins10, rangeNone, normedNone, weightsNone, densityNone):...位置参数a&#xff1a; The histogram is computed over the flattened array.&#xff08;源码对参数a的解释&#xff09; 从源码对参数a的解释来看&#xff0c;参…

从0开始使用Maven

文章目录 一.Maven的介绍即相关概念1.为什么使用Maven/Maven的作用2.Maven的坐标 二.Maven的安装三.IDEA编译器配置Maven环境1.在IDEA的单个工程中配置Maven环境2.方式2&#xff1a;配置Maven全局参数 四.IDEA编译器创建Maven项目五.IDEA中的Maven项目结构六.IDEA编译器导入Mav…

设计模式之代理模式(1)

目录 概述定义应用场景主要角色类图 详述基本代码应用实例符合的设计原则 总结 概述 定义 代理模式是一种结构型设计模式&#xff0c;它允许通过一个代理对象来控制对原始对象的访问。代理对象可以在不改变原始对象的情况下&#xff0c;增加一些额外的功能&#xff0c;例如权限…

差分基准站

差分基准站&#xff0c;又称参考接收机&#xff0c;是一种固定式卫星接收机&#xff0c;用于提高卫星定位精度。 差分基准站的作用是提供已知位置和准确的位置信号&#xff0c;以纠正其他移动定位终端接收器接收到的卫星信号中的误差。 卫星定位信号会受到多种因素的影响&#…

selenium自动化测试:xpath八种定位方式!

01、前言 如果可以的话&#xff0c;请先关注&#xff08;专栏和账号&#xff09;&#xff0c;然后点赞和收藏&#xff0c;最后学习和进步。你的支持是我继续写下去的最大动力&#xff0c;个人定当倾囊而送&#xff0c;不负众望。谢谢&#xff01;&#xff01;&#xff01; 1.…

【蓝桥杯省赛真题49】Scratch小狗避障 蓝桥杯scratch图形化编程 中小学生蓝桥杯省赛真题讲解

目录 scratch小狗避障 一、题目要求 编程实现 二、案例分析 1、角色分析

JDK安装太麻烦?一篇文章搞定

JDK是 Java 语言的软件开发工具包&#xff0c;主要用于移动设备、嵌入式设备上的java应用程序。JDK是整个java开发的核心&#xff0c;它包含了JAVA的运行环境&#xff08;JVMJava系统类库&#xff09;和JAVA工具。 JDK包含的基本组件包括&#xff1a; javac – 编译器&#xf…

从零开始入门Zapier:与ChatGPT双剑合璧,手把手教程让你进入AI与自动化新纪元

coments 1. 1. 打开Zapier的官方界面 登录之后&#xff0c;会出现一个调查表&#xff0c;可以根据自己的情况进行选择。 第一次注册成功&#xff0c;会送你14天的免费体验

SAP ABAP ALV创建动态树形菜单

创建动态树形菜单——ALV 创建的合同越多&#xff0c;使用树形菜单能比较直观的地显示&#xff0c;而且展开下阶也能明确的知识相关的信息&#xff0c;比如合同中的出口成品有哪些。 设计要点&#xff1a; 第一、 Node_key一定要区分&#xff0c;不能重复&#xff0c;否则出错…

C语言--每日选择题--Day35

第一题 1. 有如下定义&#xff1a;(x y) % 2 (int) a / (int) b 的值是&#xff08;&#xff09; int x 3; int y 2;float a 2.5; float b 3.5; A&#xff1a;0 B&#xff1a;2 C&#xff1a;1.5 D&#xff1a;1 答案及解析 D 本题是考查强制类型转换和操作符优先级 操作…

JavaWeb 前端工程化

前端工程化是使用软件工程的方法来单独解决前端的开发流程中模块化、组件化、规范化、自动化的问题,其主要目的为了提高效率和降低成本。 前端工程化实现技术栈 前端工程化实现的技术栈有很多,我们采用ES6nodejsnpmViteVUE3routerpiniaaxiosElement-plus组合来实现 ECMAScri…

由11月27日滴滴崩溃到近两个月国内互联网产品接二连三崩溃引发的感想

文章目录 知乎文分析微信聊天截图微信公众号 滴滴技术 发文k8s 官方文档滴滴官方微博账号 近两个月国内互联网产品“崩溃”事件2023-10-23 语雀崩溃2023-11-12 阿里云崩溃2023-11-27 滴滴崩溃2023-12-03 腾讯视频崩溃总结 我的感想 知乎文分析 最近连续加班&#xff0c;打车较…

简单的界面与数据分离的架构

草图绘制于2021年2月19日 当时用到了&#xff1a;qt的子项目、delegate、view和widget的关系&#xff0c;有感而写的小备忘&#xff0c;2022年底考的软件设计师里面的设计模式虽然可能早已包含&#xff0c;但自己也得有自己啊&#xff0c;要把自己哪怕不成熟的东西也记录下来&…