1. Introduction
1.绪论
Java Collections is a topic often brought up on technical interviews for Java developers. This article reviews some important questions that are asked most often and may be tricky to get right.
Java集合是一个经常在Java开发人员的技术面试中被提及的话题。本文回顾了一些最常被问到的重要问题，这些问题可能很棘手，要想答对。
2. Questions
2.问题
Q1. Describe the Collections Type Hierarchy. What Are the Main Interfaces, and What Are the Differences Between Them?
Q1.描述一下集合类型的层次结构 主要的接口是什么，它们之间的区别是什么？
The Iterable interface represents any collection that can be iterated using the for-each loop. The Collection interface inherits from Iterable and adds generic methods for checking if an element is in a collection, adding and removing elements from the collection, determining its size etc.
Iterable接口代表任何可以使用for-each循环进行迭代的集合。Collection接口继承自Iterable，并增加了通用方法，用于检查一个元素是否在一个集合中，从集合中添加和删除元素，确定其大小等。
The List, Set, and Queue interfaces inherit from the Collection interface.
List、Set和Queue接口继承于Collection接口。
List is an ordered collection, and its elements can be accessed by their index in the list.
List是一个有序的集合，其元素可以通过它们在列表中的索引来访问。
Set is an unordered collection with distinct elements, similar to the mathematical notion of a set.
集是一个具有不同元素的无序集合，类似于数学上的集合概念。
Queue is a collection with additional methods for adding, removing and examining elements, useful for holding elements prior to processing.
Queue是一个集合，具有额外的添加、移除和检查元素的方法，对于在处理前保存元素很有用。
Map interface is also a part of the collection framework, yet it does not extend Collection. This is by design, to stress the difference between collections and mappings which are hard to gather under a common abstraction. The Map interface represents a key-value data structure with unique keys and no more than one value for each key.
Map接口也是集合框架的一部分，但它并没有扩展Collection。这是为了强调集合和映射之间的区别，而后者很难在一个共同的抽象下集合。Map接口表示一个键值数据结构，具有唯一的键，每个键不超过一个值。
Q2. Describe Various Implementations of the Map Interface and Their Use Case Differences.
问题2 描述地图接口的各种实现及其用例的差异
One of the most often used implementations of the Map interface is the HashMap. It is a typical hash map data structure that allows accessing elements in constant time, or O(1), but does not preserve order and is not thread-safe.
Map接口的一个最常用的实现是HashMap。它是一个典型的哈希图数据结构，允许在恒定时间内访问元素，或者说是O(1)，但是不保留顺序，也不是线程安全的。
To preserve insertion order of elements, you can use the LinkedHashMap class which extends the HashMap and additionally ties the elements into a linked list, with foreseeable overhead.
为了保持元素的插入顺序，你可以使用LinkedHashMap类，该类扩展了HashMap，并额外将元素捆绑成一个链接列表，其开销可想而知。
The TreeMap class stores its elements in a red-black tree structure, which allows accessing elements in logarithmic time, or O(log(n)). It is slower than the HashMap for most cases, but it allows keeping the elements in order according to some Comparator.
TreeMap类以红黑树结构存储其元素，这允许在对数时间内访问元素，即O(log(n))。在大多数情况下，它比HashMap慢，但它允许根据一些Comparator保持元素的顺序。
The ConcurrentHashMap is a thread-safe implementation of a hash map. It provides full concurrency of retrievals (as the get operation does not entail locking) and high expected concurrency of updates.
ConcurrentHashMap是一个哈希图的线程安全实现。它提供了全并发的检索（因为get操作不需要加锁）和高预期的更新并发性。
The Hashtable class has been in Java since version 1.0. It is not deprecated but is mostly considered obsolete. It is a thread-safe hash map, but unlike ConcurrentHashMap, all its methods are simply synchronized, which means that all operations on this map block, even retrieval of independent values.
Hashtable类从1.0版本开始就在Java中出现了。它没有被废弃，但大多被认为是过时的。它是一个线程安全的哈希图，但与ConcurrentHashMap不同，它的所有方法都是简单的synchronized，这意味着这个图上的所有操作都是阻塞的，甚至检索独立的值。
Q3. Explain the Difference Between Linkedlist and Arraylist.
问题3.解释一下Linkedlist和Arraylist之间的区别
ArrayList is an implementation of the List interface that is based on an array. ArrayList internally handles resizing of this array when the elements are added or removed. You can access its elements in constant time by their index in the array. However, inserting or removing an element infers shifting all consequent elements which may be slow if the array is huge and the inserted or removed element is close to the beginning of the list.
ArrayList是List接口的一个实现，它基于一个数组。ArrayList在内部处理当元素被添加或移除时对该数组的大小调整。您可以通过其在数组中的索引在恒定时间内访问其元素。然而，插入或删除一个元素会推断出所有随之而来的元素，如果数组很大，而且插入或删除的元素靠近列表的开头，那么这可能会很慢。
LinkedList is a doubly-linked list: single elements are put into Node objects that have references to previous and next Node. This implementation may appear more efficient than ArrayList if you have lots of insertions or deletions in different parts of the list, especially if the list is large.
LinkedList是一个双重链接的列表：单个元素被放入Node对象中，该对象对上一个和下一个Node有引用。如果你在列表的不同部分有大量的插入或删除，特别是在列表很大的情况下，这种实现可能比ArrayList更有效率。
In most cases, however, ArrayList outperforms LinkedList. Even elements shifting in ArrayList, while being an O(n) operation, is implemented as a very fast System.arraycopy() call. It can even appear faster than the LinkedList‘s O(1) insertion which requires instantiating a Node object and updating multiple references under the hood. LinkedList also can have a large memory overhead due to a creation of multiple small Node objects.
然而，在大多数情况下，ArrayList胜过了LinkedList。即使是ArrayList中的元素移位，虽然是一个O(n)操作，但却被实现为一个非常快的System.arraycopy()调用。它甚至可以显得比LinkedList的O(1)插入更快，后者需要实例化一个Node对象并更新引擎下的多个引用。LinkedList也会因为创建多个小Node对象而产生较大的内存开销。
Q4. What Is the Difference Between Hashset and Treeset?
Q4.Hashset和Treeset之间的区别是什么？
Both HashSet and TreeSet classes implement the Set interface and represent sets of distinct elements. Additionally, TreeSet implements the NavigableSet interface. This interface defines methods that take advantage of the ordering of elements.
HashSet和TreeSet类都实现了Set接口，代表不同元素的集合。此外，TreeSet实现了NavigableSet接口。这个接口定义了利用元素的排序的方法。
HashSet is internally based on a HashMap, and TreeSet is backed by a TreeMap instance, which defines their properties: HashSet does not keep elements in any particular order. Iteration over the elements in a HashSet produces them in a shuffled order. TreeSet, on the other hand, produces elements in order according to some predefined Comparator.
HashSet内部基于HashMap，而TreeSet则由TreeMap实例支持，该实例定义了它们的属性。HashSet不会以任何特定的顺序保留元素。对HashSet中的元素进行迭代时，会以洗牌的顺序产生它们。另一方面，TreeSet根据一些预定义的Comparator来产生元素的顺序。
Q5. How Is Hashmap Implemented in Java? How Does Its Implementation Use Hashcode and Equals Methods of Objects? What Is the Time Complexity of Putting and Getting an Element from Such Structure?
Q5.Hashmap在Java中是如何实现的？它的实现是如何使用对象的哈希码和等价方法的？从这种结构中放置和获取一个元素的时间复杂性是什么？
The HashMap class represents a typical hash map data structure with certain design choices.
HashMap类代表了一个典型的哈希图数据结构，有一定的设计选择。
The HashMap is backed by a resizable array that has a size of power-of-two. When the element is added to a HashMap, first its hashCode is calculated (an int value). Then a certain number of lower bits of this value are used as an array index. This index directly points to the cell of the array (called a bucket) where this key-value pair should be placed. Accessing an element by its index in an array is a very fast O(1) operation, which is the main feature of a hash map structure.
HashMap是由一个可调整大小的数组支持的，该数组的大小为2的幂。当元素被添加到HashMap时，首先它的hashCode被计算出来（一个int值）。然后这个值的一定数量的低位被用作数组索引。这个索引直接指向数组中的单元（称为桶），这个键值对应该被放置在那里。通过数组中的索引访问一个元素是一个非常快速的O(1)操作，这是哈希图结构的主要特点。
A hashCode is not unique, however, and even for different hashCodes, we may receive the same array position. This is called a collision. There is more than one way of resolving collisions in the hash map data structures. In Java’s HashMap, each bucket actually refers not to a single object, but to a red-black tree of all objects that landed in this bucket (prior to Java 8, this was a linked list).
然而，一个hashCode不是唯一的，即使是不同的hashCodes，我们也可能收到相同的数组位置。这就是所谓的碰撞。在哈希图数据结构中，有不止一种解决碰撞的方法。在Java的HashMap中，每个桶实际上不是指单个对象，而是指落在这个桶中的所有对象的红黑树（在Java 8之前，这是一个链接列表）。
So when the HashMap has determined the bucket for a key, it has to traverse this tree to put the key-value pair in its place. If a pair with such key already exists in the bucket, it is replaced with a new one.
因此，当HashMap为一个键确定了桶时，它必须遍历这个树来把键值对放在它的位置上。如果桶中已经存在这样的键值对，它将被替换成一个新的键值对。
To retrieve the object by its key, the HashMap again has to calculate the hashCode for the key, find the corresponding bucket, traverse the tree, call equals on keys in the tree and find the matching one.
为了通过键来检索对象，HashMap必须再次计算键的hashCode，找到相应的桶，遍历树，对树中的键调用equals，并找到匹配的键。
HashMap has O(1) complexity, or constant-time complexity, of putting and getting the elements. Of course, lots of collisions could degrade the performance to O(log(n)) time complexity in the worst case, when all elements land in a single bucket. This is usually solved by providing a good hash function with a uniform distribution.
HashMap的复杂度为O(1)，或者说是恒定的时间复杂度，用于放置和获取元素。当然，在最坏的情况下，当所有元素都落在一个桶里时，大量的碰撞会使性能下降到O(log(n))的时间复杂度。这通常是通过提供一个具有均匀分布的好的哈希函数来解决的。
When the HashMap internal array is filled (more on that in the next question), it is automatically resized to be twice as large. This operation infers rehashing (rebuilding of internal data structures), which is costly, so you should plan the size of your HashMap beforehand.
当HashMap内部数组被填满时（在下一个问题中会详细说明），它的大小会被自动调整为两倍大。这个操作推导出重新洗牌（重建内部数据结构），成本很高，所以你应该事先计划好HashMap的大小。
Q6. What Is the Purpose of the Initial Capacity and Load Factor Parameters of a Hashmap? What Are Their Default Values?
Q6.哈希图的初始容量和负载因子参数的目的是什么？它们的默认值是什么？
The initialCapacity argument of the HashMap constructor affects the size of the internal data structure of the HashMap, but reasoning about the actual size of a map is a bit tricky. The HashMap‘s internal data structure is an array with the power-of-two size. So the initialCapacity argument value is increased to the next power-of-two (for instance, if you set it to 10, the actual size of the internal array will be 16).
HashMap构造函数的initialCapacity参数会影响到HashMap的内部数据结构的大小，但是对地图的实际大小进行推理是有点麻烦的。HashMap的内部数据结构是一个大小为2次方的数组。所以initialCapacity参数值会增加到2的次幂（例如，如果你设置为10，内部数组的实际大小将是16）。
The load factor of a HashMap is the ratio of the element count divided by the bucket count (i.e. internal array size). For instance, if a 16-bucket HashMap contains 12 elements, its load factor is 12/16 = 0.75. A high load factor means a lot of collisions, which in turn means that the map should be resized to the next power of two. So the loadFactor argument is a maximum value of the load factor of a map. When the map achieves this load factor, it resizes its internal array to the next power-of-two value.
HashMap的负载因子是元素数除以桶数（即内部数组大小）的比率。例如，如果一个16个桶的HashMap包含12个元素，其负载因子为12/16 = 0.75。高负载因子意味着大量的碰撞，这反过来又意味着地图的大小应该被调整到2的次幂。所以loadFactor参数是一个地图的负载系数的最大值。当地图达到这个负载因子时，它就会将其内部数组的大小调整到下一个2的幂值。
The initialCapacity is 16 by default, and the loadFactor is 0.75 by default, so you could put 12 elements in a HashMap that was instantiated with the default constructor, and it would not resize. The same goes for the HashSet, which is backed by a HashMap instance internally.
initialCapacity默认为16，loadFactor默认为0.75，所以你可以在一个用默认构造函数实例化的HashMap中放入12个元素，而它将不会调整大小。HashSet也是如此，它在内部是由HashMap实例支持的。
Consequently, it is not trivial to come up with initialCapacity that satisfies your needs. This is why the Guava library has Maps.newHashMapWithExpectedSize() and Sets.newHashSetWithExpectedSize() methods that allow you to build a HashMap or a HashSet that can hold the expected number of elements without resizing.
因此，想出满足你需求的initialCapacity并非易事。这就是为什么Guava库有Maps.newHashMapWithExpectedSize()和Sets.newHashSetWithExpectedSize()方法，允许你建立一个HashMap或HashSet，可以容纳预期的元素数量而无需调整大小。
Q7. Describe Special Collections for Enums. What Are the Benefits of Their Implementation Compared to Regular Collections?
Q7.描述一下枚举的特殊集合 与普通集合相比，它们的实现有什么好处？
EnumSet and EnumMap are special implementations of Set and Map interfaces correspondingly. You should always use these implementations when you’re dealing with enums because they are very efficient.
EnumSet和EnumMap是Set和Map接口的特殊实现。当你处理枚举时，你应该总是使用这些实现，因为它们非常高效。
An EnumSet is just a bit vector with “ones” in the positions corresponding to ordinal values of enums present in the set. To check if an enum value is in the set, the implementation simply has to check if the corresponding bit in the vector is a “one”, which is a very easy operation. Similarly, an EnumMap is an array accessed with enum’s ordinal value as an index. In the case of EnumMap, there is no need to calculate hash codes or resolve collisions.
一个EnumSet只是一个位向量，在对应于集合中枚举的序数值的位置上有 “1”。要检查一个枚举值是否在集合中，实现者只需检查向量中的相应位是否为 “一”，这是一个非常简单的操作。类似地，EnumMap是一个以枚举的序数值为索引访问的数组。在EnumMap的情况下，不需要计算哈希代码或解决碰撞问题。
Q8. What Is the Difference Between Fail-Fast and Fail-Safe Iterators?
Q8.失败-快速和失败-安全迭代器之间的区别是什么？
Iterators for different collections are either fail-fast or fail-safe, depending on how they react to concurrent modifications. The concurrent modification is not only a modification of collection from another thread but also modification from the same thread but using another iterator or modifying the collection directly.
不同集合的迭代器要么是故障快速的，要么是故障安全的，取决于它们对并发修改的反应。并发修改不仅是指从另一个线程对集合的修改，也包括从同一线程但使用另一个迭代器或直接修改集合的修改。
Fail-fast iterators (those returned by HashMap, ArrayList, and other non-thread-safe collections) iterate over the collection’s internal data structure, and they throw ConcurrentModificationException as soon as they detect a concurrent modification.
失败-快速迭代器（由HashMap、ArrayList和其他非线程安全集合返回的迭代器）在集合的内部数据结构上进行迭代，并且一旦检测到并发修改，就会抛出ConcurrentModificationException。
Fail-safe iterators (returned by thread-safe collections such as ConcurrentHashMap, CopyOnWriteArrayList) create a copy of the structure they iterate upon. They guarantee safety from concurrent modifications. Their drawbacks include excessive memory consumption and iteration over possibly out-of-date data in case the collection was modified.
失败安全迭代器（由线程安全集合返回，如ConcurrentHashMap、CopyOnWriteArrayList）创建了它们所迭代结构的副本。它们保证了并发修改的安全性。它们的缺点包括过度的内存消耗，以及在集合被修改的情况下对可能过时的数据进行迭代。
Q9. How Can You Use Comparable and Comparator Interfaces to Sort Collections?
Q9.你如何使用比较器和比较器接口对集合进行排序？
The Comparable interface is an interface for objects that can be compared according to some order. Its single method is compareTo, which operates on two values: the object itself and the argument object of the same type. For instance, Integer, Long, and other numeric types implement this interface. String also implements this interface, and its compareTo method compares strings in lexicographical order.
Comparable接口是一个对象的接口，可以按照某种顺序进行比较。它的单一方法是compareTo，它对两个值进行操作：对象本身和相同类型的参数对象。例如，Integer、Long和其它数字类型实现了这个接口。String也实现了这个接口，它的compareTo方法按词典顺序对字符串进行比较。
The Comparable interface allows to sort lists of corresponding objects with the Collections.sort() method and uphold the iteration order in collections that implement SortedSet and SortedMap. If your objects can be sorted using some logic, they should implement the Comparable interface.
Comparable接口允许用Collections.sort()方法对相应对象的列表进行排序，并在实现SortedSet和SortedMap的集合中维护迭代顺序。如果你的对象可以使用一些逻辑进行排序，它们应该实现Comparable接口。
The Comparable interface usually is implemented using natural ordering of the elements. For instance, all Integer numbers are ordered from lesser to greater values. But sometimes you may want to implement another kind of ordering, for instance, to sort the numbers in descending order. The Comparator interface can help here.
Comparable接口通常使用元素的自然排序来实现。例如，所有的Integer数字都是从小值到大值排序。但有时你可能想实现另一种排序，例如，将数字按降序排序。Comparator接口可以在这里提供帮助。
The class of the objects you want to sort does not need to implement this interface. You simply create an implementing class and define the compare method which receives two objects and decides how to order them. You may then use the instance of this class to override the natural ordering of the Collections.sort() method or SortedSet and SortedMap instances.
你想排序的对象的类不需要实现这个接口。你只需创建一个实现类并定义compare方法，该方法接收两个对象并决定如何对它们排序。然后你可以使用这个类的实例来覆盖Collections.sort()方法或SortedSet和SortedMap实例的自然排序。
As the Comparator interface is a functional interface, you may replace it with a lambda expression, as in the following example. It shows ordering a list using a natural ordering (Integer‘s Comparable interface) and using a custom iterator (Comparator<Integer> interface).
由于Comparator接口是一个函数接口，你可以用一个lambda表达式来代替它，如下面的例子。它显示了使用自然排序（Integer的Comparable接口）和使用自定义迭代器（Comparator<Integer>接口）对一个列表排序。
List<Integer> list1 = Arrays.asList(5, 2, 3, 4, 1);
Collections.sort(list1);
assertEquals(new Integer(1), list1.get(0));
List<Integer> list1 = Arrays.asList(5, 2, 3, 4, 1);
Collections.sort(list1, (a, b) -> b - a);
assertEquals(new Integer(5), list1.get(0));