ArrayList实现原理要点概括

参考文献：
http://zhangshixi.iteye.com/blog/674856l
https://www.cnblogs.com/leesf456/p/5308358.html

1. ArrayList是List接口的可变数组非同步实现，并允许包括null在内的所有元素。
2. 底层使用数组实现
3. 该集合是可变长度数组，数组扩容时，会将老数组中的元素重新拷贝一份到新的数组中，每次数组容量增长大约是其容量的1.5倍，这种操作的代价很高。
4. 采用了Fail-Fast机制，面对并发的修改时，迭代器很快就会完全失败，而不是冒着在将来某个不确定时间发生任意不确定行为的风险
5. remove方法会让下标到数组末尾的元素向前移动一个单位，并把最后一位的值置空，方便GC

LinkedList实现原理要点概括

参考文献：
1.http://www.cnblogs.com/ITtangtang/p/3948610.htmll
2.https://www.cnblogs.com/leesf456/p/5308843.html

1. LinkedList是List接口的双向链表非同步实现，并允许包括null在内的所有元素。
2. 底层的数据结构是基于双向链表的，该数据结构我们称为节点
3. 双向链表节点对应的类Node的实例，Node中包含成员变量：prev，next，item。其中，prev是该节点的上一个节点，next是该节点的下一个节点，item是该节点所包含的值。
4. 它的查找是分两半查找，先判断index是在链表的哪一半，然后再去对应区域查找，这样最多只要遍历链表的一半节点即可找到

HashMap实现原理要点概括

参考文献：http://zhangshixi.iteye.com/blog/672697
参考文献：http://blog.csdn.net/lizhongkaide/article/details/50595719

1. HashMap是基于哈希表的Map接口的非同步实现，允许使用null值和null键，但不保证映射的顺序。
2. 底层使用数组实现，数组中每一项是个单向链表，即数组和链表的结合体；当链表长度大于一定阈值时，链表转换为红黑树，这样减少链表查询时间。
3. HashMap在底层将key-value当成一个整体进行处理，这个整体就是一个Node对象。HashMap底层采用一个Node[]数组来保存所有的key-value对，当需要存储一个Node对象时，会根据key的hash算法来决定其在数组中的存储位置，在根据equals方法决定其在该数组位置上的链表中的存储位置；当需要取出一个Node时，也会根据key的hash算法找到其在数组中的存储位置，再根据equals方法从该位置上的链表中取出该Node。
4. HashMap进行数组扩容需要重新计算扩容后每个元素在数组中的位置，很耗性能
5. 采用了Fail-Fast机制，通过一个modCount值记录修改次数，对HashMap内容的修改都将增加这个值。迭代器初始化过程中会将这个值赋给迭代器的expectedModCount，在迭代过程中，判断modCount跟expectedModCount是否相等，如果不相等就表示已经有其他线程修改了Map，马上抛出异常

Hashtable实现原理要点概括

参考文献：http://blog.csdn.net/zheng0518/article/details/42199477

1. Hashtable是基于哈希表的Map接口的同步实现，不允许使用null值和null键
2. ** 底层使用数组实现，数组中每一项是个单链表，即数组和链表的结合体**
3. Hashtable在底层将key-value当成一个整体进行处理，这个整体就是一个Entry对象。Hashtable底层采用一个Entry[]数组来保存所有的key-value对，当需要存储一个Entry对象时，会根据key的hash算法来决定其在数组中的存储位置，在根据equals方法决定其在该数组位置上的链表中的存储位置；当需要取出一个Entry时，也会根据key的hash算法找到其在数组中的存储位置，再根据equals方法从该位置上的链表中取出该Entry。
4. synchronized是针对整张Hash表的，即每次锁住整张表让线程独占

ConcurrentHashMap实现原理要点概括

参考文献：http://blog.csdn.net/zheng0518/article/details/42199477

