1. java 容器都有哪些？

图片.png

2. Collection 和 Collections 有什么区别？

• java.util.Collection 是一个集合接口（集合类的一个顶级接口）。它提供了对集合对象进行基本操作的通用接口方法。Collection接口在Java 类库中有很多具体的实现。Collection接口的意义是为各种具体的集合提供了最大化的统一操作方式，其直接继承接口有List与Set。
• Collections则是集合类的一个工具类/帮助类，其中提供了一系列静态方法，用于对集合中元素进行排序、搜索以及线程安全等各种操作。

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

图片.png

4. HashMap 和 Hashtable 有什么区别？

• 1.hashMap去掉了HashTable 的contains方法，但是加上了containsValue（）和containsKey（）方法。
• 2.hashTable同步的，而HashMap是非同步的，效率上比hashTable要高。
• 3.hashMap允许空键值，而hashTable不允许。

5. 如何决定使用 HashMap 还是 TreeMap？

• 对于在Map中插入、删除和定位元素这类操作，HashMap是最好的选择。然而，假如你需要对一个有序的key集合进行遍历，TreeMap是更好的选择。
• 基于你的collection的大小，也许向HashMap中添加元素会更快，将map换为TreeMap进行有序key的遍历。

6.HashMap

6.1 说一下 HashMap 的实现原理？

• HashMap概述： HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。
• HashMap的数据结构： 在java编程语言中，最基本的结构就是两种，一个是数组，另外一个是模拟指针（引用），所有的数据结构都可以用这两个基本结构来构造的，HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体。
• 当我们往Hashmap中put元素时,首先根据key的hashcode重新计算hash值,根据hash值得到这个元素在数组中的位置(下标),如果该数组在该位置上已经存放了其他元素,那么在这个位置上的元素将以链表的形式存放,新加入的放在链头,最先加入的放入链尾.如果数组中该位置没有元素,就直接将该元素放到数组的该位置上。
• 需要注意Jdk 1.8中对HashMap的实现做了优化,当链表中的节点数据超过八个之后,该链表会转为红黑树来提高查询效率,从原来的O(n)到O(logn)

6.2 HashMap扩容原理？？

• 当HashMap的元素越来越多的时候其发生碰撞的几率也会越来越大（数组长度固定）。所以为了提高查询效率就需要对HashMap进行扩容，但是扩容后会对性能有较大的影响，因为数组长度扩展以后会把原来的数组链表的元素都移动到新的数组中。
• HashMap的初始化容量是16，HashMap有一个加载因子（loadFactor）默认值为0.75。当HashMap中的元素个数超过HashMap容量0.75的时候就会发生扩容。扩容后的数组大小为2原始容量，即二倍。
• 举个栗子：原始容量是16，加载因子（loadFactor）是0.75。也就是说当HashMap中元素的个数>16*0.75=12的时候就会发生扩容。

6.3 HashMap如何解决碰撞的?

HashMap使用链表来解决碰撞冲突，当数组中的key的hash值位置上有元素时，就把这个元素放入链表的头部，最先加入的放到链表的尾部。

6.4 为什么要在jdk1.8以后在HashMap中引入红黑树？

• 引入红黑树是为了提高HashMap的查询效率。
• 链表的时间复杂度是O(n)，红黑树的时间复杂度O(logn)，很显然，红黑树的复杂度是优于链表的;

6.5 为什么链表个数大于8个才会选择使用红黑树?

• 源码上说，为了配合使用分布良好的hashCode，树节点很少使用。并且在理想状态下，受随机分布的hashCode影响，链表中的节点遵循泊松分布，而且根据统计，链表中节点数是8的概率已经接近千分之一，而且此时链表的性能已经很差了。所以在这种比较罕见和极端的情况下，才会把链表转变为红黑树。
• 因为链表转换为红黑树也是需要消耗性能的，特殊情况特殊处理，为了挽回性能，权衡之下，才使用红黑树，提高性能。

