(Java集合面试题)(java集合相关面试题)

1.集合框架

1.集合框架概述

1.集合框架 Collection集合总结 Collection

|--List 有序,可重复

|--ArrayList 底层数据结构是数组，查询快，增删慢。 线程不安全，效率高

|--Vector 底层数据结构是数组，查询快，增删慢。 线程安全，效率低

|--LinkedList 底层数据结构是链表，查询慢，增删快。 线程不安全，效率高

|--Set无序,唯一

|--HashSet 底层数据结构是哈希表。 如何保证元素唯一性的呢? 依赖两个方法：hashCode()和equals() 开发中自动生成这两个方法即可

|--LinkedHashSet 底层数据结构是链表和哈希表 由链表保证元素有序 由哈希表保证元素唯一

|--TreeSet 底层数据结构是红黑树。 如何保证元素排序的呢? 自然排序 比较器排序 如何保证元素唯一性的呢?

根据比较的返回值是否是0来决定 针对Collection集合我们到底使用谁呢? 唯一吗?

是：Set 排序吗? 是：TreeSet 否：HashSet 如果你知道是Set，但是不知道是哪个Set，就用HashSet。

否：List 要安全吗?

是：Vector

否：ArrayList或者LinkedList

查询多：ArrayList

增删多：LinkedList 如果你知道是List，但是不知道是哪个List，就用ArrayList。 如果你知道是Collection集合，但是不知道使用谁，就用ArrayList。 如果你知道用集合，就用ArrayList。

在集合中常见的数据结构(掌握)

ArrayXxx:底层数据结构是数组，查询快，增删慢

LinkedXxx:底层数据结构是链表，查询慢，增删快

HashXxx:底层数据结构是哈希表。

依赖两个方法：hashCode()和equals() TreeXxx:底层数据结构是二叉树。两种方式排序：自然排序和比较器排序

LinkedHashSet的数据结构

1.和HashMap是继承关系，是HashMap的子类，所以底层原理没有太大的变化。

2.因为是继承关系，底层的实现是在HashMap中定义了空方法和调用，LinkedHashMap中进行重写，然后核心方法直接调用HashMap的即可。

3.在原来的数据结构上改为了双向链表，专门维护插入顺序。

4.removeEldestEntry()可以自己进行重写，专门定义自己的废弃规则，从而实现简单的缓存系统。

2.ArrayList和LinkList的区别？

ArrayList底层用的是数组，查找快，增删慢

LinkList:底层用的链表，增删慢，查找快。

3.HashMap原理，添加数据的过程，查找数据的过程，为什么用红黑树，用自己的代码实现一个HashMap?

数据结构为数组+链表+红黑树

1.先计算Key的hash,得到数据的索引，然后将key放到table[index]位置，当table[index]已存在其它元素时，会在table[index]位置形成一个链表，将新添加的元素放在table[index]，原来的元素通过Entry的next进行链接，这样以链表形式解决hash冲突问题

2.如果有哈希冲突就使用equals进行比较 ,相等覆盖,不相等添加

3.如果有容量不够进行扩容，对全部数据进行重新hash

4.HashMap的初始容量为16，Hashtable初始容量为11，两者的填充因子默认都是0.75 HashMap扩容时是当前容量翻倍即:capacity2，Hashtable扩容时是容量翻倍+1即:capacity2+1

5.查找数据也是先计算Hash，如果有哈希冲突就使用equals进行比较

当链表的长度>=8且数组长度>=64时，会把链表转化成红黑树。

当链表长度>=8，但数组长度<64时，会优先进行扩容，而不是转化成红黑树。

当红黑树节点数<=6，自动转化成链表。

1.HashMap和Hashtable的底层实现都是数组+链表结构实现的，这点上完全一致

添加、删除、获取元素时都是先计算hash，根据hash和table.length计算index也就是table数组的下标，然后进行相应操作.

2./**

* HashMap的默认初始容量 必须为2的n次幂
*/
static final int DEFAULT_INITIAL_CAPACITY = 16;

/**
* HashMap的最大容量，可以认为是int的最大值
*/
static final int MAXIMUM_CAPACITY = 1 &lt;&lt; 30;

/**
* 默认的加载因子
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
* HashMap用来存储数据的数组
*/
transient Entry[] table;

3.HashMap的创建 HashMap默认初始化时会创建一个默认容量为16的Entry数组，默认加载因子为0.75，同时设置临界值为16*0.75

