苏州网站制作计划,重庆装修公司避坑指南,网站设计 注意,中华网军事网这里写目录标题 Collection 接口List 接口ArrayList 简述 1. ArrayList 和 LinkedList 区别#xff1f;⭐️⭐️⭐️⭐️2. ArrayList 和 Array 的区别#xff1f;⭐️⭐️⭐️ArrayList 和 Vector 区别#xff1f;⭐️⭐️ArrayList 的扩容机制#xff1f;⭐️⭐️⭐️ Qu… 这里写目录标题 Collection 接口List 接口ArrayList 简述 1. ArrayList 和 LinkedList 区别⭐️⭐️⭐️⭐️2. ArrayList 和 Array 的区别⭐️⭐️⭐️ArrayList 和 Vector 区别⭐️⭐️ArrayList 的扩容机制⭐️⭐️⭐️ Queue 接口1. Queue和Deque的区别⭐️⭐️⭐️2. ArrayDeque与LinkedList区别⭐️⭐️⭐️3. PriorityQueue有什么特点⭐️⭐️⭐️ Set 接口 Map 接口简述HashMap1HashMap查询、删除的时间复杂度⭐️⭐️⭐️⭐️2HashMap的底层实现⭐️⭐️⭐️⭐️⭐️ 1. HashMap和HashTable的区别2. HashMap和HashSet区别⭐️⭐️⭐️⭐️3. HashMap和TreeMap的区别⭐️⭐️⭐️⭐️4. CocurrentHashMap线程安全的具体实现方式/底层具体实现⭐️⭐️⭐️⭐️ 本文是基于javaGuide的学习和自我总结 集合有两大接口Collection和MapCollection中存单一元素Map中存放kv对 图片 from javaGuide Collection 接口
List 接口 ArrayList 简述
public class ArrayListE extends AbstractListEimplements ListE, 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会默认在末尾追加元素时间复杂度是O1
执行add(int index, E element)ArrayList会让第i个及以后元素 全部移动一位时间复杂度是OnListedList 采用链表存储插入、删除头尾元素不受影响指定索引的插入删除操作受影响 执行add(E e) addFirst(E e)addLast(E e)removeFirst()removeLast() 时间复杂度为O1
执行add(int index, E element) remove(Object o) remove(int index)时间复杂度为On因为需要先移动到指定位置再插入和删除 是否支持快速随机访问 ArrayList 支持 -- 实现了RandomAccess的接口 ListedList不支持 内存空间占用 ArrayList 的空间浪费主要体现在 : list列表结尾会预留一定容量的空间LinkedList 的空间花费则体现在 : 每个元素都需要消耗比ArrayList更多的空间 (因为都要存放直接后继和直接前驱以及数据) 2. ArrayList 和 Array 的区别⭐️⭐️⭐️
Array Array(数组) 就是一个可以自定义固定长度的数组 , 只能按照下标访问元素 , Array里面没有定义什么便于使用的方法 最常用的可能就是Array.length() 和 Array.sort() ArrayList ArrayListInteger 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()方法
/*** 要分配的最大数组大小*/
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 QueueE extends CollectionE {...}Deque : public interface DequeE extends QueueE {...}Deque继承了Queue接口并且扩展了在队头和队尾增删元素的方法事实上Deque还提供有push和pop等其他方法可用于模拟栈 2. ArrayDeque与LinkedList区别⭐️⭐️⭐️
ArrayDeque和LinkedList都继承了Deque两者有什么不同吗 ArrayDeque ArrayDeque是基于可变数组和双指针实现的LinkedList是基于链表实现 //ArrayDeque
transient Object[] elements; //数组
transient int head; //头指针
transient int tail; //尾指针ArrayDeque 不能添加null值原因如下源码LinkedList可以 public void addFirst(E e) {if (e null)throw new NullPointerException();elements[head (head - 1) (elements.length - 1)] e;if (head tail)doubleCapacity();
}ArrayDeque是在jdk1.6才被引入的LinkedList早就存在ArrayDeque 插入时存在扩容过程ArrayDeque性能更好 图片 from javaGuide
3. PriorityQueue有什么特点⭐️⭐️⭐️ 特点元素出队顺序是与优先级相关的即总是优先级最高的元素先出队 PriorityQueue会出现在手撕算法应用当中 --》堆排序、第K大的数、带权图的遍历等
Set 接口
Map 接口 简述HashMap
Map里面存放的是KV对且Key值不可重复这一点很重要事关HashSet为啥不可重复因为HashSet直接把值存到Key上了Value则赋值为一个虚拟的Object对象这篇文章很详细不过比较老了深入Java集合学习系列HashMap的实现原理
1HashMap查询、删除的时间复杂度⭐️⭐️⭐️⭐️
如果没有元素 处理直接插入元素或者直接返回未找到 时间复杂度O1 如果有元素链表 处理沿着链表遍历 时间复杂度On 红黑树 时间复杂度Olongn 2HashMap的底层实现⭐️⭐️⭐️⭐️⭐️ 基于Map接口实现 public class HashMapK,V extends AbstractMapK,Vimplements MapK,V, Cloneable, Serializable {...}非线程安全HashMap的存储方法解决哈希冲突 - JDK1.8之前HashMap由 数组链表 组成的数组是HashMap的主题链表则主要是为了解决哈希冲突而存在的“拉链法”
- JDK1.8以后得HashMap在解决哈希冲突时有了较大的变化
-- 当链表的长度大于等于阈值默认为8时
-- 会判断当前数组的长度是否小于64
-- 如果小于64则先进行数组扩容
-- 如果大于64则将链表转化为红黑树以减少搜索时间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区别⭐️⭐️⭐️⭐️
HashSetObject objects new HashSet();
HashMapObject, Object objectObjectHashMap new HashMap();区别 HashMap里面存的是KV对 HashSet里存的是对象 HashMap的Key不可重复Value可重复HashSet不可重复 HashSet的add方法调用了HashMap中的put方法 // HashSet部分源码
public class HashSetEextends AbstractSetEimplements SetE, Cloneable, java.io.Serializable
{static final long serialVersionUID -5024744406713321676L;private transient HashMapE,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 ttHashMap/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
public class HashMapK,V extends AbstractMapK,Vimplements MapK,V, Cloneable, Serializable {//TreeMap
public class TreeMapK,Vextends AbstractMapK,Vimplements NavigableMapK,V, Cloneable, java.io.SerializableTreeMap实现了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及以后
