Java集合(八股)

news/2024/12/23 0:24:33/

这里写目录标题

  • Collection 接口
    • List 接口
        • ArrayList 简述
      • 1. ArrayList 和 LinkedList 区别?⭐️⭐️⭐️⭐️
      • 2. ArrayList 和 Array 的区别?⭐️⭐️⭐️
      • ArrayList 和 Vector 区别?⭐️⭐️
      • ArrayList 的扩容机制?⭐️⭐️⭐️
    • Queue 接口
      • 1. Queue和Deque的区别?⭐️⭐️⭐️
      • 2. ArrayDeque与LinkedList区别?⭐️⭐️⭐️
      • 3. PriorityQueue有什么特点?⭐️⭐️⭐️
    • Set 接口
  • Map 接口
    • 简述HashMap
      • (1)HashMap查询、删除的时间复杂度⭐️⭐️⭐️⭐️
      • (2)HashMap的底层实现⭐️⭐️⭐️⭐️⭐️
    • 1. HashMap和HashTable的区别
    • 2. HashMap和HashSet区别⭐️⭐️⭐️⭐️
    • 3. HashMap和TreeMap的区别?⭐️⭐️⭐️⭐️
    • 4. CocurrentHashMap线程安全的具体实现方式/底层具体实现⭐️⭐️⭐️⭐️

!!!本文是基于javaGuide的学习和自我总结!!!

集合有两大接口CollectionMap,Collection中存单一元素,Map中存放kv对
from <a class=javaGuide" />
(图片 from javaGuide)

Collection 接口

List 接口

在这里插入图片描述

ArrayList 简述
java">public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable{...}

ArrayList
继承了AbstractList类;
实现了ListRandomAccessCloneableSerializable接口

  • List:表明他是一个列表,支持增删查等操作、
  • RandomAccess:表明List集合是支持快速随机访问
注:
这只是一个标志接口,不是实现了它就能快速随机访问,
还要看类的底层逻辑
(如LinkedList就算继承了RandomAccess,也无法实现随机访问,因为它底层是链表,内存地址是不连续的 , 所以注定不可能)
  • Cloneable:表明它具有拷贝能力,可以进行深拷贝和浅拷贝
  • Serializable:表明它可以进行序列化操作,也就是可以将对象转换为字节流进行持久化存储或网络传输

1. ArrayList 和 LinkedList 区别?⭐️⭐️⭐️⭐️

首先说明 :
貌似绝大多数情况都是使用ArrayList , 就算是需要用到LinkedList的情况 ,也是可以用ArrayList替代掉的 , 且性能会更好
在这里插入图片描述

  • 是否线程安全

都不是线程安全的,因为他俩都是不同步的(源码中没有任何“同步”的想法)

  • 底层数据结构
  • ArrayList 底层使用的是Object数组
  • ListedList 底层使用的是双向链表
  • 插入和删除是否受元素位置的影响
  • ArrayList 采用数组存储,所以插入和删除的时间复杂度 受元素位置的影响。
比如:
执行 `add(E e)`方法时,ArrayList会默认在末尾追加元素,时间复杂度是O(1)
执行`add(int index, E element)`,ArrayList会让第i个及以后元素 全部移动一位,时间复杂度是O(n)
  • ListedList 采用链表存储,插入、删除头尾元素不受影响,指定索引的插入删除操作受影响
执行`add(E e)` `addFirst(E e)``addLast(E e)``removeFirst()``removeLast()` 时间复杂度为O(1)
执行`add(int index, E element)` `remove(Object o)` `remove(int index)`时间复杂度为O(n),因为需要先移动到指定位置再插入和删除 
  • 是否支持快速随机访问

ArrayList 支持 --> 实现了RandomAccess的接口
ListedList不支持

  • 内存空间占用
  • ArrayList 的空间浪费主要体现在 : list列表结尾会预留一定容量的空间
  • LinkedList 的空间花费则体现在 : 每个元素都需要消耗比ArrayList更多的空间 (因为都要存放直接后继和直接前驱以及数据)

2. ArrayList 和 Array 的区别?⭐️⭐️⭐️

  • Array

