面试题

1、说说常见的集合有哪些？

Map接口和Collection接口是所有集合框架的父接口

Collection接口的子接口包括：Set接口和List接口。Set中不能包含重复的元素。List是一个有序的集合，可以包含重复的元素，提供了按索引访问的方式。
Map接口的实现类主要有：HashMap、Hashtable、ConcurrentHashMap以及TreeMap等。Map不能包含重复的key，但是可以包含相同的value。根据键得到值，对map集合遍历时先得到键的set集合，对set集合进行遍历，得到相应的值。
Set接口的实现类主要有：HashSet、TreeSet、LinkedHashSet等
List接口的实现类主要有：ArrayList、LinkedList、Stack以及Vector等
Iterator，所有的集合类，都实现了Iterator接口，这是一个用于遍历集合中元素的接口，主要包含以下三种方法：
hasNext()是否还有下一个元素
next()返回下一个元素
remove()删除当前元素

2、哪些集合类可对元素的随机访问？

ArrayList 、 HashMap 、 TreeMap 和 HashTable 类提供对元素的随机访问。

3、Comparable 和 Comparator 接口的区别？

Comparable是排序接口，若一个类实现了Comparable接口，就意味着“该类支持排序”。而Comparator是比较器，我们若需要控制某个类的次序，可以建立一个“该类的比较器”来进行排序。
Comparable相当于“内部比较器”，而Comparator相当于“外部比较器”。
两种方法各有优劣， 用Comparable 简单， 只要实现Comparable 接口的对象直接就成为一个可以比较的对象，但是需要修改源代码。 用Comparator 的好处是不需要修改源代码， 而是另外实现一个比较器， 当某个自定义的对象需要作比较的时候，把比较器和对象一起传递过去就可以比大小了， 并且在Comparator 里面用户可以自己实现复杂的可以通用的逻辑，使其可以匹配一些比较简单的对象，那样就可以节省很多重复劳动了。

4、Collection 和 Collections 的区别？

Collection是集合类的一个顶级接口，其直接继承接口有List与Set
而Collections则是集合类的一个工具类/帮助类，其中提供了一系列静态方法，用于对集合中元素进行排序、搜索以及线程安全等各种操作。java.util.Collections 是一个包装类。它包含有各种有关集合操作的静态多态方法。此类不能实例化，就像一个工具类，服务于Java的Collection框架。

Collection是个Java.util下的接口，它是各种集合结构的父接口。
Collections是个java.util下的类，它包含有各种有关集合操作的静态方法。
Collection 层次结构中的根接口。Collection 表示一组对象，这些对象也称为 collection的元素。一些 collection 允许有重复的元素，而另一些则不允许。一些 collection 是有序的，而另一些则是无序的。JDK 不提供此接口的任何直接 实现：它提供更具体的子接口（如 Set 和 List）实现。此接口通常用来传递 collection，并在需要最大普遍性的地方操作这些 collection。
Collection
├List
│├LinkedList
│├ArrayList
│└Vector
│ └Stack
└Set
collections 此类完全由在 collection 上进行操作或返回 collection 的静态方法组成。它包含在 collection 上操作的多态算法，即“包装器”，包装器返回由指定 collection 支持的新 collection，以及少数其他内容。 如果为此类的方法所提供的 collection 或类对象为 null，则这些方法都会抛出 NullPointerException。

5、Enumeration 和 Iterator 接口的区别？

public interface Enumeration {
boolean hasMoreElements();
E nextElement();
}
public interface Iterator {
boolean hasNext();
E next();
void remove();
}
(01) 函数接口不同
Enumeration只有2个函数接口。通过Enumeration，我们只能读取集合的数据，而不能对数据进行修改。
Iterator只有3个函数接口。Iterator除了能读取集合的数据之外，也能数据进行删除操作。
(02) Iterator支持fail-fast机制，而Enumeration不支持
Enumeration 是JDK 1.0添加的接口。使用到它的函数包括Vector、Hashtable等类，这些类都是JDK 1.0中加入的，Enumeration存在的目的就是为它们提供遍历接口。Enumeration本身并没有支持同步，而在Vector、Hashtable实现Enumeration时，添加了同步。
而Iterator 是JDK 1.2才添加的接口，它也是为了HashMap、ArrayList等集合提供遍历接口。Iterator是支持fail-fast机制的：当多个线程对同一个集合的内容进行操作时，就可能会产生fail-fast事件。

