Java集合自测题

2024-06-12 23:28
文章标签 java 集合 自测题

本文主要是介绍Java集合自测题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 一、说说 List , Set , Map 三者的区别?
  • 二、List , Set , Map 在 Java 中分别由哪些对应的实现类?底层的数据结构?
  • 三、有哪些集合是线程不安全的?怎么解决呢?
  • 四、HashMap 查询,删除的时间复杂度
  • 五、HashMap 的底层实现?
  • 六、HashMap 的⻓度为什么是 2 的幂次方
  • 七、比较 HashSet 、 LinkedHashSet 和 TreeSet 三者的异同
  • 八、HashMap 和 Hashtable 的区别? HashMap 和 HashSet 区别? HashMap 和 TreeMap 区别?ConcurrentHashMap 和 Hashtable 的区别?
  • 九、ConcurrentHashMap 线程安全的具体实现方式/底层具体实现


一、说说 List , Set , Map 三者的区别?

可以从这些数据结构中的元素是否有序、是否可以重复、存储的元素类型(⽐如 Map 存储的就是键值对)等⽅⾯来回答。

首先,就是LIst集合是单列集合,而Map集合是双列集合,也就是存储的是键值对。List集合通常是有序的,而Set集合和Map集合通常是无序的,同时,List集合里面的元素是可以重复的而Set集合里面的元素是不可重复的。Map集合中的键是可以不可重复的,而值是可以重复的。


二、List , Set , Map 在 Java 中分别由哪些对应的实现类?底层的数据结构?

提示:拿 List 来举例, List 的常⻅实现类以及它们的数据结构 :1、ArrayList : Object[] 数组 2、Vector : Object[] 数组 3、LinkedList : 双向链表(JDK1.6 之前为循环链表,JDK1.7 取消了循环)

首先说List集合,它的实现类有ArrayList、Vector、LinkedLIst,其中ArraList和Vector是由数组来实现的,而LinkedList而是由双向链表来实现的。然后再说Set集合,它的主要实现类是HashSet、LinkedHashSet和TreeSet,其中HashSet是基于HashMap实现的,LinkedHashSet是HashSet的子类,是通过LinkedHashMap来实现的。TreeSet是由红黑树实现的。


三、有哪些集合是线程不安全的?怎么解决呢?

提示:这块⽐较常问的是 Arraylist 和 Vector 、 HashMap 和 ConcurrentHashMap (⾼频问题,重要) 。被问到 Vector 的时候, 你紧接着可能会被问到 Arraylist 和 Vector 的区别。被问到 ConcurrentHashMap 的时候,你紧接着就可能会被问到 ConcurrentHashMap 相关的问题⽐如 ConcurrentHashMap 是如何保证线程安全的。

首先说单列集合里的ArrayList,它的线程是不安全的,双列集合Map里的HashMap是线程非安全的。而Vector是线程安全的,它们的区别在于线程是否安全,而Vector是远古实现类,现在基本不用了。ConcurrentHashMap是线程安全的,jdk1.8之前它是通过Segment 数组结构和 HashEntry 数组结构组成。通过给每一段加锁的方式来保证线程安全。而jdk1.8之后Node + CAS + synchronized来保证并发安全。
在这里插入图片描述

在这里插入图片描述

Java 8 中,锁粒度更细,synchronized 只锁定当前链表或红黑二叉树的首节点,这样只要 hash 不冲突,就不会产生并发,就不会影响其他 Node 的读写,效率大幅提升。


四、HashMap 查询,删除的时间复杂度

提示:1.没有哈希冲突的情况 2.转链表的情况 3.链表转红⿊树的情况

  1. 没有哈希冲突的情况

    • 时间复杂度:O(1)
    • 在理想情况下,如果没有哈希冲突,HashMap的查询和删除操作的时间复杂度是常数时间复杂度O(1),即平均情况下,它们的操作是非常快速的。
  2. 转链表的情况

    • 时间复杂度:O(n)
    • 当发生哈希冲突,即两个不同的键被映射到同一个桶(bucket)时,HashMap会在该桶上使用链表来存储这些键值对。在这种情况下,查询和删除操作的时间复杂度会退化为O(n),其中n是链表的长度。
  3. 链表转红黑树的情况

    • 时间复杂度:O(log n)
    • 为了避免链表过长导致性能下降,当链表长度达到一定阈值时,HashMap会将链表转换为红黑树(自平衡二叉搜索树)。在红黑树中,查询和删除操作的时间复杂度将变为O(log n),其中n是红黑树的节点数。

