Collection

1. Set

  • TreeSet：基于红黑树实现，支持有序性操作，例如根据一个范围查找元素的操作。但是查找效率不如 HashSet，HashSet 查找的时间复杂度为 O(1)，TreeSet 则为 O(logN)。
  • HashSet：基于哈希表实现，支持快速查找，但不支持有序性操作。并且失去了元素的插入顺序信息，也就是说使用 Iterator 遍历 HashSet 得到的结果是不确定的。HashSet的底层实际上是维护了一个HashMap
  • LinkedHashSet：具有 HashSet 的查找效率，并且内部使用双向链表维护元素的插入顺序。

    说一说TreeSet和HashSet的区别

    HashSet、TreeSet中的元素都是不能重复的，并且它们都是线程不安全的，二者的区别是：
  1. HashSet中的元素可以是null，但TreeSet中的元素不能是null；
  2. HashSet不能保证元素的排列顺序，而TreeSet支持自然排序、定制排序两种排序的方式；
  3. HashSet底层是采用哈希表实现的，而TreeSet底层是采用红黑树实现的。

2. List

  • ArrayList：基于动态数组实现，支持随机访问。
    • ArrayList的底层是用数组来实现的，默认第一次插入元素时创建大小为10的数组，超出限制时会增加50%的容量，并且数据以 System.arraycopy() 复制到新的数组，因此最好能给出数组大小的预估值。
    • 按数组下标访问元素的性能很高，这是数组的基本优势。直接在数组末尾加入元素的性能也高，但如果按下标插入、删除元素，则要用 System.arraycopy() 来移动部分受影响的元素，性能就变差了，这是基本劣势。
  • Vector：和 ArrayList 类似，但它是线程安全的。
  • LinkedList：基于双向链表实现，只能顺序访问，但是可以快速地在链表中间插入和删除元素。不仅如此，LinkedList 还可以用作栈、队列和双向队列。

    谈谈CopyOnWriteArrayList的原理

CopyOnWriteArrayList是Java并发包里提供的并发类，简单来说它就是一个线程安全且读操作无锁的ArrayList。正如其名字一样，在写操作时会复制一份新的List，在新的List上完成写操作，然后再将原引用指向新的List。这样就保证了写操作的线程安全。
CopyOnWriteArrayList允许线程并发访问读操作，这个时候是没有加锁限制的，性能较高。而写操作的时候，则首先将容器复制一份，然后在新的副本上执行写操作，这个时候写操作是上锁的。结束之后再将原容器的引用指向新容器。注意，在上锁执行写操作的过程中，如果有需要读操作，会作用在原容器上。因此上锁的写操作不会影响到并发访问的读操作。

  • 优点：读操作性能很高，因为无需任何同步措施，比较适用于读多写少的并发场景。在遍历传统的List时，若中途有别的线程对其进行修改，则会抛出ConcurrentModificationException异常。而CopyOnWriteArrayList由于其”读写分离”的思想，遍历和修改操作分别作用在不同的List容器，所以在使用迭代器进行遍历时候，也就不会抛出ConcurrentModificationException异常了。
  • 缺点：一是内存占用问题，毕竟每次执行写操作都要将原容器拷贝一份，数据量大时，对内存压力较大，可能会引起频繁GC。二是无法保证实时性，Vector对于读写操作均加锁同步，可以保证读和写的强一致性。而CopyOnWriteArrayList由于其实现策略的原因，写和读分别作用在新老不同容器上，在写操作执行过程中，读不会阻塞但读取到的却是老容器的数据。

ArrayList和LinkedList有什么区别？

  1. ArrayList的实现是基于数组，LinkedList的实现是基于双向链表；
  2. 对于随机访问ArrayList要优于LinkedList，ArrayList可以根据下标以O(1)时间复杂度对元素进行随机访问，而LinkedList的每一个元素都依靠地址指针和它后一个元素连接在一起，查找某个元素的时间复杂度是O(N)；
  3. 对于插入和删除操作，LinkedList要优于ArrayList，因为当元素被添加到LinkedList任意位置的时候，不需要像ArrayList那样重新计算大小或者是更新索引；
  4. LinkedList比ArrayList更占内存，因为LinkedList的节点除了存储数据，还存储了两个引用，一个指向前一个元素，一个指向后一个元素。

3. Queue

  • LinkedList：可以用它来实现双向队列。
  • PriorityQueue：基于堆结构实现，可以用它来实现优先队列。
  • 牛客秋招java基础6

Map

  • TreeMap：基于红黑树实现。
  • HashMap：基于哈希表实现。
  • HashTable：和 HashMap 类似，但它是线程安全的，这意味着同一时刻多个线程同时写入 HashTable 不会导致数据不一致。它是遗留类，不应该去使用它，而是使用 ConcurrentHashMap 来支持线程安全，ConcurrentHashMap 的效率会更高，因为 ConcurrentHashMap 引入了分段锁。
  • LinkedHashMap：使用双向链表来维护元素的顺序，顺序为插入顺序或者最近最少使用（LRU）顺序。

HashMap怎么扩容？

