首页  思维导图  详情

集合

2021-05-29 12:33:12   1  举报





AI智能生成

java集合

java 集合 Collections

作者其他创作

大纲/内容

Collection

List 有序，可重复

ArrayList

ArrayList就是数组列表，主要用来装载数据，当我们装载的是基本类型的数据int，long，boolean，short，byte…的时候我们只能存储他们对应的包装类 arraylist可以存null吗?  ArrayList存储的类型是object,null属于object类型。

和LinkedList相比，它的查找和访问元素的速度较快，但新增，删除的速度较慢。

特点：ArrayList底层是用数组实现的存储，查询效率高，增删效率低，线程不安全。使用频率很高

初始化大小

ArrayList可以通过构造方法在初始化的时候指定底层数组的大小,不会初始化数组大小(就是指定为8，但size为0)，只有add数据后，才会真正分配 通过无参构造方法的方式ArrayList()初始化，则赋值底层数Object[] elementData为一个默认空数组Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}所以数组容量为0，只有真正对数据进行添加add时，才分配默认DEFAULT_CAPACITY = 10的初始容量。

扩容

扩容1.5倍，通过数组扩容的方式,比如我们现在有一个长度为10的数组，现在我们要新增一个元素，发现已经满了,重新定义一个长度为10+10/2的数组也就是新增一个长度为15的数组,然后把原数组的数据，原封不动的复制到新数组中，这个时候再把指向原数的地址换到新数组，ArrayList就这样完成了一次改头换面。

新增

在这之前他会有一步校验长度的判断ensureCapacityInternal，就是说如果长度不够，是需要扩容的

在扩容的时候，老版本的jdk和8以后的版本是有区别的，8之后的效率更高了，采用了位运算，右移一位，其实就是除以2这个操作。

在校验之后就是数组的copy,System.arraycopy()

删除

删除其实跟新增是一样的，不过叫是叫删除，但是在代码里面我们发现，他还是在copy一个数组。

线程不安全

Vector 已废弃

Collections.synchronizedList

juc 包下的CopyOnWriteArrayList

ArrayList不适合做队列，数组适合用来做队列

遍历

论遍历ArrayList要比LinkedList快得多，ArrayList遍历最大的优势在于内存的连续性，CPU的内部缓存结构会缓存连续的内存片段，可以大幅降低读取内存的性能开销。

两种数组复制方法的区别在于： arraycopy()需要目标数组，将原数组拷贝到你自己定义的数组里，而且可以选择拷贝的起点和长度以及放入新数组中的位置 copyOf()是系统自动在内部新建一个数组，调用arraycopy()将original内容复制到copy中去，并且长度为newLength。返回copy; 即将原数组拷贝到一个长度为newLength的新数组中，并返回该数组。 总结 Array.copyOf()可以看作是受限的System.arraycopy(),它主要是用来将原数组全部拷贝到一个新长度的数组，适用于数组扩容。

LinkedList

底层是双向链表，只能从头开始逐个遍历

Vector

底层也是用数组来实现的，基本每个方法都加Synchronized,已经废弃了

List 的实现方式有 LinkedList 和 ArrayList 两种，那面试时最常问的就是这两个数据结构如何选择。

一是考虑数据结构是否能完成需要的功能； 如果都能完成，二是考虑哪种更高效。

Vector 和 ArrayList 的区别是什么

线程安全

默认情况下它是扩容两倍。

Set 无序，不重复

HashSet

采用 Hashmap 的 key 来储存元素，主要特点是无序的，基本操作都是 O(1) 的时间复杂度，很快。

LinkedHashSet

HashSet + LinkedList 的结构，特点就是既拥有了 O(1) 的时间复杂度，又能够保留插入的顺序。

SortedSet

TreeSet

采用红黑树结构，特点是可以有序，可以用自然排序或者自定义比较器来排序；缺点就是查询速度没有 HashSet 快。

Queue 队列，先进先出

LinkedList

实现「普通队列 - 先进先出」的语义

Deque

ArrayDeque

实现「普通队列 - 先进先出」和栈的语义

PriorityQueue（特殊，heap）

实现「优先队列」的语义

基本API

如何选择用 LinkedList 还是 ArrayDeque 呢？

总结来说就是推荐使用 ArrayDeque，因为效率高，而 LinkedList 还会有其他的额外开销（overhead）。

那 ArrayDeque 和 LinkedList 的区别有哪些呢？

ArrayDeque 是一个可扩容的数组，LinkedList 是链表结构； ArrayDeque 里不可以存 null 值，但是 LinkedList 可以； ArrayDeque 在操作头尾端的增删操作时更高效，但是 LinkedList 只有在当要移除中间某个元素且已经找到了这个元素后的移除才是 O(1) 的； ArrayDeque 在内存使用方面更高效。 所以，只要不是必须要存 null 值，就选择 ArrayDeque 吧！

Map

HashMap 与 HashSet 对应，也是无序的，O(1)。