1. ConcurrentHashMap允许多个修改操作并发进行，其关键在于使用了锁分离技术。
2. 它使用了多个锁来控制对hash表的不同段进行的修改，每个段其实就是一个小的hashtable，它们有自己的锁。只要多个并发发生在不同的段上，它们就可以并发进行。
3. ConcurrentHashMap在底层将key-value当成一个整体进行处理，这个整体就是一个Entry对象。Hashtable底层采用一个Entry[]数组来保存所有的key-value对，当需要存储一个Entry对象时，会根据key的hash算法来决定其在数组中的存储位置，在根据equals方法决定其在该数组位置上的链表中的存储位置；当需要取出一个Entry时，也会根据key的hash算法找到其在数组中的存储位置，再根据equals方法从该位置上的链表中取出该Entry。
4. 与HashMap不同的是，ConcurrentHashMap使用多个子Hash表，也就是段(Segment)
5. ConcurrentHashMap完全允许多个读操作并发进行，读操作并不需要加锁。如果使用传统的技术，如HashMap中的实现，如果允许可以在hash链的中间添加或删除元素，读操作不加锁将得到不一致的数据。ConcurrentHashMap实现技术是保证HashEntry几乎是不可变的。

HashSet实现原理要点概括

参考文献：http://zhangshixi.iteye.com/blog/673143l

1. HashSet由哈希表(实际上是一个HashMap实例)支持，不保证set的迭代顺序，并允许使用null元素。
2. 基于HashMap实现，API也是对HashMap的行为进行了封装，可参考HashMap

LinkedHashMap实现原理要点概括

参考文献：http://zhangshixi.iteye.com/blog/673789l

1. LinkedHashMap继承于HashMap，底层使用哈希表和双向链表来保存所有元素，并且它是非同步，允许使用null值和null键。
2. 基本操作与父类HashMap相似，通过重写HashMap相关方法，重新定义了数组中保存的元素Entry，来实现自己的链接列表特性。该Entry除了保存当前对象的引用外，还保存了其上一个元素before和下一个元素after的引用，从而构成了双向链接列表。

LinkedHashSet实现原理要点概括

参考文献：http://zhangshixi.iteye.com/blog/673319l

1. 对于LinkedHashSet而言，它继承与HashSet、又基于LinkedHashMap来实现的。LinkedHashSet底层使用LinkedHashMap来保存所有元素，它继承与HashSet，其所有的方法操作上又与HashSet相同。

什么是Java集合API

Java集合框架API是用来表示和操作集合的统一框架，它包含接口、实现类、以及帮助程序员完成一些编程的算法。简言之，API在上层完成以下几件事：

● 编程更加省力，提高城程序速度和代码质量
● 非关联的API提高互操作性
● 节省学习使用新API成本
● 节省设计新API的时间
● 鼓励、促进软件重用

具体来说，有6个集合接口，最基本的是Collection接口，由三个接口Set、List、SortedSet继承，另外两个接口是Map、SortedMap,这两个接口不继承Collection，表示映射而不是真正的集合。

Collection接口：存储一组不唯一，无序的对象
　　 List接口：存储一组不唯一，有序的对象
　　 Set接口：存储一组唯一，无序的对象
　　 Map接口：存储一组键值对象，提高键（key）到值(value)的映射

为何Map接口不继承Collection接口？

虽然Map接口和它的实现也是集合框架的一部分。但Map不是集合。集合也不是Map。
因此，Map继承Collection毫无意义，反之亦然。
假设Map继承Collection接口，那么元素去哪儿？Map包括key-value对，它提供抽取key或value列表集合的方法，可是它不适合“一组对象”规范

2.HashMap和Hashtable之间的区别？

在JDK1.6，JDK1.7中，HashMap采用位桶+链表实现，即使用链表处理冲突，同一hash值的链表都存储在一个链表里。但是当位于一个桶中的元素较多，即hash值相等的元素较多时，通过key值依次查找的效率较低。而JDK1.8中，HashMap采用位桶+链表+红黑树实现，当链表长度超过阈值（8）时，将链表转换为红黑树，这样大大减少了查找时间。