6、集合使用泛型有什么优点？

1）保证了类型的安全性：泛型约束了变量的类型，保证了类型的安全性。
2）避免了不必要的装箱、拆箱操作，提高程序的性能：泛型变量固定了类型，使用的时候就已经知道是值类型还是引用类型，避免了不必要的装箱、拆箱操作。
3）提高方法的复用性。

7、List、Set、Map 之间的区别是什么？

List(列表)
List的元素以线性方式存储，可以存放重复对象，List主要有以下两个实现类：
1.ArrayList: 长度可变的数组，可以对元素进行随机的访问，向ArrayList中插入与删除元素的速度慢。JDK8中ArrayList扩容的实现是通过grow()方法里使用语句newCapacity = oldCapacity + (oldCapacity >> 1)（即1.5倍扩容）计算容量，然后调用Arrays.copyof()方法进行对原数组进行复制。
LinkedList: 采用链表数据结构，插入和删除速度快，但访问速度慢。
Set(集合)
Set中的对象不按特定(HashCode)的方式排序，并且没有重复对象，Set主要有以下两个实现类：
1.HashSet：HashSet按照哈希算法来存取集合中的对象，存取速度比较快。当HashSet中的元素个数超过数组大小*loadFactor（默认值为0.75）时，就会进行近似两倍扩容（newCapacity = (oldCapacity << 1) + 1）。
2.TreeSet：TreeSet实现了SortedSet接口，能够对集合中的对象进行排序。
Map(映射)
Map是一种把键对象和值对象映射的集合，它的每一个元素都包含一个键对象和值对象。Map主要有以下实现类：
HashMap：HashMap基于散列表实现，其插入和查询的开销是固定的，可以通过构造器设置容量和负载因子来调整容器的性能。
LinkedHashMap：类似于HashMap，但是迭代遍历它时，取得的顺序是其插入次序，或者是最近最少使用(LRU)的次序。
TreeMap：TreeMap基于红黑树实现。查看时，它们会被排序。TreeMap是唯一的带有subMap()方法的Map，subMap()可以返回一个子树。

8、为什么 Map 接口不继承 Collection 接口？

1.首先Map提供的是键值对映射（即Key和value的映射），而collection提供的是一组数据（并不是键值对映射）。如果map继承了collection接口，那么所有实现了map接口的类到底是用map的键值对映射数据还是用collection的一组数据呢（就我们平常所用的hashMap、hashTable、treeMap等都是键值对，所以它继承collection完全没意义），而且map如果继承了collection接口的话还违反了面向对象的接口分离原则。
接口分离原则：客户端不应该依赖它不需要的接口。另一种定义是：类间的依赖关系应该建立在最小的接口上。接口隔离原则将非常庞大、臃肿的接口拆分成为更小的和更具体的接口，这样客户将会只需要知道他们感兴趣的方法。接口隔离原则的目的是系统解开耦合，从而容易重构、更改和重新部署，让客户端依赖的接口尽可能地小。
2. Map和List、set不同，Map放的是键值对，list、set放的是一个个的对象。说到底是因为数据结构不同，数据结构不同，操作就不一样，所以接口是分开的。还是接口分离原则

9、常用的线程安全的 Map 有哪些？

1、HashTable
private Map map = new Hashtable<>();
来看看HashTable的源码

HashTable的get/put方法都被synchronized关键字修饰，说明它们是方法级别阻塞的，它们占用共享资源锁，所以导致同时只能一个线程操作get或者put，而且get/put操作不能同时执行，所以这种同步的集合效率非常低，一般不建议使用这个集合。
2、SynchronizedMap
private Map map = Collections.synchronizedMap(new HashMap());
这种是直接使用工具类里面的方法创建SynchronizedMap，把传入进行的HashMap对象进行了包装同步而已，来看看它的源码。

这个同步方式实现也比较简单，看出SynchronizedMap的实现方式是加了个对象锁，每次对HashMap的操作都要先获取这个mutex的对象锁才能进入，所以性能也不会比HashTable好到哪里去，也不建议使用。
3、ConcurrentHashMap - 推荐
private Map map = new ConcurrentHashMap<>();
这个也是最推荐使用的线程安全的Map，也是实现方式最复杂的一个集合，每个版本的实现方式也不一样，在jdk8之前是使用分段加锁的一个方式，分成16个桶，每次只加锁其中一个桶，而在jdk8又加入了红黑树和CAS算法来实现。

