秋春招总结|Java集合类型面试最全总结【易错,易问】集合论|java

前言：之前有介绍过在reids中的五种常用类型： string hash list set zset 五种数据类型。今天来介绍一下关于 java中的集合类型。还会进行基础的介绍不同之处。
基础使用
一直都想记录一下也是因为在刷题过程中，也都用用到各种的栈，队列。今日打算痛定思痛记录一番：
栈 Stack 在《算法》（第四版）中对栈的基础函数有以下比较常用的：

方法	介绍
Stack()	创建一个新栈
void push(Item item )	添加一个新的元素
Item pop（）	删除最近添加的元素，将元素从栈顶取出，有返回值
boolean isEmpty（）	判断栈是否已经为空
int size()	返回栈的长度

注：关于栈的使用地方非常的多例如对于很多的数的操作：数的前序和后序遍历，对于表达式的求解，前缀与后缀表达式都会有相对应的涉及。
队列 Queue 同上：

方法	介绍
Queue ()	创建一个空队列
void enqueue(Item item)	添加一个元素到队列中
Item dequeue ()	取出队列中最早添加的元素
boolean isEmpty()	是否为空
int size()	此时队列的长度

注：虽然对于队列来说，使用的比较少，但是基础的操作，对于树的层序遍历还是会使用到，同时对于判断平衡二叉树时候也会使用到。
基础面试
说一说 List，Map，Set三者之前的区别

List：存储的元素是不唯一的（可以存储一组由多个元素引用相同的对象），有序，可以插入时候插入多条的null值。
Set 不允许有重复的元素，不允许有多个元素应用的是相同的对象，只允许有一个null元素。
Map：使用键值对进行存取，Map本身会维护Key与Value之间的关系，在理论上不同的key可以引用相同的对象，但是Key值不能够是重复的。

Array与ArrayList有什么区别

Array可以包含基本类型的对象类型，但是ArrayLsit只能包含对象类型的数据类型。
Array的大小值是固定的，ArrayList的动态变化的
ArrayList 还提供了Array不具有的方法，addAll()，removeAll()，iterator()。
对于基本数据类型，集合有采用自动封箱来减少代码量。但是对于处理固定大小的数据类型时候，处理起来就会比较慢

ArrayList 和LinkedList 的区别

是否保证线程安全：都不是同步的，也就是说都不能够保证线程的安全性。
底层的数据结构： ArrayList底层使用的是 Object数组； LinkedList 底层使用的是双向链表来实现
插入元素与删除元素时候是否会受到位置的影响：如前面所说的 Arr底层使用的是数组，所以在查找的效率会比较高，但是对于插入和删除而言，会动用到很多其他的元素。对于LinkedList而言底层采用链表结构对于查找不是很有利，但是进行插入和删除会比较快。
是否支持随机访问： LinkedList 底层使用链表，不支持随机访问。ArrayList 底层使用Object数组可以随机访问
空间占用： ArrayList 的空间浪费主要体现在List列表的结尾会预留一定量的空间容量，而LinkedList的空间发费体现在她的每一个元素消耗的空间都比Arr要多（因为对于一个链表的节点，不仅要存取其值，还要存取其前驱节点和后继节点信息。）

什么是迭代器 Iterator 接口中提供了很多对集合元素迭代的方法。每个集合中都有可以返回迭代器对象的方法iterator()。迭代器在迭代的过程中还可以删除底层的元素。
iterator和ListIterator的区别

Iterator可以用来遍历Set与List，但是ListIterator只能用来遍历List.
lterator 只能向前遍历（next）。而ListIterator可以向前遍历，也可以向后遍历（previous()）
*ListIterator 实现了Iterator接口

ArrayList 和Vector 有什么区别都是集成了List 接口（List接口继承了Collection接口）都是有序的集合，相当于一种动态的数组可以按照位置索引号取出某个元素，并且运行元素是重复的，这是与HashSet最大不同的地方。主要有两个方面的区别：

同步性：
对于 Vertor是线程安全的，也就是说她的方法是线程同步的，而ArrayList是线程不安全的。如果有一个线程访问集合，最好使用ArrayList，不用考虑线程安全的情况下，效率会更高。对于有多个线程访问时候，使用到Vertor 因为不需要我们自己去考虑编写线程安全的代码。
数据增长:
对于ArrayList 与 Vertor都有一个初始的容量大小，当数据增长到存储的容量时候，就需要增加空间，他们的存储空间，每次都会增加一定数量的存储空间，对于Vertor增长的是原来的两倍，而在Arr中源码表示的是增长 1.5倍。Arr与Vertor都可以设置初始的空间大小。Ver还可以设置增长的空间大小，但是Arr没有提供增长空间的方法。

ArrayList，Vertor，LinkedList的存储特性 ArrayList与 Vertor都是使用数组进行存储，相对之下，查找较快，但是插入和删除比较慢，LinkedList使用双向链表与之相反，关于为什么Vertor的效率较Arr慢，是因为使用了synchronized（线程安全）所以性能就会较差。
HashMap 和HashTable 的区别两者都实现了Map接口主要区别在安全性同步性，和速度上。

是否线程安全： HashMap是线程不安全，对于 Hashtable 内部都经过了synchronized的修饰，线程同步安全。
2.效率：由于synchronize的修饰效率会交HashMap差一点。
对于 null key 与 null value的支持：对于HashMap 支持null key但是只能有一个key的值为null。对于 value可以有多个的value值为null。
而在HashTable中 key值是不可以为null的。
底层数据结构的处理：对于HashMap 在JDK1.8中增加了红黑树的处理，对于一个数组中的链表长度大于阙值（8）时候会将链表自动转换为红黑树，以增加效率，但是在 HashTable中没有这样的处理。