1.两者最主要的区别在于Hashtable是线程安全，而HashMap则非线程安全

Hashtable的实现方法里面都添加了synchronized关键字来确保线程同步，因此相对而言HashMap性能会高一些，我们平时使用时若无特殊需求建议使用HashMap，在多线程环境下若使用HashMap需要使用Collections.synchronizedMap()方法来获取一个线程安全的集合。

2.HashMap可以使用null作为key，而Hashtable则不允许null作为key
虽说HashMap支持null值作为key，不过建议还是尽量避免这样使用，因为一旦不小心使用了，若因此引发一些问题，排查起来很是费事

3.HashMap是对Map接口的实现，HashTable实现了Map接口和Dictionary抽象类
HashMap的初始容量为16，Hashtable初始容量为11，两者的填充因子默认都是0.75

4.HashMap扩容时是当前容量翻倍即:capacity2，Hashtable扩容时是容量翻倍+1即:capacity2+1

5.两者计算hash的方法不同
Hashtable计算hash是直接使用key的hashcode对table数组的长度直接进行取模

Iterator、ListIterator 和 Enumeration的区别？

Enumeration接口在Java1.2版本开始有，所以Enumeration是合法规范的接口
Enumeration使用elements()方法
Iterator对所有Java集合类都有实现
Iterator使用iterator方法
Iterator只能往一个方向前进
ListIterator仅仅对List类型的类实现了
ListIterator使用listIterator（）方法

fail-fast 与 fail-safe 之间的区别？

Fail fast快速地报告任何的failure。无论何时任何一个问题都会引发 fail fast系统fails
在Java Fail fast 迭代器中，迭代objects集合有时会出现并发修改异常，出现这种情况有2个原因
如果一个线程正在迭代一个集合，而另一个线程同时试图修改这个集合
在调用remove()方法后，如何我们还试图去修改集合object

Java 中 Set 与 List 有什么不同?

Set是一个不允许重复元素存在的集合
Set没有索引
Set仅仅允许一个null值
Set有类：HashSet、LinkedHashMap、TreeSet
List有索引
List允许N个null值
List可以按插入顺序显示
List有类：Vector、ArrayList、LinkedList

arraylist 与 vector 的区别?

Vector 在Java的第一个版本就引入了，也就是说vector是一个合法规范的类
ArrayList在Java1.2版本引入的，是Java 集合框架的组成部分
Vector是同步的
ArrayList是不同步的

什么类实现了List接口？

ArrayList
LinkedList
Vector

什么类实现了Set接口？

HashSet
LinkedHashSet
TreeSet

如何保证一个集合线程安全？

Vector, Hashtable, Properties 和 Stack 都是同步的类，所以它们都线程安全的，可以被使用在多线程环境中
使用Collections.synchronizedList(list)) 方法，可以保证list类是线程安全的
使用java.util.Collections.synchronizedSet()方法可以保证set类是线程安全的

是否可以往 TreeSet 或者 HashSet 中添加 null

可以往 hashset 中添加一个 null
TreeSet 也允许一个 null值

Iterator符合哪个设计模式？

Iterator 设计模式

如何对Object的list排序？

对objects数组进行排序，我们可以用Arrays.sort()方法
如果要对objects的集合进行排序，需要使用Collections.sort()方法

HashSet 实现了哪个数据结构？

HashSet 内部实现了hashmap

为什么 Collection 不能继承 Cloneable 和 Serializable？

Collection接口指定一组对象，对象即为它的元素。怎样维护这些元素由Collection的详细实现决定。
比如。一些如List的Collection实现同意反复的元素。而其他的如Set就不同意。非常多Collection实现有一个公有的clone方法。
然而。把它放到集合的全部实现中也是没有意义的。这是由于Collection是一个抽象表现。重要的是实现。
当与详细实现打交道的时候，克隆或序列化的语义和含义才发挥作用。所以，详细实现应该决定怎样对它进行克隆或序列化，或它能否够被克隆或序列化。
在全部的实现中授权克隆和序列化，终于导致更少的灵活性和很多其他的限制。特定的实现应该决定它能否够被克隆和序列化。

