汇合

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()