虽然实现起来很复杂，但使用起来也是非常简单的，在java面试中问的频率也非常高，最重要的是性能要比上面两种同步方式要快太多，推荐使用。

10、HashMap 与 Hashtable 的区别？

HashMap和Hashtable都实现了Map接口，但决定用哪一个之前先要弄清楚它们之间的分别。主要的区别有：线程安全性，同步(synchronization)，以及速度。

1. HashMap几乎可以等价于Hashtable，除了HashMap是非synchronized的，并可以接受null(HashMap可以接受为null的键值(key)和值(value)，而Hashtable则不行)。
2. HashMap是非synchronized，而Hashtable是synchronized，这意味着Hashtable是线程安全的，多个线程可以共享一个Hashtable；而如果没有正确的同步的话，多个线程是不能共享HashMap的。Java 5提供了ConcurrentHashMap，它是HashTable的替代，比HashTable的扩展性更好。
3. 另一个区别是HashMap的迭代器(Iterator)是fail-fast迭代器，而Hashtable的enumerator迭代器不是fail-fast的。所以当有其它线程改变了HashMap的结构（增加或者移除元素），将会抛出ConcurrentModificationException，但迭代器本身的remove()方法移除元素则不会抛出ConcurrentModificationException异常。但这并不是一个一定发生的行为，要看JVM。这条同样也是Enumeration和Iterator的区别。
4. 由于Hashtable是线程安全的也是synchronized，所以在单线程环境下它比HashMap要慢。如果你不需要同步，只需要单一线程，那么使用HashMap性能要好过Hashtable。

