Java容器部分上（重要）
1.java容器都有哪些？（容器指的是集合类）
基本概念
Java容器类类库的用途是“持有对象”，并将其划分为两个不同的概念：
１）Collection：一个独立元素的序列，这些元素都服从一条或者多条规则。 List必须按照插入的顺序保存元素，而set不能有重复的元素。Queue按照排队规则来确定对象产生的顺序（通常与它们被插入的顺序相同）。
2）Map：一组成对的“键值对”对象，允许你使用键来查找值。
|Collection
| ├List
| │-├LinkedList
| │-├ArrayList
| │-└Vector
| │ └Stack
| ├Set
| │├HashSet
| │├TreeSet
| │└LinkedSet
|
|Map
├Hashtable
├HashMap
└WeakHashMap
2.Collection 和 Collections 有什么区别？
注： 1、java.util.Collection 是一个集合接口。它提供了对集合对象进行基本操作的通用接口方法。Collection接口在Java 类库中有很多具体的实现。Collection接口的意义是为各种具体的集合提供了最大化的统一操作方式。
2、java.util.Collections 是一个包装类。它包含有各种有关集合操作的静态多态方法。此类不能实例化，就像一个工具类，服务于Java的Collection框架。
3.List、Set、Map 之间的区别是什么？
答：
1.List：
可以允许重复对象、可以插入多个null元素、是一个有序容器
2.Set：
不允许重复对象、只允许一个null元素、无序容器
3.Map:
Map不是Collection的子接口或实现类。Map是一个接口、Map 的每个Entry都特有两个对象，也就是一个键一个值，Map可能会持有相同的值对象但键对象必须是唯一的、Map里可以拥有随意个niull值但最多只能有一个null键
4.HashMap 和 Hashtable 有什么区别？
1.Map是一个以键值对存储的接口。Map下有两个具体的实现，分别是HashMap和HashTable.
2.HashMap是线程非安全的，HashTable是线程安全的，所以HashMap的效率高于HashTable.
3.HashMap允许键或值为空，而HashTable不允许键或值为空.
4.继承关系不同：
HashTable
public class Hashtable<K,V> extends Dictionary<K,V>1.0
implements Map<K,V>, Cloneable, java.io.Serializable {}
HashMap
public class HashMap<K,V> extends AbstractMap<K,V>1.2
implements Map<K,V>, Cloneable, Serializable{}
5.HashMap性能为什么优于Hashtable？
HashTable容器使用synchronized来保证线程安全，但在线程竞争激烈的情况下HashTable的效率非常低下。因为当一个线程访问HashTable的同步方法时，其他线程访问HashTable的同步方法时，可能会进入阻塞或轮询状态。如线程1使用put进行添加元素，线程2不但不能使用put方法添加元素，并且也不能使用get方法来获取元素，所以竞争越激烈效率越低。
附加问题：
我们可以使用CocurrentHashMap来代替Hashtable吗？
我们知道Hashtable是synchronized的，但是ConcurrentHashMap同步性能更好，因为它仅仅根据同步级别对map的一部分进行上锁。ConcurrentHashMap当然可以代替HashTable，但是HashTable提供更强的线程安全性。它们都可以用于多线程的环境，但是当Hashtable的大小增加到一定的时候，性能会急剧下降，因为迭代时需要被锁定很长的时间。因为ConcurrentHashMap引入了分割(segmentation)，不论它变得多么大，仅仅需要锁定map的某个部分，而其它的线程不需要等到迭代完成才能访问map。简而言之，在迭代的过程中，ConcurrentHashMap仅仅锁定map的某个部分，而Hashtable则会锁定整个map。CocurrentHashMap在JAVA8中存在一个bug，会进入死循环，原因是递归创建ConcurrentHashMap 对象
6.如何决定使用HashMap还是 TreeMap？
7.说一下 HashMap 的实现原理？
如图所示，HashMap底层是基于数组和链表实现的。其中有两个重要的参数：
容量、负载因子
容量的默认大小是16，负载因子是 0.75，当 HashMap 的 size > 16*0.75时就会发生扩容(容量和负载因子都可以自由调整)。
Put方法：
首先会将传入的Key做 hash运算计算出 hashcode,然后根据数组长度取模计算出在数组中的 index 下标。
由于在计算中位运算比取模运算效率高的多，所以HashMap规定数组的长度为 2^n。这样用 2^n - 1做位运算与取模效果一致，并且效率还要高出许多。
由于数组的长度有限，所以难免会出现不同的Key通过运算得到的 index 相同，这种情况可以利用链表来解决，HashMap 会在 table[index]处形成链表，采用头插法将数据插入到链表中。
get方法：
get和 put 类似，也是将传入的 Key 计算出 index ，如果该位置上是一个链表就需要遍历整个链表，通过 key.equals(k)来找到对应的元素。
遍历方式：
Iterator<Map.Entry<String, Integer>> entryIterator = map.entrySet().iterator();
while (entryIterator.hasNext()) {
Map.Entry<String, Integer> next = entryIterator.next();
System.out.println("key=" + next.getKey() + " value=" + next.getValue());
}
Iterator<String> iterator = map.keySet().iterator();
while (iterator.hasNext()){
String key = iterator.next();
System.out.println("key=" + key + " value=" + map.get(key));
}
map.forEach((key,value)->{
System.out.println("key=" + key + " value=" + value);});
强烈建议使用第一种EntrySet进行遍历。
第一种可以把key value同时取出，第二种还得需要通过 key 取一次 value，效率较低, 第三种需要 JDK1.8以上，通过外层遍历 table，内层遍历链表或红黑树。
死循环问题：
在并发环境下使用HashMap容易出现死循环。
并发场景发生扩容，调用resize()方法里的 rehash()时，容易出现环形链表。这样当获取一个不存在的 key时，计算出的index正好是环形链表的下标时就会出现死循环。
所以HashMap只能在单线程中使用，并且尽量的预设容量，尽可能的减少扩容。
在JDK1.8中对 HashMap进行了优化： 当 hash碰撞之后写入链表的长度超过了阈值(默认为8)并且 table的长度不小于64(否则扩容一次)时，链表将会转换为红黑树。
假设hash冲突非常严重，一个数组后面接了很长的链表，此时重新的时间复杂度就是 O(n)。
如果是红黑树，时间复杂度就是O(logn)。
大大提高了查询效率。
多线程场景下推荐使用CocurrentHashMap。
8.说一下 HashSet 的实现原理？
HashSet是一个不允许存储重复元素的集合，它的实现比较简单，只要理解了 HashMap，HashSet就水到渠成了。
成员变量：
首先了解下HashSet的成员变量:
private transient HashMap<E,Object> map;
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
发现主要就两个变量:
map：用于存放最终数据的。
PRESENT：是所有写入 map 的 value值。
构造函数：
public HashSet() {
map = new HashMap<>();
}
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
构造函数很简单，利用了HashMap初始化了 map。
add:
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
比较关键的就是这个add()方法。 可以看出它是将存放的对象当做了 HashMap的健，value都是相同的 PRESENT。由于 HashMap的 key是不能重复的，所以每当有重复的值写入到 HashSet时，value会被覆盖，但 key不会受到影响，这样就保证了 HashSet中只能存放不重复的元素。
总结:
HashSet的原理比较简单，几乎全部借助于 HashMap来实现的。
所以HashMap会出现的问题 HashSet依然不能避免。
9.ArrayList 和 LinkedList 的区别是什么？
Arraylist：底层是基于动态数组，根据下表随机访问数组元素的效率高，向数组尾部添加元素的效率高；但是，删除数组中的数据以及向数组中间添加数据效率低，因为需要移动数组。例如最坏的情况是删除第一个数组元素，则需要将第2至第n个数组元素各向前移动一位。而之所以称为动态数组，是因为Arraylist在数组元素超过其容量大，Arraylist可以进行扩容（针对JDK1.8 数组扩容后的容量是扩容前的1.5倍），Arraylist源码中最大的数组容量是Integer.MAX_VALUE-8，对于空出的8位，目前解释是 ：①存储Headerwords；②避免一些机器内存溢出，减少出错几率，所以少分配③最大还是能支持到Integer.MAX_VALUE（当Integer.MAX_VALUE-8依旧无法满足需求时）.只要ArrayList的当前容足够大，add()操作向数组的尾部的效率非常高的，当向数组指定位置添加yi据时，会进行大量的数组移动复制操作。而数组复制时，最终将调用System.arraycopy()方法，因此add()操作的效率还是相当高的。尽管这样当向指定位置添加数据时也还是比Linkedlist慢，后者添加数据只需要改变指针指向即可。Arraylist删除数组也需要移动数组，效率较慢。
Linkedlist基于链表的动态数组，数据添加删除效率高，只需要改变指针指向即可，但是访问数据的平均效率低，需要对链表进行遍历。
总结：
1、对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针。 对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据。
2、各自效率问题：
10.如何实现数组和List之间的转换？
List转数组：
toArray(arraylist.size()方法
数组转List：
1.Arrays的asList(a)方法（效率不高）
2.通过集合工具类Collections.addAll()方法(最高效)通过Collections.addAll(arrayList, strArray)方式转换，根据数组的长度创建一个长度相同的List，然后通过Collections.addAll()方法，将数组中的元素转为二进制，然后添加到List中，这是最高效的方法。
11.ArrayList 和 Vector 的区别是什么？
ArrayList实现于 List、RandomAccess 接口。可以插入空数据，也支持随机访问。
ArrayList相当于动态数据，其中最重要的两个属性分别是: elementData 数组，以及 size 大小。 在调用 add() 方法的时候：
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
首先进行扩容校验。
将插入的值放到尾部，并将size + 1。
如果是调用add(index,e)在指定位置添加的话：
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
//复制，向后移动
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
也是首先扩容校验。
接着对数据进行复制，目的是把index位置空出来放本次插入的数据，并将后面的数据向后移动一个位置。
其实扩容最终调用的代码:
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
也是一个数组复制的过程。
由此可见ArrayList的主要消耗是数组扩容以及在指定位置添加数据，在日常使用时最好是指定大小，尽量减少扩容。更要减少在指定位置插入数据的操作。
序列化：
由于ArrayList是基于动态数组实现的，所以并不是所有的空间都被使用。因此使用了 transient 修饰，可以防止被自动序列化。
transient Object[] elementData;
因此ArrayList自定义了序列化与反序列化：
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();
// Write out size as capacity for behavioural compatibility with clone()
s.writeInt(size);
// Write out all elements in the proper order.
//只序列化了被使用的数据
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA;
// Read in size, and any hidden stuff
s.defaultReadObject();
// Read in capacity
s.readInt(); // ignored
if (size > 0) {
// be like clone(), allocate array based upon size not capacity
ensureCapacityInternal(size);
Object[] a = elementData;
// Read in all elements in the proper order.
for (int i=0; i<size; i++) {
a[i] = s.readObject();
}
}
}
当对象中自定义了writeObject和 readObject 方法时，JVM 会调用这两个自定义方法来实现序列化与反序列化。
从实现中可以看出ArrayList只序列化了被使用的数据。
Vector:
Vector也是实现于 List 接口，底层数据结构和 ArrayList 类似,也是一个动态数组存放数据。不过是在 add() 方法的时候使用 synchronized 进行同步写数据，但是开销较大，所以 Vector 是一个同步容器并不是一个并发容器。
以下是add()方法：
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}
以及指定位置插入数据:
public void add(int index, E element) {
insertElementAt(element, index);
}
public synchronized void insertElementAt(E obj, int index) {
modCount++;
if (index > elementCount) {
throw new ArrayIndexOutOfBoundsException(index
+ " > " + elementCount);
}
ensureCapacityHelper(elementCount + 1);
System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
elementData[index] = obj;
elementCount++;
}
12.Array 和 ArrayList 有何区别？
Array可以包含基本类型和对象类型，ArrayList只能包含对象类型
Array大小固定，ArrayList的大小是动态变化的。
ArrayList提供了更多的方法和特性：比如 ：addAll(),removeAll(),iterator()等等。
对于基本数据类型，集合使用自动装箱来减少编码工作量。但是，当处理固定大小基本数据类型的时候，这种方式相对较慢。
13.在Queue中poll()和remove()有什么区别？
poll()和 remove() 都是从队列中取出一个元素，但是 poll() 在获取元素失败的时候会返回空，但是 remove() 失败的时候会抛出异常。
14.哪些集合类是线程安全的？
Vector：就比ArrayList多了一个同步化机制（线程安全）
LinkedList因为成员方法大多是synchronized的，因此LinkedList是线程安全的。而ArrayList不是线程安全的。在扩容机制上，当Vector的元素数量超过它的初始化大小的时候会将容量翻倍，而ArrayList只会增长50%。
ArrayList的数据结构是基于数组的（Object[]）,而LinkList内部结构是基于一组链接的记录，形式上属于链表的。所以在增加元素方面linkList的效率更高，因为在ArrayList中增加元素，会牵扯一次重新排序。删除也是类似，所以ArrayList的查询性能要好些。反之LinkList增加，删除性能更好。如果是迭代读取的话，就没有什么差别了。
HashTable：比hashMap多了一个线程安全。hashTable的方法都提供了同步机制。hashTable不允许插入空值，hashMap是允许的。
ConcurrentHashMap：是一种高效但是也线程安全的集合。它比Hashmap来讲，是线程安全的，但是效率也比较高，因为它引入了一个分段锁的概念，可以理解为把一个大的Map拆分成了N个小的hashTable。根据key.hashCode（）决定把key放到哪个hashtable中。HashMap的数据结构是数据和链表。通过hash算法计算该key所在的数组下标，根据equals取比较值。通俗的说救赎ConcurrenthashMap是对每个数组进行加锁，当通过hash算法得出的结果相同时才需要去同步数据。
15.迭代器Iterator 是什么？
对Collection 进行迭代的类，称其为迭代器。还是面向对象的思想，专业对象做专业的事情，迭代器就是专门取出集合元素的对象。但是该对象比较特殊，不能直接创建对象（通过new），该对象是以内部类的形式存在于每个集合类的内部。
16.Iterator 怎么使用？有什么特点？
Collection接口中定义了获取集合类迭代器的方法（iterator（）），所以所有的Collection体系集合都可以获取自身的迭代器。
17.Iterator 和 ListIterator 有什么区别？
1. ListIterator有add()方法，可以向List中添加对象，而Iterator不能
2. ListIterator和Iterator都有hasNext()和next()方法，可以实现顺序向后遍历，但是ListIterator有hasPrevious()和previous()方法，可以实现逆向（顺序向前）遍历。Iterator就不可以。
3. ListIterator可以定位当前的索引位置，nextIndex()和previousIndex()可以实现。Iterator没有此功能。
4. 都可实现删除对象，但是ListIterator可以实现对象的修改，set()方法可以实现。Iierator仅能遍历，不能修改。
18.怎么确保一个集合不能被修改？
Collections.unmodifiableList(List)
Collections.unmodifiableMap(Map)
Collections.unmodifiableSet(Set)
可以返回一个只读视图不能修改
19.List、Map、Set三个接口，存取元素时，各有什么特点？
List 以特定次序来持有元素，可有重复元素。即，有序可重复。
访问时可以使用for循环，foreach循环，iterator迭代器 迭代。
Set 无法拥有重复元素,内部排序。即，无序不可重复。
访问时可以使用foreach循环，iterator迭代器 迭代。
Map 保存 key-value 值，一一映射。key值 是无序，不重复的。value值可重复。
访问时可以map中key值转为为set存储，然后迭代这个set，用map.get(key)获取value
20.对比Hashtable、HashMap、TreeMap有什么不同？
HashTable HashMap TreeMap都是最常见的一些Map实现,是以键值对的形式存储和操作数据的容器类型。
HashTable是早期Java类库提供的一个哈希表实现,本身是同步的,不支持null键和值,由于同步导致的性能开销,所以已经很少被推荐使用。
HashMap是应用更加广泛的哈希表实现,行为大致上与HashTable一致,主要区别在于HashMap不是同步的,支持null键和值等。通常情况下,HashMap进行put或者get操作,可以达到常数时间的性能,所以它是绝大部分利用键值对存储场景的首选,比如,实现一个用户ID和用户信息对应的运行时存储结构。
TreeMap则是基于红黑树的一种提供顺序访问的Map,和HashMap不同,它的get remove之类操作都是O(long(n)的时间复杂度,具体顺序可以由指定的Comparator来决定或者根据键的自然顺序来判断。
