★★1. Arraylist与LinkedList区别

从底层结构、效率、开销等方面进行区分
ArrayList
1、Arraylist底层结构为一个Object[] 类型的动态数组进行元素的存储，是一个连续内存存储。
2、Arraylist的扩容机制：ArrayList的初始长度为10的数组，当向list中添加一个元素，若此时长度超出了数组长度，则需要进行扩容，扩容长度为原来的1.5倍，然后将原来的数组拷贝到新数组中。
3、Arraylist由于底层为数组结构，所有查找的操作比较快
linkedList
1、LinkedList底层结构是基于链表的形式存储的，可以存储在分散的内存中，即每一个元素都指向下一个元素，形成链表结构。
2、LinkedList底层由于是链表结构，因此进行插入、增加、删除的操作比较快。
3、LinkedList比ArrayList开销更大，因为LinkedList的节点除了存储数据，还需要存储引用（该引用是指还需将当前元素指向下个元素节点）

2、Collection.sort 和Arrays.sort的区别？

Collections.sort是基于list集合的排序。
image.png
Arrays.sort是基于数组的排序。
image.png

3、 Collections.sort(list)的底层原理

image.png

  1. Collections类
  2.     public static <T extends Comparable<? super T>> void sort(List<T> list) {
  3.         list.sort(null);
  4.     }
  6.  List接口   
  7.      default void sort(Comparator<? super E> c) {
  8.         Object[] a = this.toArray();
  9.         Arrays.sort(a, (Comparator) c);
  10.         ListIterator<E> i = this.listIterator();
  11.         for (Object e : a) {
  12.             i.next();
  13.             i.set((E) e);
  14.         }
  15.     }
  16.     Arrays工具类
  17.         public static <T> void sort(T[] a, Comparator<? super T> c) {
  18.         if (c == null) {
  19.             sort(a);
  20.         } else {
  21.             if (LegacyMergeSort.userRequested)
  22.                 legacyMergeSort(a, c);//归并排序
  23.             else
  24.                 TimSort.sort(a, 0, a.length, c, null, 0, 0);//合并排序和插入排序的结合
  25.         }
  26.     }

★4. HashMap原理，java8做了什么改变

HashMap是以键值对(key-value)的形式进行元素的存储，可以存储null值
JDK1.7
jdk1.7，hashmap底层存储数据是基于数组（桶）+链表形式进行的。
JDK1.8
jdk1.8，hashmap底层存储数据是基于数组（桶）+链表+红黑树形式进行存储的，将链表的长度大于阈值（8），链表将改为红黑树进行存储，避免了元素过多造成的效率低下问题。
jdk1.8中HasmMap put()方法的底层原理：
step1：首先判断当前hashmap是否为空，如果为空，则进行扩容；如果不为空，则进行键值对（key-value）的插入。
step2： 调用插入键值对的key的hashCode()值，计算对应的hash值（该hash值对应的是键值对（key-value）插入的索引位置），然后判断该位置索引上是否存在其他键值对，如果不存在，那么直接插入；如果存在，产生了哈希冲突，则需要进行进一步判断。(底层为[ ]Node数组)
step3：若key对应的hash值所在的索引位置上已经有其他元素了，那么调用key的equals()方法和table[i]的euqals()方法(该位置上的数)，比较是否相同，如果相同，直接将table[i]进行覆盖，如果不相同，进行插入。
step4：key-value插入到该索引位置时，判断是否为红黑树，如果是，则直接插入；如果不是，则遍历链表，遇到重复值就覆盖，否则就直接插入，若链表的长度大于阈值8，则将链表结构转为红黑树结构。
step5：执行完成后，看hashmap的size值是否大于阈值（数组的容量*负载因子），如果大于阈值，则需要进行扩容。

★5、Hashmap中一些常量设计的目的？

5.1 为什么hashmap的初始容量为1<<4?

