Java 容器模块

Java 容器都有哪些？

Java 容器分为 Collection 和 Map 两大类，其下又有很多子类：Collection、List、ArrayList、LinkedList、Vector、Stack、Set、HashSet、LinkedHashSet、TreeSet、Map、HashMap、LinkedHashMap、TreeMap、ConcurrentHashMap、Hashtable。

Collection 和 Collections 的区别

Collection 是一个集合接口，它提供了对集合对象进行基本操作的通用接口方法，所有集合都是它的子类，比如 List、Set 等。
Collections 是一个包装类，包含了很多静态方法，不能被实例化，就像一个工具类，比如提供的排序方法：Collections. sort(list)。

List、Set、Map 之间的区别

List、Set、Map 的区别主要体现在两个方面：元素是否有序、是否允许元素重复。

HashMap 和 Hashtable 的区别

1. HashMap是继承自AbstractMap类，而HashTable是继承自Dictionary类。不过它们都实现了同时实现了map、Cloneable（可复制）、Serializable（可序列化）这三个接口。
   
2. Hashtable比HashMap多提供了elments() 和contains() 两个方法。
3. HashMap的key-value支持key-value，null-null，key-null，null-value四种。而Hashtable只支持key-value一种（即key和value都不为null这种形式）。既然HashMap支持带有null的形式，那么在HashMap中不能由get()方法来判断HashMap中是否存在某个键， 而应该用containsKey()方法来判断，因为使用get的时候，当返回null时，你无法判断到底是不存在这个key，还是这个key就是null，还是key存在但value是null。
4. 线程安全性不同：
   1. HashMap的方法都没有使用synchronized关键字修饰，都是非线程安全的，而Hashtable的方法几乎都是被synchronized关键字修饰的。但是，当我们需要HashMap是线程安全的时，怎么办呢？我们可以通过Collections.synchronizedMap(hashMap)来进行处理，亦或者我们使用线程安全的ConcurrentHashMap。
   2. ConcurrentHashMap虽然也是线程安全的，但是它的效率比Hashtable要高好多倍。因为ConcurrentHashMap使用了分段锁，并不对整个数据进行锁定。
5. 初始容量大小和每次扩充容量大小的不同：
   1. Hashtable默认的初始大小为11，之后每次扩充，容量变为原来的2n+1。
   2. HashMap默认的初始化大小为16。之后每次扩充，容量变为原来的2倍。
6. 计算hash值的方法不同：
   1. 为了得到元素的位置，首先需要根据元素的 KEY计算出一个hash值，然后再用这个hash值来计算得到最终的位置。
   2. Hashtable直接使用对象的hashCode。
   3. hashCode是JDK根据对象的地址或者字符串或者数字算出来的int类型的数值。然后再使用除留余数发来获得最终的位置。

如何决定使用 HashMap 还是 TreeMap？

对于在 Map 中插入、删除、定位一个元素这类操作，HashMap 是最好的选择，因为相对而言 HashMap 的插入会更快，但如果你要对一个 key 集合进行有序的遍历，那 TreeMap 是更好的选择。

TreeMap 与 TreeSet

TreeSet使用的Map集合（SortedMap接口子类），里面存放的是TreeMap，TreeMap的特点在于所有的 key 都是可以排序的，而排序的依据可以发现是Comparable（往往会忽略掉Comparator）。
在TreeMap之中对于大小的关系判断强制使用了Comparable接口的compareTo()完成。

正因为TreeSet的使用必须依靠Comaprable，并且在实际开发之中即使使用了集合保存有所有的查询结果，但是也很少会出现重复的判断，因为数据表的主键不会重复。所以也就证明这个时候是否进行重复元素的判断是没有任何意义的，再如在实现二叉树的时候也需要考虑对象的比较问题。
所以在开发里面最为常用的一个子类：HashSet，只需要判断重复，而且大部分使用的情况都只是String、Integer类，很少会保存一个对象。

HashMap 的实现原理

HashMap 基于 Hash 算法实现的，我们通过 put(key,value)存储，get(key)来获取。当传入 key 时，HashMap 会根据 key.hashCode() 计算出 hash 值，根据 hash 值将 value 保存在 bucket 里。当计算出的 hash 值相同时，我们称之为 hash 冲突，HashMap 的做法是用链表和红黑树存储相同 hash 值的 value。当 hash 冲突的个数比较少时，使用链表否则使用红黑树。

HashMap put方法