由数组和链表组合构成的数据结构,允许使用 null 值和 null 键

我们都知道数组长度是有限的，在有限的长度里面我们使用哈希，哈希本身就存在概率性，就是”帅丙“和”丙帅“我们都去hash有一定的概率会一样，就像上面的情况我再次哈希”丙帅“极端情况也会hash到一个值上，那就形成了链表。

每一个节点都会保存自身的hash、key、value、以及下个节点

新的Entry节点在插入链表的时候，插入方式

jdk 8之前是头插法

同一位置上新元素总会被放在链表的头部位置，会改变链表的上的顺序。 在旧数组中同一条Entry链上的元素，通过重新计算索引位置后，有可能被放到了新数组的不同位置上。 会造成无限循环的问题

jdk8之后是尾插法

在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题了。

扩容机制 数组容量是有限的，数据多次插入的， 到达一定的数量就会进行扩容，也就是resize。

因素

Capacity：HashMap当前长度。 LoadFactor：负载因子，默认值0.75f。

扩容

分为两步 扩容：创建一个新的Entry空数组，长度是原数组的2倍。 ReHash：遍历原Entry数组，把所有的Entry重新Hash到新数组

为什么要重新哈希？ 因为长度扩大以后，Hash的规则也随之改变。 Hash的公式---> index = HashCode（Key） & （Length - 1）

初始化大小为16

为了位运算的方便，位与运算比算数计算的效率高了很多

实现均匀分布。 只要输入的HashCode本身分布均匀，Hash算法的结果就是均匀的。

链表有红黑树

二叉树

1.左子树上所有结点的值均小于或等于它的根结点的值。 2.右子树上所有结点的值均大于或等于它的根结点的值。 3.左、右子树也分别为二叉排序树。

当二叉树多次插入新的节点，导致的不平衡，红黑树应用而生。

1.节点是红色或黑色。 2.根节点是黑色。 3.每个叶子节点都是黑色的空节点（NIL节点）。 4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点) 5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

如何保证红黑树始终是红黑树

变色

旋转

在极限状态下,HashMap在同一索引中放入第十一个元素时才会转变为红黑二叉树 那么由此我们会想为什么会这样呢?Java中明明预设了阈值"8",怎么会到第十一才转为红黑二叉树呢? 其实在HashMap中存在扩容机制, 它一开始默认是长度为16的数组, 当某一个索引中的元素超过到8时,它优先会选择将长度扩容2倍(即长度为32)的数组, 它会认为是不是由于数组的长度不够才导致一个索引中元素过多; 但当它发现长度为32时,某一个索引中的元素还是超过9时, 它还是会优先选择将长度再次扩容到2倍(即长度为64)的数组, 在长度为64的数组中,它发现某一个索引中的元素还是超过10时,它就会对该索引所在的链表转化为红黑二叉树. 所以在第十一个元素时,就会对该索引所在的链表转化为红黑二叉树.

为啥我们重写equals方法的时候 需要重写hashCode方法呢？

在java中，所有的对象都是继承于Object类。Object类中有两个方法equals、hashCode，这两个方法都是用来比较两个对象是否相等的

在未重写equals方法我们是继承了object的equals方法，那里的 equals是比较两个对象的内存地址，显然我们new了2个对象内存地址肯定不一样 对于值对象，==比较的是两个对象的值 对于引用对象，比较的是两个对象的地址

大家是否还记得我说的HashMap是通过key的hashCode去寻找index的，那index一样就形成链表了，也就是说”帅丙“和”丙帅“的index都可能是2，在一个链表上的。 我们去get的时候，他就是根据key去hash然后计算出index，找到了2，那我怎么找到具体的”帅丙“还是”丙帅“呢？ equals！是的，所以如果我们对equals方法进行了重写，建议一定要对hashCode方法重写，以保证相同的对象返回相同的hash值，不同的对象返回不同的hash值。

线程不安全，线程安全需使用

HashTable

适合在多线程的情况下使用，但是效率可不太乐观。 对数据操作的时候都会上锁，所以效率比较低下。

CurrentHashMap

Collections.synchronizedMap(Map)

两个构造器 如果你传入了mutex参数，则将对象排斥锁赋值为传入的对象。 如果没有，则将对象排斥锁赋值为this，即调用synchronizedMap的对象

Hashtable 跟HashMap不一样

Hashtable 是不允许键或值为 null 的，HashMap 的键值则都可以为 null。 Hashtable在我们put 空值的时候会直接抛空指针异常，但是HashMap却做了特殊处理。

Hashtable使用的是安全失败机制（fail-safe），这种机制会使你此次读到的数据不一定是最新的数据。

实现方式不同：Hashtable 继承了 Dictionary类，而 HashMap 继承的是 AbstractMap 类。

初始化容量不同：HashMap 的初始容量为：16，Hashtable 初始容量为：11，两者的负载因子默认都是：0.75。