分两个维度，第一个是为什么是2的幂，第二个是16而不是8或32.
image.png
（1）hashmap定位key的下标索引位置是通过（n-1）& hash进行下标索引位置确定的，n表示hashmap的初始容量，hash表示key的hash值。当初始化大小n是2的倍数时， (n-1)&hash等价于 n%hash。定位下标一般用取余法，为什么这里不用取余呢？

  - 因为，与运算（&）比取余（%）运算效率高
  - 求余运算： a % b就相当与a-(a / b)*b 的运算。
  - 与运算： 一个指令就搞定

因此，默认初始化大定义为2的幂，就是为了使用更高效的与运算。
（2）如果太小，4或者8，扩容比较频繁；如果太大，32或者64甚至太大，又占用内存空间。

5.2 为什么hashmap的默认加载因子为0.75?

综合时间和空间的考虑，如果加载因子为0.5，那么填充到一半就需要进行扩容，会导致扩容过于频繁。
如果加载因子为1，那么需要完全填充满才进行扩容，容易造成哈希冲突。


作为一般规则，默认负载因子（0.75）在时间和空间成本上提供了良好的权衡。
负载因子数值越大，空间开销越低，但是会提高查找成本（体现在大多数的HashMap类的操作，包括get和put）。
设置初始大小时，应该考虑预计的entry数在map及其负载系数，并且尽量减少rehash操作的次数。
如果初始容量大于最大条目数除以负载因子，rehash操作将不会发生。

5.3 为什么hashmap红黑树产生的阈值为8？

Ideally, under random hashCodes, the frequency of
     * nodes in bins follows a Poisson distribution
     * (http://en.wikipedia.org/wiki/Poisson_distribution) with a
     * parameter of about 0.5 on average for the default resizing
     * threshold of 0.75, although with a large variance because of
     * resizing granularity. Ignoring variance, the expected
     * occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
     * factorial(k)). The first values are:
     *
     * 0:    0.60653066
     * 1:    0.30326533
     * 2:    0.07581633
     * 3:    0.01263606
     * 4:    0.00157952
     * 5:    0.00015795
     * 6:    0.00001316
     * 7:    0.00000094
     * 8:    0.00000006
     * more: less than 1 in ten million

  大概的解释为：
             理想状态中，在随机哈希码情况下，对于默认0.75的加载因子，桶中节点的分布频率服从参数为0.5的泊松分布，即使粒度调整会产生较大方差。
            由对照表，可以看到链表中元素个数为8时的概率非常非常小了，所以链表转换红黑树的阀值选择了8。

5.4 底层的红黑树有什么特征？

红黑树本质上是一种二叉查找树，但它在二叉查找树的基础上额外添加了一个标记（颜色），同时具有一定的规则。这些规则使红黑树保证了一种平衡，插入、删除、查找的最坏时间复杂度都为 O(logn)。
image.png
红黑树的特点：

  1. 每个节点要么是红色，要么是黑色；
  1. 根节点永远是黑色的；
  1. 所有的叶节点都是是黑色的（注意这里说叶子节点其实是上图中的 NIL 节点）；
  1. 每个红色节点的两个子节点一定都是黑色；
  1. 从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点；

红黑树的左旋/右旋操作：
插入或删除节点后，尽可能的保持红黑树的特性。
1、左旋：以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。如图3。
2、右旋：以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。如图4。
3、变色：结点的颜色由红变黑或由黑变红。
红黑树的查找操作：
因为红黑树是一颗二叉平衡树，并且查找不会破坏树的平衡，所以查找跟二叉平衡树的查找无异：
从根结点开始查找，把根结点设置为当前结点；
1.若当前结点为空，返回null；
2.若当前结点不为空，用当前结点的key跟查找key作比较；
3.若当前结点key等于查找key，那么该key就是查找目标，返回当前结点；
4.若当前结点key大于查找key，把当前结点的左子结点设置为当前结点，重复步骤2；
5.若当前结点key小于查找key，把当前结点的右子结点设置为当前结点，重复步骤2