5. HashMap不能保证随着时间的推移Map中的元素次序是不变的。

   
   11、HashMap 和 TreeMap 怎么选？

   介绍
   TreeMap的Key值是要求实现java.lang.Comparable，所以迭代的时候TreeMap默认是按照Key值升序排序的；TreeMap的实现是基于红黑树结构。适用于按自然顺序或自定义顺序遍历键（key）。
   HashMap的Key值实现散列hashCode()，分布是散列的、均匀的，不支持排序；数据结构主要是桶(数组)，链表或红黑树。适用于在Map中插入、删除和定位元素。
   结论
   如果你需要得到一个有序的结果时就应该使用TreeMap（因为HashMap中元素的排列顺序是不固定的）。除此之外，由于HashMap有更好的性能，所以大多不需要排序的时候我们会使用HashMap。
   https://juejin.cn/post/6844904111817637901#heading-15

   
   12、HashMap 的数据结构是什么？

   HashMap的底层是哈希表，而Java中哈希表是由数组+链表实现的，每一个数组的节点称之为bucket桶，当桶中由多个元素就以链表的方法进行存储，当添加元素时，通过key的hash算法得出hash值，然后通过hash值映射出存在哪个桶中，如果桶中没有有元素，就添加成功，如果有元素那就代表散列冲突，比较已存在的元素和新插入的元素的hash值是否有相同，如果没有相同的则添加成功(情况1)，如果某个元素的hash值和新的元素hash值相同的，则调用key的equals方法继续进行比较，为true则新的值覆盖掉旧的值，为false添加成功(情况2)，对于情况1 和情况2，在jdk1.7是将新的元素添加到原来的头节点，jdk1.8是添加到链表后面，jdk1.8做了一个优化，因为如果链表的长度太长遍历查找复杂度为O(n)，所以引入了红黑树，当桶中的元素>8并且数组长度>64就转为红黑树，复杂度为O(logn)

   
   13、HashMap 在 JDK 8 中有哪些改变？

   在java 1.8中，如果链表的长度超过了8，那么链表将转换为红黑树。（桶的数量必须大于64，小于64的时候只会扩容）
   发生hash碰撞时，java 1.7 会在链表的头部插入，而java 1.8会在链表的尾部插入
   在java 1.8中，Entry被Node替代(换了一个马甲)。

   
   14、HashMap 的 put 方法逻辑？

   1.判断当前是否初始化，进行初始化
   2.判断当前位置有无节点，没有的话直接新new一个节点放入
   3.当前位置有节点需要判断key是否相同，相同的话需要新值覆盖旧值
   4.不相同的话判断当前节点是否是红黑树节点，是的话按照红黑树的插入方法插入
   5.不是的话进行链表的遍历，查看是否有key相同的节点，有的话新值覆盖旧值，没有的话正常来说走到最后一个节点，使用尾插法插入即可

   
   15、HashMap 的 get 方法逻辑？

   final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    //哈希表存在的情况下，根据hash获取链表的头，也就是first对象
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        //检测第一个first是的hash和key的内容是否匹配，匹配就直接返回
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        //链表的头部如果不是那就开始遍历整个链表，如果是红黑树节点，就用红黑树的方式遍历
        //整个链表的遍历就是通过比对hash和equals来实现
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
   }

   https://www.codetd.com/article/11724673

   
   16、HashMap 是线程安全的吗？

   HashMap是线程不安全的。
   原子性意味着不可分割，也就是说多个不可分割的操作同时只能被一个线程执行。注意原子性说的是在多个操作之间整体保证原子性（同时只能被一个线程执行），单个操作的原子性并不能保证操作整体的原子性。
   内存可见性说的是当一个线程对共享变量进行了修改，其他的线程不能立刻看到共享变量的最新值。

   
   17、HashMap 是怎么解决 hash 冲突的？

   hash冲突解决方案(常见的四种)
   开放地址法（open addressing）
   简单来说就是通过计算出来冲突的hash值进行再次的运算，直到得到可用的地址，主要有以下3种：
   线性探测再散列：发生冲突时，顺序查看哈希表下一单元是否可用，直到找到可用的单元
   二次探测再散列：发生冲突时，以冲突的位置为中心向左右探测是否有可用单元
   伪随机探测再散列：通过一组伪随机数列计算得到对应的单位位置
   单独链表法
   就是在哈希表中，针对相同的hash值使用链表的方式来存放
   再散列
   提供多个hash函数，冲突时使用其他的hash函数再次运算
   建立公共溢出区
   建立一个溢出表，hash冲突的时候放入溢出表
   Java中HashMap如何解决冲突
   其实，Java中的HashMap采用的hash冲突解决方案就是单独链表法，也就是在hash表节点使用链表存储hash值相同的值
   不过需要知道的是JDK8之后，如果链表长度超过8将会将链表转化为红黑树以便提高在hash冲突严重情况下的查询效率，也能够避免一定的hash碰撞攻击。

   
   18、HashMap 是怎么扩容的？

   
   19、HashMap 如何实现同步?

   1、使用 synchronized 关键字，这也是最原始的方法
   Collections.synchronizedMap(originMap) 方法
   2、使用 JDK1.5 提供的锁（java.util.concurrent.locks.Lock）

6. lock.lock();

7. value = map.get(key);
8. lock.unlock();

3、可以使用 JDK1.5 提供的读写锁（java.util.concurrent.locks.ReadWriteLock）

1. rwlock.readLock().lock();
2. value = map.get(key);
3. rwlock.readLock().unlock();

4、使用 JDK1.5 提供的 java.util.concurrent.ConcurrentHashMap 类

20、HashMap 中的负载因子是什么？

在 HashMap 中，临界值（threshold） = 负载因子（loadFactor） * 容量（capacity）。
loadFactor 是装载因子，表示 HashMap 满的程度，默认值为 0.75f，也就是说默认情况下，当 HashMap 中元素个数达到了容量的 3/4 的时候就会进行自动扩容。

21、Hashtable 为什么不叫 HashTable？

22、ConcurrentHashMap 的数据结构？

ConcurrentHashMap是线程安全并且高效的HashMap。Hashtable效率低下的原因是所有访问HashTable的线程必须竞争同一把锁。加入容器里有多把锁，每一把锁用于锁容器中的一部分数据，那么当多线程访问容器里不同数据段的数据时，线程之间就不会存在锁竞争，从而可以有效的提高并发效率，这就是ConcurrentHashMap的锁分段技术。首先将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个数据段时，其他段的数据也能被其他线程访问。
ConcurrentHashMap是由Segment数组结构和HashEntry数组结构组成。Segment是一种可重入锁ReentrantLock，在ConcurrentHashMap中扮演锁的角色，HashEntry则用于存储键值对数据。一个ConcurrentHashMap中包含一个Segment数组，Segment的结构和HashMap类似，是一种数组和链表结构。一个Segment里面包含一个HashEntry数组，每个HashEntry是一个链表的元素。每个Segment拥有一个锁，当对HashEntry数组的数据进行修改时，必须先获得对应的Segment锁