五、HashMap 的底层实现?

JDK1.8 之前 : 数组和链表、JDK1.8 之后 : 多了红⿊树

首先在jdk1.8之前,HashMap 底层是数组和链表结合在一起使用也就是链表散列。

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


六、HashMap 的⻓度为什么是 2 的幂次方

提示:提⾼运算效率。
为了能让 HashMap 存取高效,尽量较少碰撞,也就是要尽量把数据分配均匀。

取余(%)操作中如果除数是 2 的幂次则等价于与其除数减一的与(&)操作(也就是说 hash%length==hash&(length-1)的前提是 length 是 2 的 n 次方;)。并且 采用二进制位操作 &,相对于%能够提高运算效率,这就解释了 HashMap 的长度为什么是 2 的幂次方。


七、比较 HashSet 、 LinkedHashSet 和 TreeSet 三者的异同

提示:1.HashSet 、 LinkedHashSet 和 TreeSet 都是 Set 接⼝的实现类,都能保证元素唯⼀,并且都不是线程安全的。2.HashSet 、 LinkedHashSet 和 TreeSet 的主要区别在于底层数据结构不同(底层数据结构不同⼜导致这三者的应⽤场景不同)。

首先说一下他们的相同的点,他们都是Set接口的实现类,都能保证元素的唯一性,且都不还线程安全的。不同点在于由于他们的底层结构不同,导致它们的应用场景也不相同。具体而言HashSet 的底层数据结构是哈希表(基于 HashMap 实现)。LinkedHashSet 的底层数据结构是链表和哈希表,元素的插入和取出顺序满足 FIFO。TreeSet 底层数据结构是红黑树,元素是有序的,排序的方式有自然排序和定制排序。底层数据结构不同又导致这三者的应用场景不同。HashSet 用于不需要保证元素插入和取出顺序的场景,LinkedHashSet 用于保证元素的插入和取出顺序满足 FIFO 的场景,TreeSet 用于支持对元素自定义排序规则的场景。


八、HashMap 和 Hashtable 的区别? HashMap 和 HashSet 区别? HashMap 和 TreeMap 区别?ConcurrentHashMap 和 Hashtable 的区别?

提示:1.底层数据结构 2.实现线程安全的⽅式的区别.

首先HashMap与Hashtable相比,HashMap的底层实现是由数组加链表且链表会转化成红黑树(当链表的值大于8这个阈值,会先判断数组是否大于64,如果大于64则会将链表转化成红黑树,否则将数组扩容)实现。而hashtable则没有这个机制,而Hashmap是非线程安全的,而Hashtable是线程安全的。

HashMap与HashSet相比,首先他们的实现接口不一样HashMap实现Map接口,而HashSet实现Set接口,他们存储元素的结构不一样,HashMap存储的是键值对,而HashSet存储的是对象。它们计算hash的方式不一样,HashMap使用键来计算,而HashSet使用成员对象来计算,如果hashcode相同,则用equal()方法用来判断对象的相等性。

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


九、ConcurrentHashMap 线程安全的具体实现方式/底层具体实现

提示:JDK 1.7 : Segment 分段锁 JDK 1.8 : CAS 和 synchronized
ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的方式上不同。

  • 底层数据结构: JDK1.7 的 ConcurrentHashMap 底层采用 分段的数组+链表 实现,JDK1.8 采用的数据结构跟 HashMap1.8 的结构一样,数组+链表/红黑二叉树。Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用 数组+链表 的形式,数组是 HashMap 的主体,链表则是主要为了解决哈希冲突而存在的;

  • 实现线程安全的方式(重要):

    • 在 JDK1.7 的时候,ConcurrentHashMap 对整个桶数组进行了分割分段(Segment,分段锁),每一把锁只锁容器其中一部分数据(下面有示意图),多线程访问容器里不同数据段的数据,就不会存在锁竞争,提高并发访问率。
    • 到了 JDK1.8 的时候,ConcurrentHashMap 已经摒弃了 Segment 的概念,而是直接用 Node 数组+链表+红黑树的数据结构来实现,并发控制使用 synchronized 和 CAS 来操作。(JDK1.6 以后 synchronized 锁做了很多优化) 整个看起来就像是优化过且线程安全的 HashMap,虽然在 JDK1.8 中还能看到 Segment 的数据结构,但是已经简化了属性,只是为了兼容旧版本;
    • Hashtable(同一把锁) :使用 synchronized 来保证线程安全,效率非常低下。当一个线程访问同步方法时,其他线程也访问同步方法,可能会进入阻塞或轮询状态,如使用 put 添加元素,另一个线程不能使用 put 添加元素,也不能使用 get,竞争会越来越激烈效率越低。

