List篇

1.讲一下ArrayList，LinkedList，Vector，CopyOnWriteArrayList

ArrayList 和LinkedList的区别？

  • 数据结构实现：ArrayList 是动态数组的数据结构实现，而 LinkedList 是双向链表的数据结构实现。
  • 随机访问效率：ArrayList 比 LinkedList 在随机访问的时候效率要高，因为 LinkedList 是线性的数据存储方式，所以需要移动指针从前往后依次查找。
  • 增加和删除效率：在非首尾的增加和删除操作，LinkedList 要比 ArrayList 效率要高，因为 ArrayList 增删操作要影响数组内的其他数据的下标。

综合来说，在需要频繁读取集合中的元素时，更推荐使用 ArrayList，而在插入和删除操作较多时，更推荐使用 LinkedList。
ArrayList和LinkedList都实现了List接口，他们有以下的不同点： ArrayList是基于索引的数据接口，它的底层是数组。它可以以O(1)时间复杂度对元素进行随机访问。与此对应，LinkedList是以元素列表的形式存储它的数据，每一个元素都和它的前一个和后一个元素链接在一起，在这种情况下，查找某个元素的时间复杂度是O(n)。 相对于ArrayList，LinkedList的插入，添加，删除操作速度更快，因为当元素被添加到集合任意位置的时候，不需要像数组那样重新计算大小或者是更新索引。 LinkedList比ArrayList更占内存，因为LinkedList为每一个节点存储了两个引用，一个指向前一个元素，一个指向下一个元素。

CopyOnWriteArrayList

CopyOnWriteArrayList是Java并发包中提供的一个并发容器，它是个线程安全且读操作无锁的ArrayList，写操作则通过创建底层数组的新副本来实现，是一种读写分离的并发策略，我们也可以称这种容器为”写时复制器”
1、实现了List接口
2、内部持有一个ReentrantLock lock=new ReentrantLock()
3、底层是用volatile transient声明地数组 array
4、读写分离，写时复制出一个新的数组，完成插入、修改或者移除操作后将新数组赋值给array

Vector和 CopyOnWriteArrayList 的区别？

  • Vector是增删改查方法都加了synchronized，保证同步，但是每个方法执行的时候都要去获得锁，性能就会大大下降，
  • CopyOnWriteArrayList 只是在增删改上加锁，但是读不加锁，在读方面的性能就好于Vector。
  • CopyOnWriteArrayList支持读多写少的并发情况。

2.讲一下ArrayList的实现

ArrayList的底层数据结构就是一个数组，数组元素的类型为Object类型，对ArrayList的所有操作底层都是基于数组的。默认容量是10

3.LinkedList的实现.

LinkedList类的底层实现的数据结构是一个双链表（双向链表）
Java中的LinkedList类实现了List接口和Deque接口，是一种链表类型的数据结构，支持高效的插入和删除操作，同时也实现了Deque接口，使得LinkedList类也具有队列的特性。

4.CopyOnWriteArrayList的实现

CopyOnWriteArrayList是ArrayList的基础上使用ReentrantLock改造的List

  • 内部持有一个ReentrantLock，对写操作进行加锁，读操作无锁
  • 读写分离，写时复制出一个新的数组，完成插入、修改或者移除操作后将新数组赋值给array

5.ArrayList是如何扩容的？

再add()添加新数据的时候会进行一个判断,当我们添加的数据超过数组的长度时,数组就会进行扩容(grow方法)
这里分为两步:
1.先创建一个原数组长度1.5倍的新数组
2.然后再把旧的数组copy到新的数组


6.ArrayList频繁扩容导致添加性能急剧下降，如何处理？

使用ArrayList时，可以 new ArrayList(大小)构造方法来指定集合的大小，以减少扩容的次数，提高写入效率。那么这个大小指定多少合适呢？需要根据你的业务实际分析得出答案，eq:每次查询20条，那就设置20即可。

7.CopyOnWriteArrayList为什么并发安全且性能比Vector好？

我们知道Vector是增删改查方法都加了synchronized，保证同步，但是每个方法执行的时候都要去获取锁，性能就会大大降低， 而CopyOnWriteArrayList只是在增删改上加ReentrantLock独占锁，但是读操作不加锁，支持并发读，CopyOnWriteArrayList支持读多写少的情况。

8.快速失败(fail-fast)和安全失败(fail-safe)

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

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

区别？

Iterator的安全失败是基于对底层集合做拷贝，因此，它不受源集合上修改的影响。java.util包下面的所有的集合类都是快速失败的，而java.util.concurrent包下面的所有的类都是安全失败的。快速失败的迭代器会抛出ConcurrentModificationException异常，而安全失败的迭代器永远不会抛出这样的异常。

9.ArrayList线程安全吗？

  1. ArrayList是线程不安全的。<br />当开启多个线程操作List集合，向ArrayList中增加元素，同时去除元素。最后输出list中的所有数据，会出现几种情况：<br />①有些元素输出为Null；②数组下标越界异常。<br />有两种解决方案：<br />第一种是选用线程安全的数组容器是Vector，它将所有的方法都加上了synchronized。