Array(数组) 就是一个可以自定义固定长度数组 , 只能按照下标访问元素 , Array里面没有定义什么便于使用的方法
最常用的可能就是Array.length() 和 Array.sort()

  • ArrayList
    ArrayList<Integer> list = new ArrayList();

ArrayList 内置了丰富的API操作方法 , 比如add() , remove()等
它会根据实际存储的元素动态扩容
允许使用泛型 来确保类型安全
只能存储对象

ArrayList 和 Vector 区别?⭐️⭐️

它们底层都是使用Object()存储

  • Vector比较老了 , 但它是线程安全的(很少使用了)
  • ArrayList , 适用于频繁的查找工作 ; 线程不安全

ArrayList 的扩容机制?⭐️⭐️⭐️

  • ArrayList的默认长度是10,当然也可以自定义
  • 当数组存储的元素 数量大于10的时候,就会触发扩容机制(也就是grow()方法)
  • grow()方法 会创建一个新的数组,这个新数组的长度大约是原来的1.5倍(grow中的移位运算 算出来的)
  • 然后通过Arrays.copyOf()方法将老数组赋值到新数组当中
  • 以此类推

ArrayList的扩容机制的核心其实是grow()方法

java">/*** 要分配的最大数组大小*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;/*** ArrayList扩容的核心方法。*/
private void grow(int minCapacity) {// oldCapacity为旧容量,newCapacity为新容量int oldCapacity = elementData.length;// 将oldCapacity 右移一位,其效果相当于oldCapacity /2,// 我们知道位运算的速度远远快于整除运算,整句运算式的结果就是将新容量更新为旧容量的1.5倍,int newCapacity = oldCapacity + (oldCapacity >> 1);// 然后检查新容量是否大于最小需要容量,若还是小于最小需要容量,那么就把最小需要容量当作数组的新容量,if (newCapacity - minCapacity < 0)newCapacity = minCapacity;// 如果新容量大于 MAX_ARRAY_SIZE,进入(执行) `hugeCapacity()` 方法来比较 minCapacity 和 MAX_ARRAY_SIZE,// 如果minCapacity大于最大容量,则新容量则为`Integer.MAX_VALUE`,否则,新容量大小则为 MAX_ARRAY_SIZE 即为 `Integer.MAX_VALUE - 8`。if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);// minCapacity is usually close to size, so this is a win:elementData = Arrays.copyOf(elementData, newCapacity);
}

Queue 接口

在这里插入图片描述

1. Queue和Deque的区别?⭐️⭐️⭐️

主要区别就是

Queue是单端队列
Deque是双端队列

本质上

  • Queue : public interface Queue<E> extends Collection<E> {...}
  • Deque : public interface Deque<E> extends Queue<E> {...}
  • Deque继承了Queue接口,并且扩展了在队头和队尾增删元素的方法
  • 事实上,Deque还提供有push()和pop()等其他方法,可用于模拟栈

2. ArrayDeque与LinkedList区别?⭐️⭐️⭐️

ArrayDeque和LinkedList都继承了Deque,两者有什么不同吗?

  • ArrayDeque
  1. ArrayDeque是基于可变数组和双指针实现的;LinkedList是基于链表实现
java">//ArrayDeque
transient Object[] elements;	//数组	
transient int head;	//头指针
transient int tail;	//尾指针
  1. ArrayDeque 不能添加null值,原因如下(源码);LinkedList可以
java">public void addFirst(E e) {if (e == null)throw new NullPointerException();elements[head = (head - 1) & (elements.length - 1)] >= e;if (head == tail)doubleCapacity();
}
  1. ArrayDeque是在jdk1.6才被引入的;LinkedList早就存在
  2. ArrayDeque 插入时存在扩容过程
  3. ArrayDeque性能更好

图片 from javaGuide
在这里插入图片描述

3. PriorityQueue有什么特点?⭐️⭐️⭐️

特点:元素出队顺序是与优先级相关的,即总是优先级最高的元素先出队

PriorityQueue会出现在手撕算法应用当中 --》堆排序、第K大的数、带权图的遍历等

