集合总结

Nov 26, 2023
Java基础

概括

ArrayList 默认初始容量10 内部数组对象存储扩容为当前容量的1.5倍排序采用快排

HashMap 默认初始16 负载因子0.75 扩容为当前容量的2倍采用链表+红黑树链表长度大于8转为红黑树小于6转为链表, computeIfAbsent value 不为null 进行计算赋值 computeIfPresent 为null 删除，不为null 替换， compute 不为null替换，为null 新增

ConcurrentHashMap 先cas 不成功说明位置已被抢占，此时那当前根节点（也就是桶）加锁，往后面续

HashSet 内部保存了一个HashMap 存储的key为保存的值。value是一个没用的对象

ArrayDeque 初始大小16 扩容为当前容量的2倍采用数组存储采用头尾指针头尾指针相遇时扩容为当前容量的2倍

ArrayBlockingQueue add(加不进去抛异常) offer(加不进去false) put(加不进去阻塞) 内部一把锁，两个condition 互相唤醒

LinkedBlockingQueue 双锁读写分离，因为他是链表，所以读写可以不用同一把锁, put，达到最大容量wait，唤醒一个等待线程，如果还小继续唤醒，结束的时候判断是count 是否为0，如果为0，则代表新增了一个，唤醒一个take线程

CopyOnWriteArrayList add 加锁复制一份，此时get 不受影响，读取的是复制的array

Arraylist与LinkedList异同

是否保证线程安全： ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；
底层数据结构： Arraylist 底层使用的是Object数组；LinkedList 底层使用的是双向链表数据结构（JDK1.6之前为循环链表，JDK1.7取消了循环。注意双向链表和双向循环链表的区别：）；详细可阅读JDK1.7-LinkedList循环链表优化
插入和删除是否受元素位置的影响： ① ArrayList 采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。比如：执行 add(E e) 方法的时候， ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是O(1)。但是如果要在指定位置 i 插入和删除元素的话（ add(int index, E element) ）时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。 ② LinkedList 采用链表存储，所以插入，删除元素时间复杂度不受元素位置的影响，都是近似 O（1）而数组为近似 O（n）。
是否支持快速随机访问： LinkedList 不支持高效的随机元素访问，而 ArrayList 支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于 get(int index) 方法)。
内存空间占用： ArrayList的空间浪费主要体现在在list列表的结尾会预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗比ArrayList更多的空间（因为要存放直接后继和直接前驱以及数据）。

补充内容:RandomAccess接口

public interface RandomAccess {
}

查看源码我们发现实际上 RandomAccess 接口中什么都没有定义。所以，在我看来 RandomAccess 接口不过是一个标识罢了。标识什么？标识实现这个接口的类具有随机访问功能。在binarySearch（）方法中，它要判断传入的list 是否RamdomAccess的实例，如果是，调用 indexedBinarySearch（）方法，如果不是，那么调用iteratorBinarySearch（）方法

public static <T>
    int binarySearch(List<? extends Comparable<? super T>> list, T key) {
    if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
    return Collections.indexedBinarySearch(list, key);
    else
    return Collections.iteratorBinarySearch(list, key);
}

ArrayList 实现了 RandomAccess 接口，而 LinkedList 没有实现。为什么呢？我觉得还是和底层数据结构有关！ ArrayList 底层是数组，而 LinkedList 底层是链表。数组天然支持随机访问，时间复杂度为 O（1），所以称为快速随机访问。链表需要遍历到特定位置才能访问特定位置的元素，时间复杂度为 O（n），所以不支持快速随机访问。ArrayList 实现了 RandomAccess 接口，就表明了他具有快速随机访问功能。 RandomAccess 接口只是标识，并不是说 ArrayList 实现 RandomAccess 接口才具有快速随机访问功能的！****

下面再总结一下 list 的遍历方式选择：实现了RandomAccess接口的list，优先选择普通for循环，其次foreach,未实现RandomAccess接口的list，优先选择iterator遍历（foreach遍历底层也是通过iterator实现的），大size的数据，千万不要使用普通for循环补充：数据结构基础之双向链表双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表，如下图所示，同时下图也是LinkedList 底层使用的是双向循环链表数据结构。

ArrayList 与 Vector 区别

Vector类的所有方法都是同步的。可以由两个线程安全地访问一个Vector对象、但是一个线程访问Vector的话代码要在同步操作上耗费大量的时间。

Arraylist不是同步的，所以在不需要保证线程安全时时建议使用Arraylist。