public static Vector<Object> vector= new Vector<Object>();

二种是用Collections.synchronizedList将ArrayList包装成线程安全的数组容器。

List<String> list = Collections.synchronizedList(new ArrayList<>());

第三种是使用CopyOnWriteArrayList

10、如何复制某个ArrayList到另一个ArrayList中去？写出你的代码？

  • 使用clone()方法，比如ArrayList newArray = oldArray.clone();
  • 使用ArrayList构造方法，比如：ArrayList myObject = new ArrayList(myTempObject);

  • 使用Collection的copy方法。

    注意前两种是浅拷贝(shallow copy)

Map篇

1.讲一下HashMap、HashTable、CurrentHashMap、LinkedHashMap、TreeMap

HashMap

  • 线程不安全；
  • 数据无序；
  • 允许key和value为null；
  • 继承自AbstractMap类，实现了map接口
  • 存储结构：数组+链表+红黑树(1.8以后，链表长度大于8转换为红黑树)。插入数据时，通过hashcode找到这个键值对所处的bucket，如果发生冲突，则通过linkedlist的方式存储mapEntry对象，mapEntry实际上是一个键值对，在查询时，相同hashcode的key就是通过mapEntry进行比较然后找到对应的value。在链表长度大于8以后转换为红黑树结构。
  • 负载因子默认为0.75，当hashmap中的数据量达到总容量*负载因子时，hashmap会进行扩容。 负载因子为0.75是为了提高空间利用率和 减少查询成本的折中，主要是泊松分布，0.75的话碰撞最小。

  • HashMap扩容一次容量会变为原来的二倍，其通过hash运算结果和长度二进制量进行与运算计算应该放在数组的哪个位置，如果容量为2的n次幂，可以降低冲突。

    LinkedHashMap

  • 线程不安全

  • 数据保存了插入顺序
  • 继承自HashMap，扩容机制一致

  • 遍历时速度低于HashMap，但是在HashMap容量非常大但数据非常少时可能例外。LinkedHashMap的遍历速度只和实际数据有关，和容量无关，而HashMap的遍历速度和他的容量有关。

    TreeMap

  • 线程不安全

  • 数据有序
  • 不允许key为null，因为treemap有序，需要通过comparable和Comparator比较数据。

  • 底层实现为红黑树，容量没有限制

    HashTable

  • 线程安全（因为其中方法都是synchronized修饰的）

  • 数据有序
  • 继承自Dictionary类，实现了map接口
  • 不允许key为null，因为treemap有序，需要通过comparable和Comparator比较数据。

  • 底层实现为红黑树，容量没有限制

    ConcurrentHashMap

    concurrentHashMap在hashmap的基础上，加上了线程安全的特性。

  • 线程安全：其实现线程安全的方式与HashTable不同，该类在jdk1.7使用的是分段锁的概念，对每个分段实行同步机制，在两个线程读取不同的分段时可以异步操作。而在jdk1.8中进行了重构，舍弃了分段锁，采用无锁的算法进行同步。

  • 实现了currentmap接口而不是map接口
  • 不允许key或value为null
  • 关于currenthashmap的源码解析，可以参照ConcurrentHashMap实现原理和JDK1.8 concurrentHashMap 同步机制难点解析进行学习

HashMap 和 ConcurrentHashMap 的区别

  1. ConcurrentHashMap对整个桶数组进行了分割分段(Segment)，然后在每一个分段上都用lock锁进行保护，相对于HashTable的synchronized锁的粒度更精细了一些，并发性能更好，而HashMap没有锁机制，不是线程安全的。（JDK1.8之后ConcurrentHashMap启用了一种全新的方式实现,利用CAS算法。）
  2. HashMap的键值对允许有null，但是ConCurrentHashMap都不允许。

ConcurrentHashMap 和 Hashtable 的区别？

ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的方式上不同。

  • 底层数据结构： JDK1.7的 ConcurrentHashMap 底层采用 分段的数组+链表 实现，JDK1.8 采用的数据结构跟HashMap1.8的结构一样，数组+链表/红黑二叉树。Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用 数组+链表 的形式，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的；
  • 实现线程安全的方式（重要）：

① 在JDK1.7的时候，ConcurrentHashMap（分段锁） 对整个桶数组进行了分割分段(Segment)，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。（默认分配16个Segment，比Hashtable效率提高16倍。） 到了 JDK1.8 的时候已经摒弃了Segment的概念，而是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。（JDK1.6以后 对 synchronized锁做了很多优化） 整个看起来就像是优化过且线程安全的 HashMap，虽然在JDK1.8中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本；
② Hashtable(同一把锁) :使用 synchronized 来保证线程安全，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用 put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈效率越低。

2.讲一下HashMap的实现？