红黑树的插入操作：（需要进行插入+自平衡操作）
1.若根结点为空，那么插入结点作为根结点，结束。
2.若根结点不为空，那么把根结点作为当前结点；
3.若当前结点为null，返回当前结点的父结点，结束。
4.若当前结点key等于查找key，那么该key所在结点就是插入结点，更新结点的值，结束。
5.若当前结点key大于查找key，把当前结点的左子结点设置为当前结点，重复步骤4；
6.若当前结点key小于查找key，把当前结点的右子结点设置为当前结点，重复步骤4；
image.png

6、 List 、set 和map的区别？

list接口和set接口是Collect接口的子类。
lsit主要是来存储有序的、可重复的数据，可以插入多个null值，list是按照对象进入的顺序保存对象，可以使用迭代器iterator遍历，也可以采用get(index)索引的方法获取指定索引的值。
set主要是来存储无序的、不可重复的数据，只允许插入一个null值，set底层其实是基于map来存储的，set的元素就等于map的键值（key），一般都使用iterator迭代器来进行遍历。
而map主要通过存储键值对的形式（key-values）来进行存储。
list底层存储原理有基于数组存储（Arraylist）、链表存储（linkedList）。
set和map底层存储原理基于数组+链表、数组+红黑树存储。

7、 队列结构中poll（）方法和remove（）方法的区别？

poll（）方法和remove（）方法都是从队列头取出一个元素，其区别在于若此时队列为空，poll（）返回的是一个null值，而remove（）方法则会抛出异常。

8、Hashmap、Hashtable、Concurrentmap的共同点和区别？

1、底层原理：
hashmap底层是基于数组Node[ ]+链表+红黑树实现
hashtable底层是基于数组Node[ ]+链表+红黑树实现
ConcurrentHashMap底层是基于数组Node[ ]+链表+红黑树实现
2、是否可以存储空值：
hashmap可以存储key-values都为null的值，key为null时一般存储在下标为0的位置
hashtable不能存储key-values为null的值
ConcurrentHashMap 不能存储key-value为null的值
3、线程是否安全：
hashmap线程不安全，若并发操作hashmap会在put（）方法是造成死循环
hashtable是线程安全的，因为使用了synchronized关键词
ConcurrentHashMap 是线程安全的，使用锁分段技术。
4、初始容量：
hashmap初始容量为16
hashtable的初始容量为11
5、继承的符类：
hashmap继承了map接口
hashtable继承了map接口和Dictionary抽象类

9、ArrayList中add/remove方法的规则？

不能使用增强for循环 for（元素类型 元素名称：遍历对象obj）——其底层是基于iterator和while循环的。

用增强for循环进行arraylist遍历中add（）和remove（）方法，会抛出java.util.ConcurrentModificationException的异常。触发了一个Java集合的错误检测机制——fail-fast（快速失败）：fail-fast，即快速失败，它是Java集合的一种错误检测机制。当多个线程对集合（非fail-safe的集合类）进行结构上的改变的操作时，有可能会产生fail-fast机制，这个时候就会抛出ConcurrentModificationException（当方法检测到对象的并发修改，但不允许这种修改时就抛出该异常）。

10、Array数组和list集合之间的转换？

集合转换为数组：
使用泛型，无需进行强制转换

 //集合转换成数组
     List<String> list=new ArrayList<>();
     list.add("杜");
     list.add("黎");
     list.add("明");

     list.toArray(new String[list.size()]);

数组转换为集合：
一般不直接使用Arrays.aslist()，这样创建的集合无法进行元素的添加，因为Arrays.aslist()方法返回的不是util包下的Arraylist类，而是内部类Arraylist；

    //数组转换为集合
     //方式1：
     List<String> list4=new ArrayList<>(strings.length);
     Collections.addAll(list4,strings);
     //方式2：
     List<String> list5=new ArrayList<>(Arrays.asList(strings));

11、如何保证集合不被修改？