23、ArrayList 是线程安全的么？

不安全。

24、常用的线程安全的 List 集合有哪些？

vector、SynchronizedList、CopyOnWriteArrayList

25、循环删除 List 集合可能会发生什么异常？

ConcurrentModificationException

26、ArrayList 和 LinkedList 的区别？

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

   
   27、ArrayList 和 Vector 的区别？

   1、Vector是线程安全的，ArrayList不是线程安全的。
   2、ArrayList在底层数组不够用时在原来的基础上扩展0.5倍，Vector是扩展1倍。

   
   28、什么是 CopyOnWriteArrayList？

   https://www.cnblogs.com/chengxiao/p/6881974.html

   
   29、什么是 fail-safe？

   采用安全失败机制的集合容器，在遍历时不是直接在集合内容上访问的，而是先复制原有集合内容，在拷贝的集合上进行遍历。
   原理：由于迭代时是对原集合的拷贝进行遍历，所以在遍历过程中对原集合所作的修改并不能被迭代器检测到，所以不会触发Concurrent Modification Exception。
   缺点：基于拷贝内容的优点是避免了Concurrent Modification Exception，但同样地，迭代器并不能访问到修改后的内容，即：迭代器遍历的是开始遍历那一刻拿到的集合拷贝，在遍历期间原集合发生的修改迭代器是不知道的。
   场景：java.util.concurrent包下的容器都是安全失败，可以在多线程下并发使用，并发修改。
   快速失败和安全失败是对迭代器而言的。 快速失败：当在迭代一个集合的时候，如果有另外一个线程在修改这个集合，就会抛出ConcurrentModification异常，java.util下都是快速失败。 安全失败：在迭代时候会在集合二层做一个拷贝，所以在修改集合上层元素不会影响下层。在java.util.concurrent下都是安全失败

   
   30、什么是 fail-fast？

   在用迭代器遍历一个集合对象时，如果遍历过程中对集合对象的内容进行了修改（增加、删除、修改），则会抛出Concurrent Modification Exception。
   原理：迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount 变量。集合在被遍历期间如果内容发生变化，就会改变modCount的值。每当迭代器使用hashNext()/next()遍历下一个元素之前，都会检测modCount变量是否为expectedmodCount值，是的话就返回遍历；否则抛出异常，终止遍历。
   注意：这里异常的抛出条件是检测到 modCount！=expectedmodCount 这个条件。如果集合发生变化时修改modCount值刚好又设置为了expectedmodCount值，则异常不会抛出。因此，不能依赖于这个异常是否抛出而进行并发操作的编程，这个异常只建议用于检测并发修改的bug。
   场景：java.util包下的集合类都是快速失败的，不能在多线程下发生并发修改（迭代过程中被修改）。

   
   31、fail-fast 与 fail-safe 有什么区别？

   当我们对集合结构上做出改变的时候，fail-fast机制就会抛出异常。但是，对于采用fail-safe机制来说，就不会抛出异常(大家估计看到safe两个字就知道了)。
   这是因为，当集合的结构被改变的时候，fail-safe机制会在复制原集合的一份数据出来，然后在复制的那份数据遍历。
   因此，虽然fail-safe不会抛出异常，但存在以下缺点
   复制时需要额外的空间和时间上的开销。
   不能保证遍历的是最新内容。

   
   32、HashSet 的底层实现原理是什么？

   HashSet 是最常用的 Set 集合之一，可以保证元素的唯一性。 HashSet 底层完全就是在 HashMap 的基础上包了一层，只不过存储的时候 value 是默认存储了一个 Object 的静态常量，取的时候也是只返回 key ，所以看起来就像 List 一样。

   
   33、怎么确保一个集合不能被修改？

   可以使用 Collections. unmodifiableCollection(Collection c) 方法来创建一个只读集合，这样改变集合的任何操作都会抛出 Java. lang. UnsupportedOperationException 异常。