Java集合(1)

HashMap:JDK1.8以前HashMap是由数组+链表组成的，数组是HashMap的主体，链表是为了解决哈希冲突而存在的。JDK1.8以后数组+链表+红黑树。
LinkedHashMap:LinkedHashMap继承自HashMap，所以它的底层是数组+链表+红黑树，并且加了一条双向链表。
Hashtable:数组+链表组成的，数组是Hashtable的主体，链表则主要是为了解决哈希冲突而存在的。
TreeMap:红黑树(自平衡的排序二叉树)。

如何选用集合？

根据键值获取元素值时就选用Map接口下的集合，需要排序时选择TreeMap，不需要排序时就选择HashMap，需要保证线程安全就选用ConcurrentHashMap。
我们只需要存放元素值时，就选择实现Collection接口的集合，需要保证元素唯一时选择实现Set接口的集合比如TreeSet或HashSet，不需要就选择实现List接口的比如ArrayList或LinkedList，然后根据实现这些接口的集合的特点来选用。

为啥要使用集合？

根据我们开发时存储的形式是各种各样的，传统的数组已经不能满足这个需求，我们需要一个容器能过够存储各种各样的，这就是集合。

ArrayList和Array(数组)的区别

ArrayList会根据实际存储元素动态地扩容或者缩容，而Array被创建之后就不能改变它的长度。
ArrayList让你使用泛型来确保类型安全，Array则不可以。
ArrayList提供了丰富的API操作方法，比如add()，remove()等。Array只是一个固定长度的数组，只能按照下标访问其中的元素或者增强循环访问其中的元素，不具有动态添加，删除元素的能力
ArrayList创建时不需要指定大小，而Array创建时必须指定大小。
ArrayList只能存储对象，而Array都可以存(基本数据类型和对象)

ArrayList和Vector的区别

ArrayList是List接口的主要实现类，线程不安全，用于单线程且查询频繁的场景(线程不安全)。
Vector用于多线程，它是线程安全的。

Vector和Stack的区别

Vector和Stack两者都是线程安全的，都是使用synchronized关键字进行同步处理。
Stack继承自Vector，是一个后进后出的栈，而Vector是一个列表。

随着 Java 并发编程的发展，Vector 和 Stack 已经被淘汰，推荐使用并发集合类（例如 ConcurrentHashMap、CopyOnWriteArrayList 等）或者手动实现线程安全的方法来提供安全的多线程操作支持。

ArrayList可以添加null值吗

ArrayList可以存储任何类型的对象，包括null值。不过，不建议向ArrayList中添加null值，null值毫无意义，会让代码难以维护比如忘记做判空处理就会导致空指针异常。

ArrayList插入和删除元素的时间复杂度

对于插入

头部插入:对于在头部插入的，要往后移动n个元素，所以时间复杂度为O(n)
尾部插入: 对于在尾部插入的，如果不扩容的话，时间复杂度位O(1)，如果扩容的话，时间复杂度为O(n)
指定位置插入:需要将目标位置之后的所有元素都往后移动一个位置，然后再把新元素放入指定位置，这个元素需要移动平均n/2个元素，因此时间复杂度为O(n)

对于删除:

头部删除:O(n)
尾部删除:O(1)
指定位置删除:O(n)

总结:这种的话可以直接从数组的角度来分析时间复杂度

LinkedList插入和删除元素的时间复杂度是多少

头部插入/删除:O(1)
尾部插入/删除:O(1)
指定位置插入/删除:O(n)

总结:这种的话可以根据双向链表来分析时间复杂度。

LinkedList为啥不能实现RandomAccess接口

RandomAccess(是一个标记接口)就是用来表明实现该接口的类支持随机访问(即索引访问)，而LinkedList底层是链表，内存不一定连续，是不支持随机访问(即索引访问)的，所以不能实现RandomAccess这个接口。

ArrayList与LinkedList区别

是否线程安全，两者都是不安全的，在多线程的情况下都不是安全的。
时间复杂度: ArrayList的底层是动态数组，LinkedList的底层是链表，可以从这个底层来进行分析。
内存占用:有于LinkedList得存下一个节点的地址，所以LinkedList所占的内存偏大。
是否支持随机访问，ArrayList支持随机访问，LinkedList不支持随机访问。
使用场景，ArrayList用于大多数场景。因此建议能用ArrayList就用ArrayList。