hashCode() 和 equals() 方法的重要性？如何在Java中使用它们？

hashCode() 和 equals() 方法定义在”object”类中
如果equals() 方法在比较2个对象时返回true，那么hashCode()的返回值必须得一样

什么是 Properties 类？

Properties 是Hashtable的子类。它被用于维护值的list，其中它们的键、值都是String类型

如何将一个字符串转换为arraylist?

使用 arrayList.toArray() 方法

Java 集合类框架的基本接口有哪些？

Java 集合类提供了一套设计良好的支持对一组对象进行操作的接口和类。Java 集合类里面最基本的接口有：
Collection：代表一组对象，每一个对象都是它的子元素。
Set：不包含重复元素的 Collection。
List：有顺序的 collection，并且可以包含重复元素。
Map：可以把键(key)映射到值(value)的对象，键不能重复。

为什么集合类没有实现 Cloneable 和 Serializable 接口？

集合类接口指定了一组叫做元素的对象。集合类接口的每一种具体的实现类都可以选择以它自己的方式对元素进行保存和排序。有的集合类允许重复的键，有些不允许。

什么是迭代器(Iterator)？

Iterator 接口提供了很多对集合元素进行迭代的方法。每一个集合类都包含了可以返回迭代器实例的 迭代方法。迭代器可以在迭代的过程中删除底层集合的元素。
克隆(cloning)或者是序列化(serialization)的语义和含义是跟具体的实现相关的。因此，应该由集合类的具体实现来决定如何被克隆或者是序列化。

Iterator 和 ListIterator 的区别是什么？

下面列出了他们的区别：
Iterator 可用来遍历 Set 和 List 集合，但是 ListIterator 只能用来遍历 List。
Iterator 对集合只能是前向遍历，ListIterator 既可以前向也可以后向。
ListIterator 实现了 Iterator 接口，并包含其他的功能，比如：增加元素，替换元素，获取前一个和后一个元素的索引，等等。

快速失败(fail-fast)和安全失败(fail-safe)的区别是什么？

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

Java 中的 HashMap 的工作原理是什么？

Java 中的 HashMap 是以键值对(key-value)的形式存储元素的。HashMap 需要一个 hash 函数，它使用 hashCode()和 equals()方法来向集合/从集合添加和检索元素。当调用 put()方法的时候，HashMap 会计算 key 的 hash 值，然后把键值对存储在集合中合适的索引上。如果 key已经存在了，value 会被更新成新值。HashMap 的一些重要的特性是它的容量(capacity)，负载因子(load factor)和扩容极限(threshold resizing)。

hashCode()和 equals()方法的重要性体现在什么地方？

Java 中的 HashMap 使用 hashCode()和 equals()方法来确定键值对的索引，当根据键获取值
以这两个方法的实现对 HashMap 的精确性和正确性是至关重要的

HashMap 和 Hashtable 有什么区别？

HashMap 和 Hashtable 都实现了 Map 接口，因此很多特性非常相似。但是，他们有以下不同点：
HashMap 允许键和值是 null，而 Hashtable 不允许键或者值是 null。
Hashtable 是同步的，而 HashMap 不是。因此，HashMap 更适合于单线程环境，而 Hashtable适合于多线程环境。
HashMap 提供了可供应用迭代的键的集合，因此，HashMap 是快速失败的。另一方面，Hashtable 提供了对键的列举(Enumeration)。
一般认为 Hashtable 是一个遗留的类。

数组(Array)和列表(ArrayList)有什么区别？什么时候应该使用 Array 而不是ArrayList ？