6.6 既然数组+红黑树这么棒，那为什么hashmap不直接就用数组+红黑树呢?

• 因为树节点所占空间是普通节点的两倍，所以只有当节点足够多的时候，才会使用树节点。也就是说，节点少的时候，尽管时间复杂度上，红黑树比链表好一点，但是红黑树所占空间比较大，综合考虑，认为只能在节点太多的时候，红黑树占空间大这一劣势不太明显的时候，才会舍弃链表，使用红黑树。

6. 说一下 HashSet 的实现原理？

• 1.HashSet底层由HashMap实现
• 2.HashSet的值存放于HashMap的key上
• 3.HashMap的value统一为PRESENT

7. ArrayList 和 LinkedList 的区别是什么？

• 最明显的区别是 ArrrayList底层的数据结构是数组，支持随机访问，而 LinkedList 的底层数据结构是双向循环链表，不支持随机访问。
• 使用下标访问一个元素，ArrayList 的时间复杂度是 O(1)，而 LinkedList 是 O(n)。

8. 如何实现数组和 List 之间的转换？

1.List转换成为数组：调用ArrayList的toArray方法。
2.数组转换成为List：调用Arrays的asList方法。

9.ArrayList 和 Vector 的区别是什么？

• Vector是同步的，而ArrayList不是。然而，如果你寻求在迭代的时候对列表进行改变，你应该使用CopyOnWriteArrayList。
• ArrayList比Vector快，它因为没有同步，不会过载。
• ArrayList更加通用，因为我们可以使用Collections工具类轻易地获取同步列表和只读列表。

10. Array 和 ArrayList 有何区别？

1.Array可以容纳基本类型和对象，而ArrayList只能容纳对象。
2.Array是指定大小的，而ArrayList大小是不固定的,ArrayList随着数据逐渐增大而增大。

3. Array没有提供ArrayList那么多功能，比如addAll、removeAll和iterator等。

11. 在 Queue 中 poll()和 remove()有什么区别？

poll() 和 remove() 都是从队列中取出一个元素，但是 poll() 在获取元素失败的时候会返回空，但是 remove() 失败的时候会抛出异常。

12. 哪些集合类是线程安全的？

• vector：就比arraylist多了个同步化机制（线程安全），因为效率较低，现在已经不太建议使用。在web应用中，特别是前台页面，往往效率（页面响应速度）是优先考虑的。
• statck：堆栈类，先进后出。
• hashtable：就比hashmap多了个线程安全。
• enumeration：枚举，相当于迭代器。

13. Iterator 怎么使用？有什么特点？

Java中的Iterator功能比较简单，并且只能单向移动：
(1) 使用方法iterator()要求容器返回一个Iterator。第一次调用Iterator的next()方法时，它返回序列的第一个元素。注意：iterator()方法是java.lang.Iterable接口,被Collection继承。
(2) 使用next()获得序列中的下一个元素。
(3) 使用hasNext()检查序列中是否还有元素。
(4) 使用remove()将迭代器新返回的元素删除。
Iterator是Java迭代器最简单的实现，为List设计的ListIterator具有更多的功能，它可以从两个方向遍历List，也可以从List中插入和删除元素。

14. Iterator 和 ListIterator 有什么区别？

• Iterator可用来遍历Set和List集合，但是ListIterator只能用来遍历List。
• Iterator对集合只能是前向遍历，ListIterator既可以前向也可以后向。
• ListIterator实现了Iterator接口，并包含其他的功能，比如：增加元素，替换元素，获取前一个和后一个元素的索引，等等。

15.怎么确保一个集合不能被修改？

• 通过Collections工具类的静态方法unmodifiableXxx对可变集合进行封装。
• 通过Collections的静态方法emptyXxx返回一个空的不可变集合。
• 通过Collections静态方法singletonXxx返回带有特定对象的不可变集合。

16. HashSet集合存储数据结构（哈希表)

图片.png

