汇合

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

• List以 特定索引 来存取元素，能够 有反复 元素。
• Set 不能 寄存 反复 元素（用对象的 equals() 办法 来辨别 元素 是否反复）。
• Map 保留 键值对 （key-value pair）映射，映射关系能够是 一对一或多对一。
• Set 和 Map容器都有基于 哈希存储和排序树 的两种实现版本，基于 哈希存储的版本 实践存取 工夫复杂度为 O(1)，而 基于排序树版本的实现 在插入或删除元素时会 依照元素或元素的键（key）形成排序树 从而达到 排序和去重 的成果。

2.ArrayList、Vector、LinkedList 的存储性能和个性

ArrayList 和 Vector 都是应用数组形式存储数据，此数组 元素数大于理论存储的数据 以便减少和插入元素，它们都 容许间接按序号索引元素 ，然而插入元素要波及数组元素挪动等内存操作，所以 查问数据快而插入数据慢 ，Vector 中的办法因为增加了synchronized 润饰，因而 Vector 是线程平安 的容器，但性能上较 ArrayList 差，因而曾经是 Java 中的遗留容器。
LinkedList 应用 双向链表实现存储 （将内存中零散的内存单元通过附加的援用关联起来，造成一个能够按序号索引的线性构造，这种链式存储形式与数组的间断存储形式相比， 内存的利用率更高 ）， 按序号索引数据须要进行前向或后向遍历 ，然而插入数据时只须要记录本项的前后项即可，所以 插入速度较快 。Vector 属于遗留容器（Java 晚期的版本中提供的容器，除此之外，Hashtable、Dictionary、BitSet、Stack、Properties 都是遗留容器），曾经不举荐应用，然而因为ArrayList 和 LinkedListed 都是非线程平安的，如果遇到多个线程操作同一个容器的场景，则能够 通过工具类 Collections 中的 synchronizedList 办法将其转换成线程平安的容器后再应用（这是对装潢模式的利用，将已有对象传入另一个类的结构器中创立新的对象来加强实现）。

3.List、Set、Map 是否继承自 Collection 接口

List、Set 是，Map 不是。Map 是键值对映射容器，与 List 和 Set 有显著的区别，而 Set 存储的零散的元素且不容许有反复元素（数学中的汇合也是如此），List 是线性构造的容器，实用于按数值索引拜访元素的情景。

4.Collection 和 Collections 的区别

Collection 是汇合类的下级接口，继承与他的接口次要有 Set 和 List.
Collections 是针对汇合类的一个 帮忙类 ，他 提供一系列静态方法 实现对各种汇合的 搜寻、排序、线程平安化 等操作。

5.ArrayList 和 LinkedList

ArrayList 和 LinkedList 都实现了 List 接口，他们有以下的不同点：
ArrayList 是基于索引的数据接口，它的底层是数组。它能够以 O(1)工夫复杂度对元素进行随机拜访。与此对应，LinkedList 是以元素列表的模式存储它的数据，每一个元素都和它的前一个和后一个元素链接在一起，在这种状况下，查找某个元素的工夫复杂度是 O(n)。
绝对于 ArrayList，LinkedList 的插入，增加，删除操作速度更快，因为当元素被增加到汇合任意地位的时候，不须要像数组那样从新计算大小或者是更新索引。
LinkedList 比 ArrayList 更占内存，因为 LinkedList 为每一个节点存储了两个援用，一个指向前一个元素，一个指向下一个元素。

6.HashMap 和 Hashtable

HashMap 和 Hashtable 都实现了 Map 接口，因而很多个性十分类似。然而，他们有以下不同点：

• HashMap 容许键和值是 null，而 Hashtable 不容许键或者值是 null。
• Hashtable 是同步的，而 HashMap 不是。因而，HashMap 更适宜于单线程环境，而 Hashtable 适宜于多线程环境。
• HashMap 提供了可供给用迭代的键的汇合，因而，HashMap 是疾速失败的。另一方面，Hashtable 提供了对键的列举(Enumeration)。
• 个别认为 Hashtable 是一个遗留的类。

7. 疾速失败 (fail-fast) 和平安失败(fail-safe)

疾速失败（fail—fast）