扩容机制不同：当现有容量大于总容量 * 负载因子时，HashMap 扩容规则为当前容量翻倍，Hashtable 扩容规则为当前容量翻倍 + 1。

迭代器不同：HashMap 中的 Iterator 迭代器是 fail-fast 的，而 Hashtable 的 Enumerator 不是 fail-fast 的。

总结：当其他线程改变了HashMap 的结构，如：增加、删除元素，将会抛出ConcurrentModificationException 异常，而 Hashtable 则不会。

快速失败（fail—fast）是java集合中的一种机制，在用迭代器遍历一个集合对象时， 如果遍历过程中对集合对象的内容进行了修改（增加、删除、修改）， 则会抛出Concurrent Modification Exception。

迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount 变量。 集合在被遍历期间如果内容发生变化，就会改变modCount的值。 每当迭代器使用hashNext()/next()遍历下一个元素之前，都会检测modCount变量是否为expectedmodCount值，是的话就返回遍历；否则抛出异常，终止遍历。 Tip：这里异常的抛出条件是检测到 modCount！=expectedmodCount 这个条件。如果集合发生变化时修改modCount值刚好又设置为了expectedmodCount值，则异常不会抛出。 因此，不能依赖于这个异常是否抛出而进行并发操作的编程，这个异常只建议用于检测并发修改的bug。

LinkedHashMap 这是一个「HashMap + 双向链表」的结构，落脚点是 HashMap，所以既拥有 HashMap 的所有特性还能有顺序。

TreeMap 是有序的，本质是用二叉搜索树来实现的。

ConcurrentHashMap

是由 Segment 数组、HashEntry 组成，和 HashMap 一样，仍然是数组加链表。

HashEntry跟HashMap差不多的，但是不同点是， 使用volatile去修饰了他的数据Value还有下一个节点next。

保证了不同线程对这个变量进行操作时的可见性，即一个线程修改了某个变量的值，这新值对其他线程来说是立即可见的。（实现可见性） 禁止进行指令重排序。（实现有序性） volatile 只能保证对单次读/写的原子性。i++ 这种操作不能保证原子性

并发度高的原因

jdk1.7 ConcurrentHashMap 采用了分段锁技术，其中 Segment 继承于 ReentrantLock。 每当一个线程占用锁访问一个 Segment 时，不会影响到其他的 Segment。

jdk1.8 其中抛弃了原有的 Segment 分段锁，而采用了 CAS + synchronized 来保证并发安全性。 跟HashMap很像，也把之前的HashEntry改成了Node，但是作用不变，把值和next采用了volatile去修饰，保证了可见性，并且也引入了红黑树，在链表大于一定值的时候会转换（默认是8）

jdk1.8 put操作

ConcurrentHashMap在进行put操作的还是比较复杂的，大致可以分为以下步骤： 根据 key 计算出 hashcode 。 判断是否需要进行初始化。 即为当前 key 定位出的 Node，如果为空表示当前位置可以写入数据，利用 CAS 尝试写入，失败则自旋保证成功。 如果当前位置的 hashcode == MOVED == -1,则需要进行扩容。 如果都不满足，则利用 synchronized 锁写入数据。 如果数量大于 TREEIFY_THRESHOLD 则要转换为红黑树。

CAS

CAS 是乐观锁的一种实现方式，是一种轻量级锁， JUC 中很多工具类的实现就是基于 CAS 的。 线程在读取数据时不进行加锁，在准备写回数据时， 比较原值是否修改，若未被其他线程修改则写回，若已被修改，则重新执行读取流程。

ABA 问题

一个线程把值改回了B，又来了一个线程把值又改回了A， 对于这个时候判断的线程，就发现他的值还是A， 所以他就不知道这个值到底有没有被人改过

(1) 版本号去保证就好了，就比如说，我在修改前去查询他原来的值的时候再带一个版本号， 每次判断就连值和版本号一起判断，判断成功就给版本号加1。 (2) 时间戳也可以，查询的时候把时间戳一起查出来，对的上才修改并且更新值的时候一起修改更新时间

synchronized性能可不咋地，为啥jdk1.8升级之后反而多了synchronized？

synchronized之前一直都是重量级的锁，但是后来官方是对他进行过升级的， 他现在采用的是锁升级的方式去做的。 针对 synchronized 获取锁的方式，JVM 使用了锁升级的优化方式， 就是先使用偏向锁优先同一线程然后再次获取锁，如果失败，就升级为 CAS 轻量级锁， 如果失败就会短暂自旋，防止线程被系统挂起。最后如果以上都失败就升级为重量级锁

Jdk1.8 get 操作

根据计算出来的 hashcode 寻址，如果就在桶上那么直接返回值。 如果是红黑树那就按照树的方式获取值。 就不满足那就按照链表的方式遍历获取值。

学习目标

明确每个接口和类的对应关系； 对每个接口和类，熟悉常用的 API； 对不同的场景，能够选择合适的数据结构并分析优缺点； 学习源码的设计，面试要会答啊。