下面列出了 Array 和 ArrayList 的不同点：
Array 可以包含基本类型和对象类型，ArrayList 只能包含对象类型。
Array 大小是固定的，ArrayList 的大小是动态变化的。
ArrayList 提供了更多的方法和特性，比如：addAll()，removeAll()，iterator()等等。
对于基本类型数据，集合使用自动装箱来减少编码工作量。但是，当处理固定大小的基本数据类型的时候，这种方式相对比较慢。

ArrayList 和 LinkedList 有什么区别？

ArrayList 和 LinkedList 都实现了 List 接口，他们有以下的不同点：
ArrayList 基于索引的数据接口，它的底层是数组。它可以以 O(1)时间复杂度对元素进行随机访问。与此对应，LinkedList是以元素列表的形式存储它的数据，每一个元素都和它的前 一个和后一个元素链接在一起，在这种情况下，查找某个元素的时间复杂度是 O(n)。
相对于 ArrayList ，LinkedList 的插入，添加，删除操作速度更快，因为当元素被添加到集合任 意位置的时候，不需要像数组那样重新计算大小或者是更新索引。
LinkedList 比 ArrayList 更占内存，因为 LinkedList 为每一个节点存储了两个引用，一个指向前一个元素，一个指向下一个元素。也可以参考 ArrayList vs. LinkedList 。

Comparable 和 Comparator 接口是干什么的？列出它们的区别。

参考链接: https://www.cnblogs.com/Kevin-mao/p/5912775.html

Java 提供了只包含一个 compareTo()方法的 Comparable 接口。这个方法可以个给两个对象排序。具体来说，它返回负数，0，正数来表明输入对象小于，等于，大于已经存在的对象。
Java 提供了包含 compare()和 equals()两个方法的 Comparator 接口。compare()方法用来给两个输入参数排序，返回负数，0，正数表明第一个参数是小于，等于，大于第二个参数。equals()方法需要一个对象作为参数，它用来决定输入参数是否和 comparator 相等。只有当输入参数也是一个 comparator 并且输入参数和当前 comparator 的排序结果是相同的时候，这个方法才返回 true 。

怎样使Hashmap同步？

HashMap可以通过Map m = Collections.synchronizedMap（hashMap）来达到同步的效果。

什么时候使用Hashtable，什么时候使用HashMap

基本的不同点是Hashtable同步HashMap不是的，所以无论什么时候有多个线程访问相同实例的可能时，就应该使用Hashtable，反之使用HashMap。非线程安全的数据结构能带来更好的性能。

如果在将来有一种可能—你需要按顺序获得键值对的方案时，HashMap是一个很好的选择，因为有HashMap的一个子类LinkedHashMap。所以如果你想可预测的按顺序迭代(默认按插入的顺序)，你可以很方便用LinkedHashMap替换HashMap。反观要是使用的Hashtable就没那么简单了。同时如果有多个线程访问HashMap，Collections.synchronizedMap()可以代替，总的来说HashMap更灵活。

为什么Vector类认为是废弃的或者是非官方地不推荐使用？或者说为什么我们应该一直使用ArrayList而不是Vector

你应该使用ArrayList而不是Vector是因为默认情况下你是非同步访问的，Vector同步了每个方法，你几乎从不要那样做，通常有想要同步的是整个操作序列。同步单个的操作也不安全(如果你迭代一个Vector,你还是要加锁，以避免其它线程在同一时刻改变集合).而且效率更慢。当然同样有锁的开销即使你不需要，这是个很糟糕的方法在默认情况下同步访问。你可以一直使用Collections.sychronizedList来装饰一个集合。

事实上Vector结合了“可变数组”的集合和同步每个操作的实现。这是另外一个设计上的缺陷。Vector还有些遗留的方法在枚举和元素获取的方法，这些方法不同于List接口，如果这些方法在代码中程序员更趋向于想用它。尽管枚举速度更快，但是他们不能检查如果集合在迭代的时候修改了，这样将导致问题。尽管以上诸多原因，oracle也从没宣称过要废弃Vector.

原文 https://www.evget.com/article/2017/3/27/25996.html