哈希表结构(链表散列:数组+链表)实现,结合数组和链表的优点。当链表长度超过8时,链表转换为红黑树。当个数减少为6时，转换为链表

3.讲一下ConcurrentHashMap实现

4.HashMap怎么扩容？

当map中包含的Entry的数量大于等于threshold = loadFactor * capacity的时候，且新建的Entry刚好落在一个非空的桶上，此刻触发扩容机制，将其容量扩大为2倍

5.HashMap如何插入、获取数据

HashMap底层是hash数组和单向链表实现,数组中的每个元素都是链表,由Node内部类(实现Map.Entry<K,V>接口)实现,HashMap通过put&get方法存储和获取。
存储对象时,将K/V键值传给put()方法:

  • ①、调用hash(K)方法计算K的hash值,然后结合数组长度,计算得数组下标;
  • ②、调整数组大小(当容器中的元素个数大于capacity*loadfactor时,容器会进行扩容resize为2n);
  • ③
    • i.如果K的hash值在HashMap中不存在,则执行插入,若存在,则发生碰撞;
    • ii.如果K的hash值在HashMap中存在,且它们两者equals返回true,则更新键值对;
    • iii.如果K的hash值在HashMap中存在,且它们两者equals返回false,则插入链表的尾部(尾插法)或者红黑树中(树的添加方式)。

      (JDK1.7之前使用头插法、JDK1.8使用尾插法) (注意:当碰撞导致链表大于TREEIFY_THRESHOLD=8时,就把链表转换成红黑树)

获取对象时,将K传给get()方法:

  • ①、调用hash(K)方法(计算K的hash值)从而获取该键值所在链表的数组下标;
  • ②、顺序遍历链表,equals()方法查找相同Node链表中K值对应的V值。

hashCode是定位的,存储位置;equals是定性的,比较两者是否相等。

6.HashMap如何解决碰撞

答：在解决这个问题之前，我们首先需要知道什么是哈希冲突，而在了解哈希冲突之前我们还要知道什么是哈希才行；
什么是哈希？
Hash，一般翻译为“散列”，也有直接音译为“哈希”的，这就是把任意长度的输入通过散列算法，变换成固定长度的输出，该输出就是散列值（哈希值）；这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
所有散列函数都有如下一个基本特性：根据同一散列函数计算出的散列值如果不同，那么输入值肯定也不同。但是，根据同一散列函数计算出的散列值如果相同，输入值不一定相同。
什么是哈希冲突？
当两个不同的输入值，根据同一散列函数计算出相同的散列值的现象，我们就把它叫做碰撞（哈希碰撞）。
HashMap的数据结构
在Java中，保存数据有两种比较简单的数据结构：数组和链表。数组的特点是：寻址容易，插入和删除困难；链表的特点是：寻址困难，但插入和删除容易；所以我们将数组和链表结合在一起，发挥两者各自的优势，使用一种叫做链地址法的方式可以解决哈希冲突：
java集合面试题 - 图1
这样我们就可以将拥有相同哈希值的对象组织成一个链表放在hash值所对应的bucket下，但相比于hashCode返回的int类型，我们HashMap初始的容量大小DEFAULT_INITIAL_CAPACITY = 1 << 4（即2的四次方16）要远小于int类型的范围，所以我们如果只是单纯的用hashCode取余来获取对应的bucket这将会大大增加哈希碰撞的概率，并且最坏情况下还会将HashMap变成一个单链表，所以我们还需要对hashCode作一定的优化
hash()函数
上面提到的问题，主要是因为如果使用hashCode取余，那么相当于参与运算的只有hashCode的低位，高位是没有起到任何作用的，所以我们的思路就是让hashCode取值出的高位也参与运算，进一步降低hash碰撞的概率，使得数据分布更平均，我们把这样的操作称为扰动，在JDK 1.8中的hash()函数如下：

1. static final int hash(Object key) {
2. int h;
3. return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);// 与自己右移16位进行异或运算（高低位异或）
4. }

这比在JDK 1.7中，更为简洁，相比在1.7中的4次位运算，5次异或运算（9次扰动），在1.8中，只进行了1次位运算和1次异或运算（2次扰动）；
通过上面的链地址法（使用散列表）和扰动函数我们成功让我们的数据分布更平均，哈希碰撞减少，但是当我们的HashMap中存在大量数据时，加入我们某个bucket下对应的链表有n个元素，那么遍历时间复杂度就为O(n)，为了针对这个问题，JDK1.8在HashMap中新增了红黑树的数据结构，进一步使得遍历复杂度降低至O(logn)；
总结
简单总结一下HashMap是使用了哪些方法来有效解决哈希冲突的：

1. 使用链地址法（使用散列表）来链接拥有相同hash值的数据； 2. 使用2次扰动函数（hash函数）来降低哈希冲突的概率，使得数据分布更平均； 3. 引入红黑树进一步降低遍历的时间复杂度，使得遍历更快；