Set 接口

Map 接口

在这里插入图片描述

简述HashMap

  • Map里面存放的是KV对,且Key值不可重复(这一点很重要,事关HashSet为啥不可重复,因为HashSet直接把值存到Key上了,Value则赋值为一个虚拟的Object对象)
  • 这篇文章很详细,不过比较老了:深入Java集合学习系列:HashMap的实现原理

(1)HashMap查询、删除的时间复杂度⭐️⭐️⭐️⭐️

  • 如果没有元素

处理:直接插入元素或者直接返回未找到
时间复杂度:O(1)

  • 如果有元素(链表)

处理:沿着链表遍历
时间复杂度:O(n)

  • 红黑树

时间复杂度O(longn)

(2)HashMap的底层实现⭐️⭐️⭐️⭐️⭐️

  1. 基于Map接口实现
java">public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable {...}
  1. 非线程安全
  2. HashMap的存储方法;解决哈希冲突
- JDK1.8之前,HashMap由 数组+链表 组成的,数组是HashMap的主题,链表则主要是为了解决哈希冲突而存在的(“拉链法”);
- JDK1.8以后得HashMap在解决哈希冲突时有了较大的变化,
-- 当链表的长度大于等于阈值(默认为8)时,
-- 会判断当前数组的长度是否小于64,
-- 如果小于64,则先进行数组扩容,
-- 如果大于64,则将链表转化为红黑树,以减少搜索时间
  1. HashMap默认初始化大小为16,之后每次扩充,容量变为原来的2倍。并且,HashMap总是使用2的幂作为哈希表的大小

1. HashMap和HashTable的区别

注 : HashTable基本被淘汰了

  • 线程安全

HashMap 线程不安全
HashTable 线程安全(HashTable内的方法基本都被synchronized修饰)

  • 效率

因为线程安全问题,所以HashTable的效率会低一些

  • 对Null key和Null value的支持

HashMap可以存储null的key和value,但null作为键只能有一个,null作为值可以有多个
HashTable不允许有null键和null值

  • 其他区别可以从上面写的HashMap来说(HashTable几乎不用了)

2. HashMap和HashSet区别⭐️⭐️⭐️⭐️

java">HashSet<Object> objects = new HashSet();
HashMap<Object, Object> objectObjectHashMap = new HashMap();
  • 区别:

HashMap里面存的是KV对 ;HashSet里存的是对象
HashMap的Key不可重复,Value可重复;HashSet不可重复
HashSet的add方法调用了HashMap中的put方法

// HashSet部分源码

java">public class HashSet<E>extends AbstractSet<E>implements Set<E>, Cloneable, java.io.Serializable
{static final long serialVersionUID = -5024744406713321676L;private transient HashMap<E,Object> map;// Dummy value to associate with an Object in the backing Mapprivate static final Object PRESENT = new Object();/*** Constructs a new, empty set; the backing <tt>HashMap</tt> instance has* default initial capacity (16) and load factor (0.75).*/public HashSet() {map = new HashMap<>();}...// 这里,调用了map的put方法,把e存到key上---》不能重复public boolean add(E e) {return map.put(e, PRESENT)==null;}
}

可以看出,HashSet底层就是基于HashMap实现的(HashSet的源码非常少,因为除了clone() , writeObject() , readObject() 是HashSet自己不得不实现之外,其他方法都是直接调用HashMap中的方法)

3. HashMap和TreeMap的区别?⭐️⭐️⭐️⭐️

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

//HashMap

java">public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable {

//TreeMap

java">public class TreeMap<K,V>extends AbstractMap<K,V>implements NavigableMap<K,V>, Cloneable, java.io.Serializable
  • TreeMap实现了NavigableMap接口

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

  • NavigableMap接口提供了丰富的方法来探索和操作键值对
  • TreeMap实现了SortedMap接口

实现SortedMap接口让TreeMap有了对集合中的元素根据键排序的能力。

  • 默认是按照key的升序排序,不过我们也可以指定排序的比较器

4. CocurrentHashMap线程安全的具体实现方式/底层具体实现⭐️⭐️⭐️⭐️