17. Comparable和Comparator区别？

• Comparable接口
  实现Comparable接口类表示这个类型的对象可以进行比较大小的。 这种可以比较大小的对象可以进行自然排序。
• Comparator接口
  1.比较器用于实现对象任意属性进行比较大小。
  2.在排序时候可以通过指定属性比较器实现任意属性排序。
• 在排序时候Comparable接口用于进行自然排序，而Comparator接口进行自定义排序，自定义排序更加灵活方便而常用。
• 设计上Comparable不推荐使用，因为对程序本身具有侵入性。

18 CAS实现原理，以及ABA问题

• 一个CAS方法包含三个参数CAS(V,E,N)。V表示要更新的变量，E表示预期的值，N表示新值。只有当V的值等于E时，才会将V的值修改为N。如果V的值不等于E，说明已经被其他线程修改了，当前线程可以放弃此操作，也可以再次尝试次操作直至修改成功。基于这样的算法，CAS操作即使没有锁，也可以发现其他线程对当前线程的干扰（临界区值的修改），并进行恰当的处理。
• 由于 CAS 设计机制就是获取某两个时刻(初始预期值和当前内存值)变量值，并进行比较更新，所以说如果在获取初始预期值和当前内存值这段时间间隔内，变量值由 A 变为 B 再变为 A，那么对于 CAS 来说是不可感知的，但实际上变量已经发生了变化；解决办法是在每次获取时加版本号，并且每次更新对版本号 +1，这样当发生 ABA 问题时通过版本号可以得知变量被改动过。JDK 1.5 以后的 AtomicStampedReference 类就提供了此种能力，其中的 compareAndSet 方法就是首先检查当前引用是否等于预期引用，并且当前标志是否等于预期标志，如果全部相等，则以原子方式将该引用和该标志的值设置为给定的更新值。

数据结构

1.数组(线性表)

• 0个或多个数据元素的有限序列。
• 它是一个顺序存储结构，你可以把它理解称为一个数组。
• 例如：存储的第一个元素在数组下标为0的位置，第二个在数组下标为1的位置依次类推。由于线性表的这个顺序存储特性，导致了其查询效率特别高，以为只需要拿到下标就可以获取到数组下标对应的元素值。但是其插入和删除的效率就不敢恭维了，由于是顺序存储导致了数组中不可能有空位置，如果再数组下标为0的位置删除一个元素，那么数组中所有的元素都需要向前移动一位，其时间复杂度为(O(n))。插入也是同样的道理，如果在数组中间位置插入一个元素，则插入位置之后的所有数组元素都需要向后移动一位，效率相对糟糕。
• 优点：查询效率很高
• 缺点：插入和删除效率低下

2.链表

• 用一组任意存储单元存储线性表的数据元素，这组存储单元可以是连续的也可以是不连续的。
• 链表也是一种线性表，这是它里面的元素可以是连续的也可以是不连续的，这就意味着不用提前开辟一块存储容量，当链表中没有元素时，不占用内存空间。数组中的元素必须是连续存储的，而链表不必这么干，我们可以在任意的内存地址中存储我们的链表元素，而这些内存地址还可以是分散的。这意味着我们在插入和删除的时候不需要做任何的移动操作。这就大大提高了插入和删除的效率。但是单链表的读取却是一个麻烦事，因为每次读取都需要从头开始查找，直到把元素找到为止，其时间复杂度为（O(n)）。
• 优点：插入和删除效率高;
• 缺点：查询效率低下;

3.二叉树(红黑树)

• 一棵树中有一个根节点，根节点下又有子节点和叶子节点，子节点下又有子节点和叶子节点，依次往下推构成了一颗完整的树。
• 优点：插入和删除的效力都相对较高
• 缺点：和数组、链表的优点相比，比较弱

感谢如下分享
HashSet集合存储数据结构（哈希表）
Java面试题（容器篇）
Java容器面试题
HashMap原理分析（含1.8以后的红黑树）