在用迭代器遍历一个汇合对象时，如果遍历过程中对汇合对象的内容进行了批改（减少、删除、批改），则会抛出 Concurrent Modification Exception。
原理：迭代器在遍历时间接拜访汇合中的内容，并且在遍历过程中应用一个 modCount 变量。汇合在被遍历期间如果内容发生变化，就会扭转 modCount 的值。每当迭代器应用 hashNext()/next()遍历下一个元素之前，都会检测 modCount 变量是否为 expectedmodCount 值，是的话就返回遍历；否则抛出异样，终止遍历。

留神：这里异样的抛出条件是检测到 modCount！=expectedmodCount 这个条件。如果汇合发生变化时批改 modCount 值刚好又设置为了 expectedmodCount 值，则异样不会抛出。因而，不能依赖于这个异样是否抛出而进行并发操作的编程，这个异样只倡议用于检测并发批改的 bug。

场景：java.util 包下的汇合类都是疾速失败的，不能在多线程下产生并发批改（迭代过程中被批改）。

平安失败（fail—safe）

采纳平安失败机制的汇合容器，在遍历时不是间接在汇合内容上拜访的，而是 先复制原有汇合内容，在拷贝的汇合上进行遍历。

原理：因为迭代时是对原汇合的拷贝进行遍历，所以在遍历过程中 对原汇合所作的批改并不能被迭代器检测到，所以不会触发 Concurrent Modification Exception。

毛病：基于拷贝内容的长处是 防止了 Concurrent Modification Exception，但同样地，迭代器并不能拜访到批改后的内容，即：迭代器遍历的是开始遍历那一刻拿到的汇合拷贝，在遍历期间原汇合产生的批改迭代器是不晓得的。

场景：java.util.concurrent 包下的容器都是平安失败，能够在多线程下并发应用，并发批改。

Iterator 的平安失败是基于对底层汇合做拷贝，因而，它不受源汇合上批改的影响。java.util 包上面的所有的汇合类都是疾速失败的，而 java.util.concurrent 包上面的所有的类都是平安失败的。疾速失败的迭代器会抛出 ConcurrentModificationException 异样，而平安失败的迭代器永远不会抛出这样的异样。

8.Iterator 和 ListIterator 的区别

1. Iterator 可用来遍历 Set 和 List 汇合，然而ListIterator 只能用来遍历 List。
2. Iterator 对汇合只能是前向遍历，ListIterator 既能够前向也能够后向。
3. ListIterator 实现了 Iterator 接口，并蕴含其余的性能，比方：减少元素，替换元素，获取前一个和后一个元素的索引，等等。

9. 什么是迭代器

Iterator 提供了 对立遍历操作汇合元素的对立接口 , Collection 接口实现 Iterable 接口, 每个汇合都通过实现 Iterable 接口中 iterator() 办法返回 Iterator 接口的实例, 而后对汇合的元素进行迭代操作.
留神：在迭代元素的时候不能通过汇合的办法删除元素, 否则会抛出 ConcurrentModificationException 异样. 然而能够通过 Iterator 接口中的 remove()办法进行删除.

10. 为什么汇合类没有实现 Cloneable 和 Serializable 接口

克隆 (cloning) 或者是序列化 (serialization) 的语义和含意是 跟具体的实现相干的 。因而，应该由 汇合类的具体实现类来决定如何被克隆或者是序列化 。
实现 Serializable 序列化的作用：将 对象的状态保留在存储媒体中 以便能够在 当前重写创立出完全相同的正本 ；按 值将对象从一个从一个应用程序域发向另一个应用程序域 。
实现 Serializable 接口的作用就是能够把 对象存到字节流，而后能够复原。所以你想如果你的对象没有序列化，怎么能力进行网络传输呢？要网络传输就得转为字节流，所以在分布式应用中，你就得实现序列化。如果你不须要分布式应用，那就没必要实现实现序列化。

11.ConcurrentHashMap

ConcurrentHashMap 是 HashMap 的一个线程平安的、反对高效并发的版本。在默认现实状态下，ConcurrentHashMap 能够反对 16 个线程执行并发写操作及任意数量线程的读操作。
ConcurrentHashMap 类中蕴含两个动态外部类 HashEntry 和 Segment。HashEntry 用来 封装映射表的键 / 值对 ；Segment 用来充当锁 的角色，每个 Segment 对象守护整个散列映射表的若干个桶。每个桶是由若干个 HashEntry 对象链接起来的链表。一个 ConcurrentHashMap 实例中蕴含由若干个 Segment 对象组成的数组。HashEntry 用来封装散列映射表中的键值对。在 HashEntry 类中，key，hash 和 next 域都被申明为 final 型，value 域被申明为 volatile 型。

