There are collections in every programming language, and the initial version of Java included several collection classes: Vector, Stack, HashTable, and Array. With the widespread use of collections, Java 1.2 proposed a collection framework that includes all collection interfaces, implementations and algorithms. Java has been going through the process of using generics and concurrent collection classes while ensuring thread safety for a long time. It also includes blocking interfaces and their implementations in the Java concurrency package. Some of the advantages of the collection framework are as follows:
(1) Use core collection classes to reduce development costs instead of implementing our own collection classes.
(2) With the use of rigorously tested collection framework classes, code quality will be improved.
(3) By using the collection classes that come with the JDK, you can reduce code maintenance costs.
(4) Reusability and operability.
Java1.5 introduced generics, and all collection interfaces and implementations use them extensively. Generics allow us to provide a collection with a object type that it can hold, so if you add any element of other type, it will error at compile time. This avoids ClassCastException at runtime, since you will get an error message at compile time. Generics also make the code cleaner, we don't need to use explicit conversions and instanceOfoperators. It also brings benefits to the runtime because no type-checked bytecode instructions are generated.
Collection is the root interface of the collection level. A collection represents a set of objects that are its elements. The Java platform does not provide any direct implementation of this interface.
Set is a collection that cannot contain duplicate elements. This interface models a mathematical set abstraction and is used to represent sets, like a deck of cards.
List is an ordered collection that can contain repeated elements. You can access any element by its index. List is more like an array whose length changes dynamically.
Map is an object that maps keys to values. A Map cannot contain duplicate keys: each key can only map at most one value.
Some other interfaces are Queue, Dequeue, SortedSet, SortedMap and ListIterator.
The Collection interface specifies a set of objects, and the objects are its elements. How these elements are maintained is determined by the specific implementation of the Collection. For example, some Collection implementations such as List allow duplicate elements, while others such as Set do not. Many Collection implementations have a public clone method. However, it doesn't make sense to put it in all implementations of collections. This is because Collection is an abstract representation. What matters is implementation.
The semantics and implications of cloning or serialization come into play when dealing with specific implementations. So, the implementation should decide how to clone or serialize it, or whether it can be cloned or serialized at all.
Empower cloning and serialization in all implementations, ultimately leading to less flexibility and more restrictions. The specific implementation should decide whether it can be cloned and serialized.
Although the Map interface and its implementation are also part of the collection framework, Map is not a collection, and collections are not Maps. Therefore, it makes no sense for Map to inherit Collection and vice versa.
If Map inherits the Collection interface, where do the elements go? Map contains key-value pairs, which provides methods for extracting key or value list collections, but it does not fit the "set of objects" specification.
Iterator interface Provides an interface for traversing any Collection. We can use the iterator method to get an iterator instance from a Collection. Iterators replace Enumeration in the Java collection framework. Iterators allow the caller to remove elements during the iteration process.
Enumeration is twice as fast as Iterator and uses less memory. Enumeration is very basic and meets basic needs. However, compared with Enumeration, Iterator is safer because it prevents other threads from modifying the collection while a collection is being traversed.
Iterator replaces Enumeration in Java collection framework. Iterators allow the caller to remove elements from a collection, whereas Enumeration cannot. Iterator method names have been improved to make its functionality clearer.
The semantics are unclear. What is known is that the Iterator protocol cannot ensure the order of iteration. Note, however, that ListIterator does not provide an add operation, which ensures the order of iteration.
It can be implemented at the top level of the current Iterator, but it is rarely used. If it is added to the interface, every inheritance must implement it, which makes no sense.
(1) We can use Iterator to traverse Set and List collections, while ListIterator can only traverse List.
(2) Iterator can only traverse forward, while LIstIterator can traverse in both directions.
(3) ListIterator inherits from the Iterator interface, and then adds some additional functions, such as adding an element, replacing an element, and getting the index position of the previous or following element.
List<String> strList = new ArrayList<>();
//使用for-each循环
for(String obj : strList){
System.out.println(obj);
}
//using iterator
Iterator<String> it = strList.iterator();
while(it.hasNext()){
String obj = it.next();
System.out.println(obj);
}Using iterators is more thread-safe because it ensures that when the currently traversed collection elements are changed, it will throw a ConcurrentModificationException.
Every time we try to get the next element, the Iterator fail-fast property checks for any changes in the current collection structure. If any modifications are found, it throws ConcurrentModificationException. All Iterator implementations in Collection are designed to be fail-fast (except for concurrent collection classes such as ConcurrentHashMap and CopyOnWriteArrayList).
The fail-fast attribute of Iterator works with the current collection, so it will not be affected by any changes in the collection. All collection classes in the Java.util package are designed to be fail-fast, while the collection classes in java.util.concurrent are fail-safe. Fail-fast iterators throw ConcurrentModificationException, while fail-safe iterators never throw ConcurrentModificationException.
When traversing a collection, we can use concurrent collection classes to avoid ConcurrentModificationException, such as using CopyOnWriteArrayList instead of ArrayList.
The Iterator interface defines methods for traversing collections, but its implementation is the responsibility of the collection implementation class. Each collection class that returns an Iterator for traversal has its own Iterator implementation inner class.
This allows collection classes to choose whether the iterator is fail-fast or fail-safe. For example, the ArrayList iterator is fail-fast, and the CopyOnWriteArrayList iterator is fail-safe.
UnsupportedOperationException is an exception used to indicate that the operation is not supported. It has been widely used in JDK classes. In the collection framework java.util.Collections.UnmodifiableCollection will throw this exception in all add and remove operations.
HashMap stores key-value pairs in Map.Entrystaticinternal class implementation. HashMap uses hash algorithm, and in put and get methods, it uses hashCode() and equals() methods. When we call the put method by passing the key-value pair, HashMap uses Key hashCode() and the hashing algorithm to find the index where the key-value pair is stored. Entry is stored in a LinkedList, so if the entry exists, it uses the equals() method to check if the passed key already exists, if it exists, it overwrites the value, if it does not exist, it creates a new entry and then saves it. When we call the get method by passing the key, it again uses hashCode() to find the index in the array and then uses the equals() method to find out the correct Entry and then returns its value. The pictures below explain the details.
Other important issues regarding HashMap are capacity, load factor and threshold adjustment. The default initial capacity of HashMap is 32, and the load factor is 0.75. The threshold is the load factor multiplied by the capacity. Whenever we try to add an entry, if the map size is larger than the threshold, HashMap will rehash the map contents and use the larger capacity. Capacity is always a power of 2, so if you know you need to store a large number of key-value pairs, such as cachingdata pulled from a database, it is a good idea to initialize the HashMap with the correct capacity and load factor way of doing.
HashMap uses the hashCode() and equals() methods of the Key object to determine the index of the key-value pair. These methods are also used when we try to get values from HashMap. If these methods are not implemented correctly, in which case two different keys may produce the same hashCode() and equals() output, the HashMap will consider them to be the same and overwrite them instead of replacing them. Store in different places. Likewise, all collection classes that do not allow the storage of duplicate data use hashCode() and equals() to find duplicates, so it is very important to implement them correctly. The implementation of equals() and hashCode() should follow the following rules:
(1) If o1.equals(o2), then o1.hashCode() == o2.hashCode() is always true.
（2）如果o1.hashCode() == o2.hashCode()，并不意味着o1.equals(o2)会为true。
我们可以使用任何类作为Map的key，然而在使用它们之前，需要考虑以下几点：
（1）如果类重写了equals()方法，它也应该重写hashCode()方法。
（2）类的所有实例需要遵循与equals()和hashCode()相关的规则。请参考之前提到的这些规则。
（3）如果一个类没有使用equals()，你不应该在hashCode()中使用它。
（4）用户自定义key类的最佳实践是使之为不可变的，这样，hashCode()值可以被缓存起来，拥有更好的性能。不可变的类也可以确保hashCode()和equals()在未来不会改变，这样就会解决与可变相关的问题了。
比如，我有一个类MyKey，在HashMap中使用它。
//传递给MyKey的name参数被用于equals()和hashCode()中 MyKey key = new MyKey('Pankaj'); //assume hashCode=1234 myHashMap.put(key, 'Value'); // 以下的代码会改变key的hashCode()和equals()值 key.setName('Amit'); //assume new hashCode=7890 //下面会返回null，因为HashMap会尝试查找存储同样索引的key，而key已被改变了，匹配失败，返回null myHashMap.get(new MyKey('Pankaj'));
那就是为何String和Integer被作为HashMap的key大量使用。
Map接口提供三个集合视图：
（1）Set keyset()：返回map中包含的所有key的一个Set视图。集合是受map支持的，map的变化会在集合中反映出来，反之亦然。当一个迭代器正在遍历一个集合时，若map被修改了（除迭代器自身的移除操作以外），迭代器的结果会变为未定义。集合支持通过Iterator的Remove、Set.remove、removeAll、retainAll和clear操作进行元素移除，从map中移除对应的映射。它不支持add和addAll操作。
（2）Collection values()：返回一个map中包含的所有value的一个Collection视图。这个collection受map支持的，map的变化会在collection中反映出来，反之亦然。当一个迭代器正在遍历一个collection时，若map被修改了（除迭代器自身的移除操作以外），迭代器的结果会变为未定义。集合支持通过Iterator的Remove、Set.remove、removeAll、retainAll和clear操作进行元素移除，从map中移除对应的映射。它不支持add和addAll操作。
（3）Set
（1）HashMap允许key和value为null，而HashTable不允许。
（2）HashTable是同步的，而HashMap不是。所以HashMap适合单线程环境，HashTable适合多线程环境。
（3）在Java1.4中引入了LinkedHashMap，HashMap的一个子类，假如你想要遍历顺序，你很容易从HashMap转向LinkedHashMap，但是HashTable不是这样的，它的顺序是不可预知的。
（4）HashMap提供对key的Set进行遍历，因此它是fail-fast的，但HashTable提供对key的Enumeration进行遍历，它不支持fail-fast。
（5）HashTable被认为是个遗留的类，如果你寻求在迭代的时候修改Map，你应该使用CocurrentHashMap。
对于在Map中插入、删除和定位元素这类操作，HashMap是最好的选择。然而，假如你需要对一个有序的key集合进行遍历，TreeMap是更好的选择。基于你的collection的大小，也许向HashMap中添加元素会更快，将map换为TreeMap进行有序key的遍历。
ArrayList和Vector在很多时候都很类似。
（1）两者都是基于索引的，内部由一个数组支持。
（2）两者维护插入的顺序，我们可以根据插入顺序来获取元素。
（3）ArrayList和Vector的迭代器实现都是fail-fast的。
（4）ArrayList和Vector两者允许null值，也可以使用索引值对元素进行随机访问。
以下是ArrayList和Vector的不同点。
（1）Vector是同步的，而ArrayList不是。然而，如果你寻求在迭代的时候对列表进行改变，你应该使用CopyOnWriteArrayList。
（2）ArrayList比Vector快，它因为有同步，不会过载。
（3）ArrayList更加通用，因为我们可以使用Collections工具类轻易地获取同步列表和只读列表。
Array可以容纳基本类型和对象，而ArrayList只能容纳对象。
Array是指定大小的，而ArrayList大小是固定的。
Array does not provide as many functions as ArrayList, such as addAll, removeAll and iterator. Although ArrayList is obviously the better choice, there are times when Array is better.
(1) If the size of the list has been specified, in most cases they are stored and traversed.
(2) For traversing basic data types, although Collections use autoboxing to ease the coding task, working on a list of basic types of a specified size will also become very slow.
(3) If you want to use multidimensional array, it is easier to use [][] than List
Both ArrayList and LinkedList implement the List interface, but there are some differences between them.
(1) ArrayList is a data structure based on an index supported by Array, so it provides random access to elements with a complexity of O(1), but LinkedList stores a series of node data, each Each node is connected to the previous and next node. Therefore, although there is a method to obtain elements using indexes, the internal implementation is to traverse from the starting point, traverse to the indexed node and then return the element. The time complexity is O(n), which is slower than ArrayList.
(2) Compared with ArrayList, inserting, adding and deleting an element in LinkedList will be faster, because when an element is inserted into the middle, it does not involve changing the size of the array or updating the index. .
(3) LinkedList consumes more memory than ArrayList because each node in LinkedList stores references to the previous and next nodes.
The ArrayList, HashMap, TreeMap and HashTable classes provide random access to elements.
java.util.EnumSet is a collection implementation using enumeration types. When a collection is created, all elements in the enumeration collection must come from a single specified enumeration type, either explicitly or implicitly. EnumSet is unsynchronized and does not allow null elements. It also provides some useful methods, such as copyOf(Collection c), of(E first,E...rest) and complementOf(EnumSet s).
Vector, HashTable, Properties and Stack are synchronization classes, so they are thread-safe and can be used in a multi-threaded environment. The Java 1.5 concurrency API includes some collection classes that allow modification during iteration, and because they all work on clones of the collection, they are safe in a multi-threaded environment.
Java1.5 concurrent package (java.util.concurrent) contains thread-safe collection classes that allow collections to be modified during iteration. Iterators are designed to be fail-fast and will throw ConcurrentModificationException. Some classes are: CopyOnWriteArrayList, ConcurrentHashMap, CopyOnWriteArraySet.
Java.util.concurrent.BlockingQueue is a queue. When retrieving or removing an element, it will wait for the queue to become non-empty; when adding an element, it will wait for the queue to become non-empty. Available space. The BlockingQueue interface is part of the Java collection framework and is mainly used to implement the producer-consumer pattern. We don't need to worry about waiting for the producer to have available space, or the consumer to have available objects, because it is all handled in the BlockingQueue implementation class. Java provides centralized BlockingQueue implementations, such as ArrayBlockingQueue, LinkedBlockingQueue, PriorityBlockingQueue, SynchronousQueue, etc.
Both stacks and queues are used to pre-store data. java.util.Queue is an interface, and its implementation class is in the Java concurrency package. Queues allow elements to be retrieved on a first-in-first-out (FIFO) basis, but this is not always the case. The Deque interface allows retrieving elements from both ends.
A stack is similar to a queue, but it allows for last-in-first-out (LIFO) retrieval of elements.
Stack is a class that extends from Vector, and Queue is an interface.
Java.util.Collections is a utility class containing only static methods that operate on or return collections. It contains polymorphic algorithms that operate on collections, return a new collection backed by the specified collection, and a few other things. This class contains methods for collection framework algorithms, such as binary search, sorting, shuffling, and reverse ordering.
If we want to use the sorting method of Array or Collection, we need to implement the Comparable interface provided by Java in the custom class. The Comparable interface has compareTo(T OBJ) method, which is used by the sorting method. We should override this method so that it returns a negative integer, 0, or a positive integer if the "this" object is smaller, equal, or larger than the passed object argument. However, in most practical cases we want to sort based on different parameters. For example, as a CEO, I want to sort employees based on salary, and an HR wants to sort them based on age. This is the situation where we need to use the Comparator interface, because the Comparable.compareTo(Object o) method implementation can only sort based on one field, and we cannot select the field according to the needs of object sorting. The implementation of the compare(Object o1, Object o2) method of the Comparator interface needs to pass two object parameters. If the first parameter is smaller than the second, a negative integer is returned; if the first parameter is equal to the second, 0 is returned; if the first parameter is smaller than the second parameter, a negative integer is returned. If one is greater than the second, a positive integer is returned.
Comparable and Comparator interfaces are used to sort object collections or arrays. The Comparable interface is used to provide natural ordering of objects, and we can use it to provide ordering based on a single logic.
The Comparator interface is used to provide different sorting algorithms. We can choose the Comparator we need to use to sort a given object collection.
If we need to sort an array of objects, we can use the Arrays.sort() method. If we need to sort a list of objects, we can use the Collection.sort() method. Both classes have overloaded method sort() for natural sorting (using Comparable) or criteria-based sorting (using Comparator). Collections internally use the array sorting method, so both of them have the same performance, except that Collections take time to convert the list into an array.
We can use the Collections.unmodifiableCollection(Collection c) method to create a read-only collection before passing it as a parameter, which will ensure that any operation that changes the collection will throw an UnsupportedOperationException.
We can use Collections.synchronizedCollection(Collection c) to obtain a synchronized (thread-safe) collection based on the specified collection.
The Java collection framework provides common algorithm implementations, such as sorting and searching. The Collections class contains implementations of these methods. Most of the algorithms operate on Lists, but some are available for all types of collections. Some algorithms include sorting, search, mixing, and max-min.
The capital O describes the performance of an algorithm in terms of a series of elements in the data structure. The Collection class is the actual data structure, and we usually choose a collection implementation with a capital O based on time, memory, and performance. For example: Example 1: ArrayList's get(index i) is a constant time operation, which does not depend on the number of elements in the list. So its performance is O(1). Example 2: The performance of a linear search in an array or list is O(n) because we need to traverse all elements to find the required element.
(1) Select the correct collection type as needed. For example, if size is specified, we will use Array instead of ArrayList. If we want to traverse a Map according to insertion order, we need to use TreeMap. If we don't want to repeat, we should use Set.
(2) Some collection classes allow specifying the initial capacity, so if we can estimate the number of stored elements, we can use it and avoid rehashing or resizing.
(3) Based on interface programming rather than implementation programming, it allows us to easily change the implementation later.
(4) Always use type-safe generics to avoid ClassCastException at runtime.
(5) Use the immutable class provided by JDK as the key of Map to avoid implementing hashCode() and equals() yourself.
(6) Use the Collections tool class as much as possible, or get a read-only, synchronized or empty collection instead of writing your own implementation. It will provide code reusability, and it will have better stability and maintainability.
The above is the detailed content of Summary of Java Collections Interview Questions and Answers. For more information, please follow other related articles on the PHP Chinese website!
![[Web front-end] Node.js quick start](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