这篇关于Java集合自测题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1055644

相关文章

JVM 的类初始化机制

前言 当你在 Java 程序中new对象时,有没有考虑过 JVM 是如何把静态的字节码(byte code)转化为运行时对象的呢,这个问题看似简单,但清楚的同学相信也不会太多,这篇文章首先介绍 JVM 类初始化的机制,然后给出几个易出错的实例来分析,帮助大家更好理解这个知识点。 JVM 将字节码转化为运行时对象分为三个阶段,分别是:loading 、Linking、initialization

Spring Security 基于表达式的权限控制

前言 spring security 3.0已经可以使用spring el表达式来控制授权,允许在表达式中使用复杂的布尔逻辑来控制访问的权限。 常见的表达式 Spring Security可用表达式对象的基类是SecurityExpressionRoot。 表达式描述hasRole([role])用户拥有制定的角色时返回true (Spring security默认会带有ROLE_前缀),去

浅析Spring Security认证过程

类图 为了方便理解Spring Security认证流程,特意画了如下的类图,包含相关的核心认证类 概述 核心验证器 AuthenticationManager 该对象提供了认证方法的入口,接收一个Authentiaton对象作为参数; public interface AuthenticationManager {Authentication authenticate(Authenti

Spring Security--Architecture Overview

1 核心组件 这一节主要介绍一些在Spring Security中常见且核心的Java类,它们之间的依赖,构建起了整个框架。想要理解整个架构,最起码得对这些类眼熟。 1.1 SecurityContextHolder SecurityContextHolder用于存储安全上下文(security context)的信息。当前操作的用户是谁,该用户是否已经被认证,他拥有哪些角色权限…这些都被保

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明(认真看哦) AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证,则会调用 #attemptAuthentica

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门(一):登录与退出》 《Spring-Security-入门(二):基于数据库验证》 《Spring-Security-入门(三):密码加密》 《Spring-Security-入门(四):自定义-Filter》 《Spring-Security-入门(五):在 Sprin

Java架构师知识体认识

源码分析 常用设计模式 Proxy代理模式Factory工厂模式Singleton单例模式Delegate委派模式Strategy策略模式Prototype原型模式Template模板模式 Spring5 beans 接口实例化代理Bean操作 Context Ioc容器设计原理及高级特性Aop设计原理Factorybean与Beanfactory Transaction 声明式事物

Java进阶13讲__第12讲_1/2

多线程、线程池 1.  线程概念 1.1  什么是线程 1.2  线程的好处 2.   创建线程的三种方式 注意事项 2.1  继承Thread类 2.1.1 认识  2.1.2  编码实现  package cn.hdc.oop10.Thread;import org.slf4j.Logger;import org.slf4j.LoggerFactory

JAVA智听未来一站式有声阅读平台听书系统小程序源码

智听未来,一站式有声阅读平台听书系统 🌟 开篇:遇见未来,从“智听”开始 在这个快节奏的时代,你是否渴望在忙碌的间隙,找到一片属于自己的宁静角落?是否梦想着能随时随地,沉浸在知识的海洋,或是故事的奇幻世界里?今天,就让我带你一起探索“智听未来”——这一站式有声阅读平台听书系统,它正悄悄改变着我们的阅读方式,让未来触手可及! 📚 第一站:海量资源,应有尽有 走进“智听

在cscode中通过maven创建java项目

在cscode中创建java项目 可以通过博客完成maven的导入 建立maven项目 使用快捷键 Ctrl + Shift + P 建立一个 Maven 项目 1 Ctrl + Shift + P 打开输入框2 输入 "> java create"3 选择 maven4 选择 No Archetype5 输入 域名6 输入项目名称7 建立一个文件目录存放项目,文件名一般为项目名8 确定