Collections.unmodifiableMap();
Collections.unmodifiableList();
Collections.unmodifiableSet();

12、 Iterator迭代器的作用？ ListIterator和Iterator的区别？

lterator迭代器常用集合的遍历，它的特点是更加安全，因为它可以确保，在当前遍历的集合元素被更改的时候，就会抛出 ConcurrentModificationException 异常。。

  //利用lterator实现集合的遍历
        Iterator<String> iterator=list4.iterator();
        while (iterator.hasNext()){
            String next = iterator.next();
            System.out.println(next);
        }

Listlterator和lterator的区别？
主要差异在于拥有不同的方法，Listlterator拥有更多的方法
image.pngimage.png

相比于lterator，Listlterator迭代器只能操作List类及其子类的集合，其拥有更多的方法，如逆向遍历、获取遍历的索引值、还可以实现对对象的修改和添加。

13、HashSet的底层原理

HashSet可以存储无序、不可重复的元素:
HashSet底层创建了一个Hashmap的对象，其添加元素的原理是基于Hashmap：
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
所以hashset添加的元素 都是不可重复的。HashSet添加元素时，首先会调用元素的hashCode（）方法，计算元素的哈希值，该哈希值代表元素存储在底层数组所在的位置索引：如果该位置上没有其他元素，那么就把需要添加的元素直接添加上去；如果该位置上已经有其他元素了，那么需要调用元素的equal()方法进行进一步的判断：
如果需要添加的元素key的equal（）方法结果和该位置上的元素key1的equal（）元素相同，那么直接进行替换；如果两个元素的equals()元素不同，就会散列到其他位置。

14、HaschCode()和equals()方法

HashCode()的主要作用是获取元素的哈希值，也成为散列码。返回的是一个int类型的整数，表示在哈希表中的索引位置，HashCode()定义在Object类，因此java中所有类型都包含HashCode（）函数。散列表（哈希表）中是以键值对的形式进行存储，它的特点是根据“键值key”快速检索出对应的值。
equals（）方法的主要作用是来比较两个对象根据equal（）方法是否相等。
HashCode()+equals()实现集合Set、Map的存储方式。

15、 map中的ConcurrentHashMap的底层实现原理？

map集合中，针对于多线程操作，Hashtable和concurrentHashMap都是线程安全的，但是使用Hashtable的代价太大（Hashtable中的每一个方法都加了synchronizatized同步方法），因此一般采用concurrentHashMap。
JDK1.7版本的ConcurrentHashMap底层原理：
jdk1.7的concurrentHashMap是基于ReentranLock+Segment+HashEntry组成的，其中一个Segment包含一个HashEntry数组，每个HashEntry又包含一个链表结构（与hashmap相似）。
Segment分段锁继承reentranlock，锁定操作的segment，每一把锁锁定自己的segment，其他segment不受影响，这样就不存在锁竞争机制了，并发度即为segment的个数，有效提高并发效率。
jdk1.7元素查询采用二次hash的方法，第一次计算的hash值定位到segment，第二次计算的hash值定位到元素链表的头部
get（）方法也无需加锁，有volatile保证线程安全。
JDK1.8版本的ConcurrentHashMap底层原理：
jdk1.8的concurrentHashMap基于Synchronized+CAS+Node+红黑树，其中通过一个Node[]数组来保存添加到map中的键值对，而在同一个数组位置是通过链表和红黑树的形式来保存的。其中node的val和next都用volatile来保证可见性，从而保证每一行数据进行加锁。
Synchronized+CAS保证并发控制，其中查找、替换、赋值操作都是CAS乐观锁进行，一些扩容、hash冲突时采用synchronizatized来锁。直接使用synchronized锁住hash后得到的数组下标位置中的第一个元素，不影响其他元素的读写，锁粒度更细，效率更高。扩容时，阻塞所有的读写操作，并发扩容。
读写操作无需加锁，因为有volatile修饰node数组的val和next节点。
数组采用volatile修饰，保证在扩容时被读线程感知。