Java集合面试题汇总---较为全面，多处资料，自总结

1.简单介绍一下java集合？

集合分为collection和map，list和set时collection的主要实现类，list有序可重复的，set是无序，不可重复的，map是key，vlaue的存储形式，key是无序不可重复的，value，是无序可重复的。

list有这几个主要的实现类，分别是arraylist，linkedlist，vector，在jdk1.0的时候，作为有序可重复的集合，只有vector一个，list，arraylist，linkedlist这三个jdk1.2的时候才出现，jdk1.2时，就把vector，arraylist，linkedlist列为list的实现类，这三者的区别呢，按线程安全划分，vector是线程安全的，内部的方法都有synchronized进行修饰，所以效率低，arraylist，linkedlist线程是不安全的，比vector效率要高。

按底层存储结构划分，vector，arraylist底层都是基于object数组进行存储的，linkedlist是基于双向链表。

因为arraylist和vector底层是基于数组进行存储，所以查询很快，增删慢。linkedlist是双向链表，查询慢，增删快。arraylist底层数组在数组的尾部会预留一部分空间，如果采用尾插法的话，效率也是比较可观。

arraylist还有自动扩容的机制，每次扩容会是原来的1.5倍。会将原来的数组内容copy到新数组中去。

下面说一下set，set是无序不可重复的，这就意味着set集合中的值都是唯一的，在来说说它这个无序性，它这个无序性，不等同于随机性，它插入元素时，元素坐落的位置，是通过每个元素之间比较一下hashcode之后，以及如果相同在用equals判别，才决定其元素是否可以加入或者说加入的位置先后顺序。

set的主要实现类有hashSet、TreeSet、linkedhashSet，先说一下他们底层使用的数据结构，hashset底层是基于hashMap实现的，数组加链表，数组的默认长度为16，底层是采用hashMap来保存元素的，linkedhashset是hashSet的子类，内部是使用linkedhashMap来实现的。treeSet底层使用的是红黑树。

treeSet，向treeSet添加元素，要求是相同类的对象，会对结果进行排序，排序顺序是从小到大，它这个排序分定制排序和自然排序。

分别就是实现两个接口，实现了compareable接口的就是自然排序，然后重写里面的方法。

实现了compareto接口的就是定制排序。

map的主要实现类有hashMap，linkedHashMap，treeMap，hashTable，concurrentHashMap，线程安全问题呢，hashMap、linkedHashMap、treeMap是线程不安全的，hashTable，concurrentHashMap这两个是线程安全的，如果我们要使用map集合，考虑线程安全问题的话我们就使用concurrentHashMap。

在来说一下底层数据结构，HashMap，jdk1.8之前采用的是数组加链表的形式，也称为链表散列，HashMap 通过key 的 hashCode 经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置（这⾥的 n 指的是数组的⻓度），如果当前位置存在元素的话，就判断该元素与要存 ⼊的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲 突。

jdk1.8之后hashMap解决哈希冲突有了较大的变化，数据结构采用的是数组加链表加红黑树的方式实现的，当链表长度大于一定阈值，默认为8，就会将链表转换为红黑树以减少搜索的时间。

这里有一个问题，面试官问过我，为什么这个阈值是8，不能是别的么？我去百度搜了一下，解释说负载因子是0.75的时候，我们能计算出哈希碰撞的概率，阈值为8的时候，碰撞到第8次，也就是数组长度为8的时候概率已经非常小，几乎就是一个不可能的事件。 linkedHashMap，我的理解就是在hashMap基础上，多了一个linked，多了一个链表，多一层指向地址值的指针，保证在遍历map元素时，可以按照添加的顺序进行遍历，，原因就是在hashMap的基础上加了一对指针，一个指前，一个指后，对于频繁的遍历可以考虑使用linkedHashMap。

hashtable，线程安全，不能存储null的key和value。

treemap，保证按照添加的key和value进行排序，按key排序。