ArrayList的扩容机制

当 ArrayList 中的元素数量超过其当前容量时，会触发扩容机制。默认情况下，ArrayList 的初始容量为 10。
当发生扩容时，ArrayList 会创建一个新的数组，其容量为原数组的 1.5 倍（即 oldCapacity + (oldCapacity » 1)），然后将原数组中的元素复制到新数组中。
复制过程是通过 Arrays.copyOf() 方法实现的。

源码分析(add方法):

1.首先会进入add方法，在add方法中首先判断(size + 1)是否需要扩容，如果需要则扩容，然后赋值。
2.判断扩容在ensureCapacityInternal这个函数，这个函数内部会调用ensureExplicitCapacity，如果(minCapacity - elementData.length > 0)即容量不够了，则会调用grow方法。
3.grow即是核心方法，grow方法中首先将旧的容量扩容成1.5倍，与minCapacity进行比较，如果小于，则新的容量为minCapacity,然后进行(newCapacity - MAX_ARRAY_SIZE > 0)，然后进行 return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE :MAX_ARRAY_SIZE;。
4.最终通过 Arrays.copyOf(elementData, newCapacity); 复制老数组的数据到新数组，完成扩容。

Comparable和Comparator的区别

Comparable接口出自java.lang包，它有一个compareTo(Object obj)方法用来排序。
Comparator接口出自java.util包，它有一个compare(Object obj1, Object obj2)方法用来排序。

无序性和不可重复性的含义是啥

无序性指的数组的元素的添加不是按照数组索引的顺序来进行添加的，而是按照根据数值的哈希值来进行加的。
不可重复性指的是equals()判断时，返回false，必须重写equals()和hashcode()方法。

比较HashSet，LikedHashSet和TreeSet三者的异同

相同点:这三者都只能存储不重复的元素，这三者都是线程不安全的。
不同点:内部数据结构不同，HashSet的底层是基于HashMap实现的，底层的数据结构跟HashMap的一样，数组+链表+红黑树，而LinkedHashSet的底层是LinkedHashMap，底层是数组+链表(双向链表)+红黑树，TreeSet的底层是TreeMap的，底层的数据结构为红黑树(一种自平衡的树)。
应用场景不同，HashSet常常用于不需要保证元素插入和取出顺序的场景，LinkedHashSet用于保证元素的插入和取出顺序满足FIFO的场景，TreeSet用于支持对元素自定义排序规则的场景。

Queue与Deque的区别

Queue的底层是单向队列，支持FIFO，从一端进从一端出。
Deque的底层是双向队列，支持两端添加和删除，这个可以模拟栈。

ArrayDeque与LikedList的区别

ArrayDeque的底层是变长的数组加双指针，LinkedListd的底层是双链表。
ArrayDeque不支持存储NULL数据，但LinkedList支持。
ArrayDeque 插入时可能存在扩容过程, 不过均摊后的插入操作依然为 O(1)。虽然 LinkedList 不需要扩容，但是每次插入数据时均需要申请新的堆空间，均摊性能相比更慢。

说一说PriorityQueue

PriorityQueue按照某种优先级进行取出和插入。
PriorityQueue 利用了二叉堆的数据结构来实现的，底层使用可变长的数组来存储数据。

啥是BlockingQueue

就是阻塞队列，符合生产者-消费者模式，当队列没有时进入阻塞状态，当队列已经满时，一直等到队列可以放入新元素时再放入

BlockingQueue的实现类有哪些

ArrayBlockingQueue和LinkedBlockingQueue。

ArrayBlockingQueue和LinkedBlockingQueue有啥区别？

底层实现：ArrayBlockingQueue 基于数组实现，而 LinkedBlockingQueue 基于链表实现。
是否有界：ArrayBlockingQueue 是有界队列，必须在创建时指定容量大小。LinkedBlockingQueue 创建时可以不指定容量大小，默认是Integer.MAX_VALUE，也就是无界的。但也可以指定队列大小，从而成为有界的。