4、集合面试题

1. Arraylist与LinkedList区别

从底层结构、效率、开销等方面进行区分
ArrayList
1、Arraylist底层结构为一个Object[] 类型的数组进行元素的存储。
2、Arraylist由于底层为数组结构，所有查找的操作比较快
linkedList
1、LinkedList底层结构是基于链表的形式存储的，即每一个元素都指向下一个元素，形成链表结构。
2、LinkedList底层由于是链表结构，因此进行插入、增加、删除的操作比较快。
3、LinkedList比ArrayList开销更大，因为LinkedList的节点除了存储数据，还需要存储引用（该引用是指还需将当前元素指向下个元素节点）

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

Collections.sort是基于list集合的排序。

Arrays.sort是基于数组的排序。

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

Collections类
    public static <T extends Comparable<? super T>> void sort(List<T> list) {
        list.sort(null);
    }
 List接口   
     default void sort(Comparator<? super E> c) {
        Object[] a = this.toArray();
        Arrays.sort(a, (Comparator) c);
        ListIterator<E> i = this.listIterator();
        for (Object e : a) {
            i.next();
            i.set((E) e);
        }
    }
    Arrays工具类
        public static <T> void sort(T[] a, Comparator<? super T> c) {
        if (c == null) {
            sort(a);
        } else {
            if (LegacyMergeSort.userRequested)
                legacyMergeSort(a, c);//归并排序
            else
                TimSort.sort(a, 0, a.length, c, null, 0, 0);//合并排序和插入排序的结合
        }
    }

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.

（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。

6、 List 、set 和map的区别？

list接口和set接口是Collect接口的子类。
lsit主要是来存储有序的、可重复的数据，可以插入多个null值。
set主要是来存储无序的、不可重复的数据，只允许插入一个null值，set底层其实是基于map来存储的，set的元素就等于map的键值（key）。
而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的值
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拥有更多的方法

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