① ：判断哈希桶数组 table 是否为空，为空则通过 resize() 进行扩容初始化。
② ：根据 key 的 hash 值，计算 key 在 table 中的索引位置 i，如果 table[i] == null， 直接新建节点，跳转到步骤 ⑥， 如果 table[i] != null，进入步骤 ③。
③ ： 判断 key 是否与 table[i] 相等，相等则覆盖，跳转到步骤⑥。不相等，进入步骤④。
④ ：判断 table[i] 是否为 treeNode，即判断哈希桶中的数据结构是否为红黑树，如果是直接在树中插入节点，否则进入步骤⑤。
⑤ ：哈希桶中的数据结构为链表的情况，循环遍历 table，将节点加入到链表的结尾，并计算链表的长度，如果链表的长度大于8，则将链表转化为红黑树。遍历的过程如果发现 key 已经存在，则直接覆盖。
⑥ ：插入成功，判断 size 是否 大于阈值 threshold，大于则进行扩容 resize。

hash冲突

在整个Hash存储过程之中，必须明确两个实际问题，hashCode() 与 equals() 两个方法。如果 hashCode 相同，这个时候会查询 equals，不过一般使用 Map 的时候都会考虑 String 实现，所以在 String 实现的 Key 里面不要存在复杂的概念，也就是说这种概念之存在自定义类里面，所以 hash 冲突严重的时候，首先先去考虑 equals 方法是否相等，那么在进行数据定位的时候会更加的快速。
HashMap 中 Hash 冲突严重时会影响 HashMap 性能。

hash冲突的处理

实际使用的数据结构的算法来讲，如果真的有hash冲突那么就需要使用一些特定的处理方法：

1. 开放定址法，为一个hash冲突的一个地址序列
2. 链地址法，将所有hash冲突的内容保存在一个链表里面（HashMap的实现原理）
3. 再hash法，重新做一个hsah计算

HashSet 的实现原理

HashSet 是基于 HashMap 实现的，HashSet 底层使用 HashMap 来保存所有元素，但是只使用了key（HashMap的主要特点：key不能重复）所以HashSet 不允许重复的值。

相关 HashSet 的操作，基本上都是直接调用底层 HashMap 的相关方法来完成

1. add() 方法利用put()实现
2. 整个存储中存在一个hashCode的使用
3. 在内部的Node类处理时依然使用equals()判断key内容

ArrayList 和 LinkedList 的区别

1. 数据结构实现：
   1. ArrayList 是动态数组的数据结构实现，
   2. LinkedList 是双向链表的数据结构实现。
2. 随机访问效率：
   1. ArrayList 比 LinkedList 在随机访问的时候效率要高，因为 LinkedList 是线性的数据存储方式，所以需要移动指针从前往后依次查找。
3. 增加和删除效率：
   1. 在非首尾的增加和删除操作，LinkedList 要比 ArrayList 效率要高，因为 ArrayList 增删操作要影响数组内的其他数据的下标。

综合来说，在需要频繁读取集合中的元素时，更推荐使用 ArrayList，而在插入和删除操作较多时，更推荐使用 LinkedList。

数组和 List 之间的转换

数组转 List：使用 Arrays. asList(array) 进行转换。
List 转数组：使用 List 自带的 toArray() 方法。

ArrayList 和 Vector 的区别

ArrayList 和 Vector 都会根据实际的需要动态的调整容量。

数组 Array 和 ArrayList 的区别

在 Queue 中 poll()和 remove()的区别

相同点：都是返回第一个元素，并在队列中删除返回的对象。
不同点：如果没有元素 remove()会直接抛出NoSuchElementException 异常，而 poll()会返回 null。

Queue<String> queue = new LinkedList<String>();
 // add
queue. offer("string");
System. out. println(queue. poll());
System. out. println(queue. remove());
System. out. println(queue. size());

线程安全的集合类

Vector、Hashtable、Stack 都是线程安全的，而像 HashMap 则是非线程安全的，不过在 JDK 1.5 之后随着 Java. util. concurrent 并发包的出现，它们也有了自己对应的线程安全类，比如 HashMap 对应的线程安全类就是 ConcurrentHashMap。

迭代器 Iterator

Iterator 接口提供遍历任何 Collection 的接口。我们可以从一个 Collection 中使用迭代器方法来获取迭代器实例。迭代器取代了 Java 集合框架中的 Enumeration，迭代器允许调用者在迭代过程中移除元素。

Iterator 的使用

Iterator 的特点是更加安全，因为它可以确保，在当前遍历的集合元素被更改的时候，就会抛出 ConcurrentModificationException 异常。

List<String> list = new ArrayList<>();
Iterator<String> it = list. iterator();
while(it. hasNext()){
    String obj = it. next();
    System. out. println(obj);
}

Iterator 和 ListIterator 的区别

ListIterator 从 Iterator 接口继承，然后添加了一些额外的功能，比如添加一个元素、替换一个元素、获取前面或后面元素的索引位置。

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

可以使用 Collections. unmodifiableCollection(Collection c) 方法来创建一个只读集合，这样改变集合的任何操作都会抛出 Java. lang. UnsupportedOperationException 异常。

List<String> list = new ArrayList<>();
list. add("x");
Collection<String> clist = Collections. unmodifiableCollection(list);
 // 运行时此行报错
clist. add("y");