java面试-java集合

说说你如何选用集合？

需要键值对选用 map 接口下的集合，需要排序用 TreeMap, 不需要排序用 HashMap
不需要键值对仅存放元素则选择 Collection 下实现的接口，保证元素唯一使用 Set, 不需要则选用 List

Collection 和 Collections 有什么区别？

• Collection 是集合类的上级接口，继承它的主要有 List 和 Set；
• Collections 是针对集合类的一个工具类，它提供了一些列的静态方法实现，如 Collections.sort() 排序、Collections.reverse() 逆序等。

Map 集合

HashMap,Hashtable,LinkedHashMap, TreeMap

HashMap:

• Hashmap 是一个最常用的 Map, 它根据键的 HashCode 值存储数据, 根据键可以直接获取它
  的值，具有很快的访问速度，遍历时，取得数据的顺序是完全随机的
• HashMap 最多只允许一条记录的键为 Null; 允许多条记录的值为 Null;
• HashMap 不支持线程的同步，即任一时刻可以 有多个线程同时写 HashMap; 可能会导致数据的不一致。如果需要同步，可以用Collections 的 synchronizedMap 方法使 HashMap 具有同步的能力，或者使用ConcurrentHashMap

Hashtable:
Hashtable 与 HashMap 类似, 它继承自 Dictionary 类，不同的是: 它不允许记录的键或者值为
空; 它支持线程的同步，即任一时刻只有一个线程能写 Hashtable, 因为 Hashtable 内部的方法基本
都经过 synchronized 修饰，因此也导致了 Hashtable 在写入时会比较慢。

LinkedHashMap:
LinkedHashMap 是 HashMap 的一个子类，额外持有一个双向链表，维保存了记录的插入顺
序，在用 Iterator 遍历 LinkedHashMap 时，先得到的记录肯定是先插入的. 也可以在构造时用带
参数，按照应用次数排序。在遍历的时候会比 HashMap 慢，不过有种情况例外，当 HashMap 容
量很大，实际数据较少时，遍历起来可能会比 LinkedHashMap 慢，因为 LinkedHashMap 的遍历
速度只和实际数据有关，和容量无关，而 HashMap 的遍历速度和他的容量有关。

TreeMap
TreeMap 实现 SortMap 接口，能够把它保存的记录根据键排序, 默认是按键值的升序排序，也
可以指定排序的比较器，当用 Iterator 遍历 TreeMap 时，得到的记录是排过序的。

HashMap 的链表转换红黑树的机制？

当链表长度大于阈值（默认为 8）会将链表转换成红黑树，以减少搜索时间，但是将链表转换成
红黑树前会判断如果当前数组小于 64 那么会先进行数组扩容而不是转换为红黑树。注：链表（寻
址时间复杂度为 O(N)）转换为红黑树（寻址时间复杂度为 O(log(N))）

ConcurrentHashMap 和 Hashtable 的区别？？

结构不同：JDK1.7 的 ConcurrentHashMap 底层采用分段的数组（Segment 大数组 +HashEntry
小数组）+ 链表实现，JDK1.8 采用的数据结构，Node 数组 + 链表/红黑二叉树。Hashtable 和
JDK1.8 之前的 HashMap 的底层数据结构类似都是采用数组 + 链表的形式

实现线程安全的方式不同：Hashtable 实现并发安全是通过 synchronized 关键字 ConcurrentHashMap 通过 cas,node,synchronized 相结合的方式实现 (更详细的说是 1.7 使用 segment 分段
锁，segment 实现了 ReentrantLock，在 1.8 取消了分段锁，采用 CAS 和 sychronized 来保证线程安全)

性能不同：Hashtbale 每一次修改都需要锁住整个对象，其他线程在此期间不能操作，所以线
程数量增加的时候性能会急剧下降而 ConcurrentHashMap 仅会对一部分上锁而不是全部都上锁，
因此在并发效率上，ConcurrentHashMap 比 Hashtable 提高了很多

List 集合

Vector 和 ArrayList 初始化大小和容量扩充有什么区别

Vector 和 ArrayList 的默认容量都为 10
Vector 容量扩充默认增加 1 倍
ArrayList 容量扩充默认增加大概 0.5 倍

比较 Arraylist 与 LinkedList ,Vector

底层数据结构：Arraylist 底层使用的是 Object 数组；LinkedList 底层使用的是双向链表
（JDK1.6 之前为循环链表，JDK1.7 取消了循环）,Vector 是 List 的古老实现类，底层用 Object[] 存储
线程安全：Vector 底层很多方法都加上了同步关键字 synchronized 保证线程安全，而
ArrayList 和 LinkedList 无法保证线程安全。
是否支持快速随机访问：Vector 和 ArrayList 的内部结构是以数组形式存储的，因此非常适
合随机访问，但非尾部的删除或新增性能较差，比如我们在中间插入一个元素，就需要把后续的
所有元素都进行移动。LinkedList 插入和删除元素效率比较高，但随机访问性能会比以上两个动
态数组慢。。

Set 集合

LinkedHashSet 如何保证有序和唯一性？

LinkedHashSet 底层数据结构由哈希表和链表组成，链表保证了元素的有序即存储和取出一致，哈
希表保证了元素的唯一性。

比较 HashSet、LinkedHashSet 和 TreeSet 三者的异同

• HashSet 是 Set 接口的实现类，底层是 HashMap, 是线程不安全的，可以存储 Null 值 (因为 HashSet 中只需要用到 key，而 HashMap 是 key-value 键值对，所以向 map 中添加键值对时，键 值对的值固定是PRESENT)
• LinkHashset 是 HashSet 的子类，LinkedHashSet 是 HashSet 的一个“扩展版本”，会维护“插
  入顺序”，而 HashSet 并不管什么顺序,LinkedHashSet 内部使用 LinkedHashMap 对象来存储和处 理它的元素
• TreeSet 是基于 TreeMap 实现的 TreeMap 是一个有序的二叉树，那么同理 TreeSet 同样也是 一个有序的