HashMap 与 HashSet的区别

HashMap	HashSet
实现了Map接口	实现了Set接口
储存键值对	仅仅储存对象
使用了Key值一系列的计算来计算hashCode	使用成员对象来计算 hashCode 对于两个对象来说，hashcode可能是相同的，所以使用 equals来判断对象的相等性

HashSet如何检查是否重复往HashSet中存放一个元素时候 HashSet首先会根据对象的hashCode值判断当前集合中此hashCode对应的位置有没有值，如果没有就直接添加，若是有就使用equals 来判断两个对象是否相同，相同就不再存储（保证了Set集合的不可重复性）否则就散列到其他位置存储。
Collection和Collections的区别

Collection是集合类的上级接口，继承他的接口主要有Set和List
Collections 仅是针对集合封装类的一个类，提供一系列的静态方法对各种几何的搜索，排序，线程安全化等操作。在java.util 包下面。

List、Map、Set 三个接口，存取元素时，各有什么特点？

首先，List 与 Set 具有相似性，它们都是单列元素的集合，所以，它们有一个功共同的父接口，叫 Collection。Set 里面不允许有重复的元素，所谓重复，即不能有两个相等（注意，不是仅仅是相同）的对象，即假设 Set 集合中有了一个 A 对象，现在我要向 Set 集合再存入一个 B 对象，但 B 对象与 A 对象equals 相等，则 B 对象存储不进去，所以，Set 集合的 add 方法有一个 boolean 的返回值，当集合中没有某个元素，此时 add 方法可成功加入该元素时，则返回 true，当集合含有与某个元素 equals 相等的元素时，此时 add 方法无法加入该元素，返回结果为 false。Set 取元素时，没法说取第几个，只能以 Iterator 接口取得所有的元素，再逐一遍历各个元素。
List 表示有先后顺序的集合，注意，不是那种按年龄、按大小、按价格之类的排序。当我们多次调用 add(Object) 方法时，每次加入的对象就像火车站买票有排队顺序一样，按先来后到的顺序排序。有时候，也可以插队，即调用 add(int index,Obj e) 方法，就可以指定当前对象在集合中的存放位置。一个对象可以被反复存储进 List 中，每调用一次 add 方法，这个对象就被插入进集合中一次，其实，并不是把这个对象本身存储进了集合中，而是在集合中用一个索引变量指向这个对象，当这个对象被 add 多次时，即相当于集合中有多个索引指向了这个对象，如图 x 所示。List 除了可以以 Iterator 接口取得所有的元素，再逐一遍历各个元素之外，还可以调用 get(index i) 来明确说明取第几个。
Map 与 List 和 Set 不同，它是双列的集合，其中有 put 方法，定义如下：put(obj key,obj value)，每次存储时，要存储一对 key/value，不能存储重复的 key，这个重复的规则也是按 equals 比较相等。取则可以根据 key 获得相应的 value，即 get(Object key) 返回值为 key 所对应的 value。另外，也可以获得所有的 key 的结合，还可以获得所有的 value 的结合，还可以获得 key 和 value 组合成的 Map.Entry 对象的集合。
List 以特定次序来持有元素，可有重复元素。Set无法拥有重复元素, 内部排序。Map 保存 key-value 值，value 可多值。 HashSet 按照 hashcode 值的某种运算方式进行存储，而不是直接按 hashCode 值的大小进行存储。例如，“abc” —> 78，“def” —> 62，“xyz” —> 65 在 hashSet 中的存储顺序不是 62,65,78，

两个对象值相同 (x.equals(y) == true)，但却可有不同的 hash code，这句话对不对? 对。如果对象要保存在 HashSet 或 HashMap 中，它们的 equals 相等，那么，它们的 hashcode 值就必须相等。如果不是要保存在 HashSet 或 HashMap，则与 hashcode 没有什么关系了，这时候 hashcode 不等是可以的，例如 arrayList 存储的对象就不用实现 hashcode，当
然，我们没有理由不实现，通常都会去实现的。
heap 和stack 有什么区别 Java 的内存分为两类，一类是堆内存，一类是栈内存。栈内存是指程序进入到一个方法时候，会为这个方法单独分配一块私属空间，用于存储这个方法内部的局部变量，当这个方法结束的时候，分配给这个方法的栈会释放，这个栈中的变量也会随之释放。
堆与栈作用于不同的内存，一般用于存放的是不在当前方法栈中的那些数据，例如使用new 创建的对象都是存放在堆上，所以说不会随着方法的结束而消失。并且在方法中的局部变量使用到了final修饰后，放在堆中（此处使用到了jvm的相关知识）。
LinkedhashMap的实现原理也是基于HashMap实现的不同的是它定义了一个Entry header ，这个 header不是存在方Table里面，是额外独立出来的。LinkedHashMap 通过继承 hashMap 中的 Entry, 并添加两个属性 Entry
before,after, 和 header 结合起来组成一个双向链表，来实现按插入顺序或访问顺序排序LinkedHashMap 定义了排序模式 accessOrder，该属性为 boolean 型变量，对于访问顺序，为 true；对于插入顺序，则为 false。一般情况下，不必指定排序模式，其迭代顺序即为默认为插入顺序。
Comparable和Compartor接口是干什么，列出区别 Java 提供了只包含一个conpareTo方法的Comparable接口，这个方法可以给两个对象排序，用来返回负数，0 和正数，来表示小于等于大于。
对于 Compartor提供了compare() 和 equals() 两个方法。compare和compareTo的使用大概相同，传进去两个参数。equals() 需要一个对象作为参数，用来判断输入的参数是否和compartor相等，只有两者相等时候返回true；
框架大体
-》 collection