4.添加 添加是先计算key的hashCode值,计算后的值会再次调用hash方法再次散列,然后与数组长度进行-1进行&操作,就是调用indexFor方法. static int hash(int h) { h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } static int indexFor(int h, int length) { return h & (length-1); } ,然后将key放到table[index]位置，当table[index]已存在其它元素时，会在table[index]位置形成一个链表，将新添加的元素放在table[index]，原来的元素通过Entry的next进行链接，这样以链表形式解决hash冲突问题，同时会比较链表中key是否相等,调用equels方法,相等覆盖,不相等添加,当元素数量达到临界值(capactiyfactor)时，则进行扩容，是table数组长度变为table.length2,但是当链表中的元素较多，即hash值相等的元素较多时，通过key值依次查找的效率较低。而JDK1.8中，HashMap采用数组+链表+红黑树实现，当链表长度超过阈值（8）时，将链表转换为红黑树，这样大大减少了查找时间。

当链表的长度>=8且数组长度>=64时，会把链表转化成红黑树。

当链表长度>=8，但数组长度<64时，会优先进行扩容，而不是转化成红黑树。

当红黑树节点数<=6，自动转化成链表。

4.resize方法 resize方法在hashmap中并没有公开，这个方法实现了非常重要的hashmap扩容，具体过程为：先创建一个容量为table.length2的新table，修改临界值，然后把table里面元素计算hash值并使用hash与table.length2重新计算index放入到新的table里面 这里需要注意下是用每个元素的hash全部重新计算index，而不是简单的把原table对应index位置元素简单的移动到新table对应位置

Entry结构分析

static class Entry<K,V> implements Map.Entry<K,V> {
final K key;// map中key值，可以为null。
V value; // map中的value值，可以为null。
Entry<K,V> next;// 链表引用，防止key值不同，hash值相同。
int hash; // 每个key的hash值
}

为什么用红黑树

java8不是用红黑树来管理hashmap，而是在hash值相同的情况下（且重复数量大于8），用红黑树来管理数据。 红黑树相当于排序数据，可以自动的使用二分法进行定位，性能较高。一般情况下，hash值做的比较好的话基本上用不到红黑树。

红黑树牺牲了一些查找性能 但其本身并不是完全平衡的二叉树。因此插入删除操作效率略高于AVL树。 AVL树用于自平衡的计算牺牲了插入删除性能，但是因为最多只有一层的高度差，查询效率会高一些。 原文链接：https://blog.csdn.net/it_qingfengzhuimeng/article/details/103308308

红黑树的特点： ①：每个节点都有红色或黑色树的根始终是黑色的 ②：没有两个相邻的红色节点 ③：从节点（包括根）到其任何后代NULL节点(叶子结点下方挂的两个空节点，并且认为他们是黑色的)的每条路径都具有相同数量的黑色节点

RB-Tree的统计性能高于AVL. 故引入RB-Tree是功能、性能、空间开销的折中结果。 ② AVL更平衡，结构上更加直观，时间效能针对读取而言更高；维护稍慢，空间开销较大。 ③ 红黑树，读取略逊于AVL，维护强于AVL，空间开销与AVL类似，内容极多时略优于AVL，维护优于AVL。 基本上主要的几种平衡树看来，红黑树有着良好的稳定性和完整的功能，性能表现也很不错，综合实力强，在诸如STL的场景中需要稳定表现。 链接：https://www.jianshu.com/p/37436ed14cc6

HashMap在并发场景下可能存在哪些问题？ 数据丢失 数据重复 死循环

4.自己实现一个ArrayList,HashMap

https://www.cnblogs.com/beyond-MS/p/12716164.html

https://blog.csdn.net/u014401141/article/details/74857341

5.ConcurrentHashMap原理，JDK1.7之前，JDK1.8之后

JDK 1.7之前采用分段锁，ReentrantLock+Segment+HashEntry ,数据结构是 数组+链表

1.Segment(分段锁)

ConcurrentHashMap中的分段锁称为Segment，它即类似于HashMap的结构，即内部拥有一个Entry数组，数组中的每个元素又是一个链表,同时又是一个ReentrantLock（Segment继承了ReentrantLock）。

2.内部结构

ConcurrentHashMap使用分段锁技术，将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问，能够实现真正的并发访问。如下图是ConcurrentHashMap的内部结构图：

ConcurrentHashMap定位一个元素的过程需要进行两次Hash操作。

第一次Hash定位到Segment，第二次Hash定位到元素所在的链表的头部。

3.该结构的优劣势

坏处

这一种结构的带来的副作用是Hash的过程要比普通的HashMap要长