分两个阶段——jdk1.8之前;1.8及以后

  • jdk1.8以前
    在这里插入图片描述

首先将数据分成一段一段(这个“端”就是Segment)的存储,然后给每一段数据配一把锁,当一个线程占用锁访问其中一个段数据时,其他段的数据也能被其他线程访问

ConcurrentHashMap是由Segment数据结构和HashEntry数据结构组成

Segment的结构和1.8以前的HashMap类似
在这里插入图片描述

  • jdk1.8及以后
    在这里插入图片描述
    在这里插入图片描述

http://www.ppmy.cn/news/1526634.html

相关文章

sqli-labs靶场自动化利用工具——第6关

文章目录 概要整体架构流程技术细节执行效果小结 概要 Sqli-Labs靶场对于网安专业的学生或正在学习网安的朋友来说并不陌生&#xff0c;或者说已经很熟悉。那有没有朋友想过自己开发一个测试脚本能实现自动化化测试sqli-labs呢&#xff1f;可能有些人会说不是有sqlmap&#…

烧结机等调速系统电气设计-大作业/毕设

目录 1. 主要任务2.设计框架原理部分举例&#xff1a;选型部分举例&#xff1a;方案设计部分举例&#xff1a; 3. 交流讨论 1. 主要任务 以烧结机为例&#xff0c;设计基于PLC控制变频器对烧结机的调速系统的设计。主要运用了变频器&#xff0c;PLC等设备。并基于某型号变频器…

什么是 HTTP/3?下一代 Web 协议

毫无疑问&#xff0c;发展互联网底层的庞大协议基础设施是一项艰巨的任务。 HTTP 的下一个主要版本基于 QUIC 协议构建&#xff0c;并有望提供更好的性能和更高的安全性。 以下是 Web 应用程序开发人员需要了解的内容。 HTTP/3 的前景与风险 HTTP/3 致力于让互联网对每个人…

SpringBoot教程(安装篇) | RabbitMQ的安装

SpringBoot教程&#xff08;安装篇&#xff09; | RabbitMQ的安装 一、下载RabbitMQ&#xff08;windows版本&#xff09;1. 先下载 RabbitMQ2. 再下载Erlang3. 开始安装 Erlang4. 为Erlang配置环境变量5、验证安装6. 开始安装 RabbitMQ7. 启用RabbitMQ的管理插件&#xff08;图…

Python Pyvis库创建交互式网络图 高级功能详解

文章目录 动态网络图图布局调整扩展到大规模网络动态网络图 Pyvis支持创建动态网络图,通过时间轴展示网络图的演化过程。 需要使用set_options函数,参数必须为json格式。动态网络图支持添加点和边。 下面是一个简单的动态网络图示例: # 动态网络图示例 from pyvis.networ…

小程序开发设计-第一个小程序:创建小程序项目④

上一篇文章导航&#xff1a; 小程序开发设计-第一个小程序&#xff1a;安装开发者工具③-CSDN博客https://blog.csdn.net/qq_60872637/article/details/142219152?spm1001.2014.3001.5501 须知&#xff1a;注&#xff1a;不同版本选项有所不同&#xff0c;并无大碍。 一、创…

胤娲科技:解锁AI奥秘——产品经理的智能进化之旅

当AI不再是遥不可及的科幻 想象一下&#xff0c;你走进一家未来感十足的咖啡厅&#xff0c;无需言语&#xff0c;智能咖啡机就能根据你的偏好调制出一杯完美的拿铁&#xff1b; 打开手机&#xff0c;AI助手不仅提醒你今天有雨&#xff0c;还贴心推荐了最适合雨中漫步的音乐列表…

Golang使用ReverseProxy实现反向代理

目录 1.源码结构体 2.官方单机示例 3.使用示例 4.简单的http服务&#xff08;用于测试&#xff09; 1.源码结构体 type ReverseProxy struct {// Rewrite 必须是一个函数&#xff0c;用于将请求修改为要使用 Transport 发送的新请求。然后&#xff0c;其响应将原封不动地…