static final class HashEntry<K,V> {
       final K key;                       // 申明 key 为 final 型
       final int hash;                   // 申明 hash 值为 final 型
       volatile V value;                 // 申明 value 为 volatile 型
       final HashEntry<K,V> next;      // 申明 next 为 final 型
 
       HashEntry(K key, int hash, HashEntry<K,V> next, V value) {
           this.key = key;
           this.hash = hash;
           this.next = next;
           this.value = value;
       }
}

在 ConcurrentHashMap 中，在散列时如果产生“碰撞”，将采纳“拆散链接法”来解决“碰撞”：把“碰撞”的 HashEntry 对象链接成一个链表。因为 HashEntry 的 next 域为 final 型，所以新节点只能在链表的表头处插入。下图是在一个空桶中顺次插入 A，B，C 三个 HashEntry 对象后的结构图：

图 1. 插入三个节点后桶的构造示意图：
在 ConcurrentHashMap 中，在散列时如果产生“碰撞”，将采纳“拆散链接法”来解决“碰撞”：把“碰撞”的 HashEntry 对象链接成一个链表。因为 HashEntry 的 next 域为 final 型，所以新节点只能在链表的表头处插入。下图是在一个空桶中顺次插入 A，B，C 三个 HashEntry 对象后的结构图：

留神：因为只能在表头插入，所以链表中节点的程序和插入的程序相同。
Segment 类继承于 ReentrantLock 类，从而使得 Segment 对象能充当锁的角色。每个 Segment 对象用来守护其（成员对象 table 中）蕴含的若干个桶。

concurrenthashmap 有什么劣势以及 1.7 和 1.8 区别
Concurrenthashmap 线程平安 的，1.7 是在 jdk1.7 中采纳 Segment + HashEntry 的形式进行实现的，lock 加在 Segment 下面。1.7size 计算是先采纳不加锁的形式，间断计算元素的个数，最多计算 3 次：1、如果前后两次计算结果雷同，则阐明计算出来的元素个数是精确的；2、如果前后两次计算结果都不同，则给每个 Segment 进行加锁，再计算一次元素的个数；

1.8 中放弃了 Segment 臃肿的设计，取而代之的是采纳 Node + CAS + Synchronized来保障并发平安进行实现，1.8 中应用一个 volatile 类型的变量 baseCount 记录元素的个数，当插入新数据或则删除数据时，会通过 addCount()办法更新 baseCount，通过累加 baseCount 和 CounterCell 数组中的数量，即可失去元素的总个数；

12.TreeMap

TreeMap 是一个 有序的 key-value 汇合 ， 基于红黑树 （Red-Black tree）的 NavigableMap 实现。该映射依据其 键的天然程序进行排序 ， 或者 依据创立映射时提供的 Comparator 进行排序 ，具体 取决于应用的构造方法。
TreeMap 的个性：

• 根节点是彩色
• 每个节点都只能是红色或者彩色
• 每个叶节点（NIL 节点，空节点）是彩色的。
• 如果一个节点是红色的，则它两个子节点都是彩色的，也就是说在一条门路上不能呈现两个红色的节点。
• 从任一节点到其每个叶子的所有门路都蕴含雷同数目的彩色节点。

13.ArrayList 是否会越界

1. ArrayList 是实现了 基于动静数组 的数据结构，而 LinkedList 是基于链表的数据结构
2. 对于随机拜访 get 和 set，ArrayList 要优于 LinkedList，因为 LinkedList 要挪动指针；
3. ArrayList 并发 add()可能呈现数组下标越界异样。

14.HashMap 的容量为什么是 2^n

负载因子默认是 0.75，2^n 是为了让散列更加平均，例如呈现极其状况都散列在数组中的一个下标，那么 hashmap 会由 O（1）简单进化为 O（n）的。

如果 hashMap 的 key 是一个自定义的类, 就必须重写 hashcode()和 equals()