好处

写操作的时候可以只对元素所在的Segment进行加锁即可，不会影响到其他的Segment，这样，在最理想的情况下ConcurrentHashMap可以最高同时支持Segment数量大小的写操作（刚好这些写操作都非常平均地分布在所有的Segment上）。

所以，通过这一种结构，ConcurrentHashMap的并发能力可以大大的提高。

JDK1.8之后采用Synchronized +Cas+HashEntry+红黑树 ，数组结构是 数组+链表+红黑树

JDK8中ConcurrentHashMap参考了JDK8 HashMap的实现，采用了数组+链表+红黑树的实现方式来设计，如下图所示：

内部大量采用CAS操作，这里我简要介绍下CAS

JDK1.8中 ConcurrentHashMap 中的CAS 和 synchronized是如何使用的

CAS：在判断数组中当前位置为null的时候，使用CAS来把这个新的Node写入数组中对应的位置

synchronized ：当数组中的指定位置不为空时，通过加锁来添加这个节点进入数组(链表<8)或者是红黑树（链表>=8）

添加数据的过程

当添加一对键值对的时候，首先会去判断保存这些键值对的数组是不是初始化了，

• 如果没有初始化就先调用initTable（）方法来进行初始化过程

• 然后通过计算hash值来确定放在数组的哪个位置

  如果没有hash冲突就直接CAS插入，如果hash冲突的话，则取出这个节点来

• 如果取出来的节点的hash值是MOVED(-1)的话，则表示当前正在对这个数组进行扩容，复制到新的数组，则当前线程也去帮助复制

• 最后一种情况就是，如果这个节点，不为空，也不在扩容，则通过synchronized来加锁，进行添加操作

• 然后判断当前取出的节点位置存放的是链表还是树

• 如果是链表的话，则遍历整个链表，直到取出来的节点的key来个要放的key进行比较，如果key相等，并且key的hash值也相等的话，

• 则说明是同一个key，则覆盖掉value，否则的话则添加到链表的末尾

• 如果是树的话，则调用putTreeVal方法把这个元素添加到树中去

• 最后在添加完成之后，调用addCount（）方法统计size，判断在该节点处共有多少个节点（注意是添加前的个数），如果达到8个以上了的话，

• 则调用treeifyBin方法来尝试将处的链表转为树，或者扩容数组

如果没有初始化就先调用initTable（）方法来进行初始化过程

ConcurrentHashMap锁的是节点 在ConcurrentHashMap中采用Node+CAS+Synchronized来保证并发安全进行实现。ConcurrentHashMap利用Node数组来存储数据，在Node数据中每一个下标对应一段数据。假设有一个线程对Node数组中某个位置插入数据，如果这个位置还没有值，则利用CAS算法不加锁的方式直接插入数据。如果当前位置有值，首先利用Synchronized锁住这个位置的值，然后向这个位置插入数据，如果这个位置存储的是链表，遍历链表向链表尾部插入数据，如果这个位置存储的是红黑树，向红黑树中插入数据。

6.List、 Set 和 Map 的初始容量和加载因子

List ArrayList 的初始容量是10，加载因子为0.5；扩容增量：原容量的 0.5倍+1；一次扩容后长度为16。 Vector 初始容量为10，加载因子1。扩容增量：原容量的1倍，一次扩容后的容量为20。

Set HashSet，初始容量为16，加载因子为0.75；扩容增量：原容量的1.6倍；如 HAshSet 的容量为16，一次扩容后容量为32

Map HashMap，初始容量16，加载因子0.75；扩容增量：原容量的1倍；如 HashMap 的容量为16，一次扩容后容量为 32

7.Java哪些集合类是线程安全的？

Vector：就比Arraylist多了个同步化机制（线程安全）。 HashTable：就比Hashmap多了个线程安全。 ConcurrentHashMap:是一种高效但是线程安全的集合。 Stack：栈，也是线程安全的，继承于Vector。

ConcurrentLinkedQueue：基于链接节点的无边界的线程安全队列，采用FIFO原则对元素进行排序，内部采用CAS算法实现

Collections.synchronizedList

8.Comparable和Comparator两个接口比较

https://www.jb51.net/article/123097.htm

Comparator 和 Comparable 比较

Comparable是排序接口；若一个类实现了Comparable接口，就意味着“该类支持排序”。

Comparator是比较器；我们若需要控制某个类的次序，可以建立一个“该类的比较器”来进行排序。

我们不难发现：Comparable相当于“内部比较器”，而Comparator相当于“外部比较器”。