使用resize()函数进行扩容。
一般情况下，当元素数量超过阈值时便会触发扩容。每次扩容的容量都是之前容量的2倍。
首先resize()方法进行扩容，会拿到当前容量的大小，如果容量等于0的话，就会给他一个初始容量大小16，然后设置临界值为初始容量16 * 负载因子 0.75，也就是12了，然后将扩容好的tab返回。
空参数的构造函数实例化的HashMap默认内部数组是null，即没有实例化。第一次调用put方法时，则会开始第一次初始化扩容，长度为16。
JDK8的HashMap在迁移元素的时候是正序的，不会出现倒置链表的发生。如果桶内元素超过8个，则会将链表转化为红黑树。
Java容器 - 图1

Map 的 put 过程

  1. 首次扩容：先判断数组是否为空，若数组为空则进行第一次扩容（resize）；
  2. 计算索引：通过hash算法，计算键值对在数组中的索引；
  3. 插入数据：
    • 如果当前位置元素为空，则直接插入数据；
    • 如果当前位置元素非空，且key已存在，则直接覆盖其value；
    • 如果当前位置元素非空，且key不存在，则将数据链到链表末端；
    • 若链表长度达到8，则将链表转换成红黑树，并将数据插入树中；
  4. 再次扩容如果数组中元素个数（size）超过threshold（临界值），则再次进行扩容操作。

HashMap为什么用红黑树而不用B树

B/B+树多用于外存上时，B/B+也被成为一个磁盘友好的数据结构。
HashMap本来是数组+链表的形式，链表由于其查找慢的特点，所以需要被查找效率更高的树结构来替换。如果用B/B+树的话，在数据量不是很多的情况下，数据都会“挤在”一个结点里面，这个时候遍历效率就退化成了链表。

HashMap中的循环链表是如何产生的？

在多线程的情况下，当重新调整HashMap大小的时候，就会存在条件竞争，因为如果两个线程都发现HashMap需要重新调整大小了，它们会同时试着调整大小。在调整大小的过程中，存储在链表中的元素的次序会反过来，因为移动到新的bucket位置的时候，HashMap并不会将元素放在链表的尾部，而是放在头部，这是为了避免尾部遍历。如果条件竞争发生了，那么就会产生死循环了。

HashMap底层原理

HashMap基于Map接口实现，元素以键值对的方式存储，并且允许使用null 键和null 值， 因为key不允许重复，因此只能有一个键为null,另外HashMap不能保证放入元素的顺序，它是无序的，和放入的顺序并不能相同。HashMap是线程不安全的。

HashMap采用Entry数组来存储key-value对，每一个键值对组成了一个Entry实体，Entry类实际上是一个单向的链表结构，它具有Next指针，可以连接下一个Entry实体，以此来解决Hash冲突的问题。

为什么放在hashMap集合key部分的元素需要重写equals方法？

因为equals默认比较是两个对象内存地址

HashMap是线程安全的吗？

不是，多线程调用的情况下，扩容会出问题。

在多线程的环境下，存在同时其他的元素也在进行put操作，如果hash值相同，可能出现同时在同一数组下用链表表示，造成闭环，导致在get时会出现死循环，所以HashMap是线程不安全的。
HashTable是线程安全的，它在所有涉及到多线程操作的都加上了synchronized关键字来锁住整个table，这就意味着所有的线程都在竞争一把锁，在多线程的环境下，它是安全的，但是效率很低，不推荐使用。

jdk8造成线程不安全分2中情况；
并发执行put操作时会出现hashcode冲突从而导致数据覆盖，造成线程不安全；
jdk8在（++size>threshold）代码片段，如果并发操作，可能导致两次扩容，但最终结果只有一次扩容的效果，从而线程不安全

ConcurrentHashMap为什么是线程安全的

JDK1.7中，ConcurrentHashMap使用的锁分段技术，将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问。

那一段一段就是指Segment，它继承了ReentrantLock，具备锁和释放锁的功能。ConcurrentHashMap只有16个Segment，并且不会扩容，最多可以支持16个线程并发写。

JDK1.8的ConcurrentHashMap怎么实现线程安全的

JDK1.8放弃了锁分段的做法，采用CAS和synchronized方式处理并发。以put操作为例，CAS方式确定key的数组下标，synchronized保证链表节点的同步效果。

JDK1.8的做法有什么好处呢

  1. 减少内存开销
    假设使用可重入锁，那么每个节点都需要继承AQS，但并不是每个节点都需要同步支持，只有链表的头节点（红黑树的根节点）需要同步，这无疑消耗巨大内存。
  2. 获得JVM的支持
    可重入锁毕竟是API级别的，后续的性能优化空间很小。synchronized则是JVM直接支持的，JVM能够在运行时作出相应的优化措施：锁粗化、锁消除、锁自旋等等。使得synchronized能够随着JDK版本的升级而不改动代码的前提下获得性能上的提升。

为什么不推荐使用HashTable呢

HashTable容器使用synchronized来保证线程安全，但在线程竞争激烈的情况下HashTable的效率非常低下。因为多个线程访问HashTable的同步方法时，可能会进入阻塞或轮询状态。如线程1使用put进行添加元素，线程2不但不能使用put方法添加元素，并且也不能使用get方法来获取元素，所以竞争越激烈效率越低。