Java collection interview questions that big companies like to ask most

After reading some JAVA interview questions from so-called big companies, I found that they all attach great importance to the use of JAVA collection classes, but I really know very little about this aspect, so I should take the time to learn it.

The java.util package contains a series of important collection classes. For collection classes, the main thing you need to master is its internal structure and the iteration mode for traversing the collection.

Interface: Collection

Collection is the most basic collection interface. A Collection represents a set of Objects, that is, the elements of the Collection. Some Collections allow identical elements and others do not. Some sort and others don't. The Java SDK does not provide classes that directly inherit from Collection. The classes provided by the Java SDK are all "sub-interfaces" that inherit from Collection, such as List and Set.

All classes that implement the Collection interface must provide two standard constructors: the parameterless constructor is used to create an empty Collection, and the constructor with a Collection parameter is used to create a new Collection. This new Collection Has the same elements as the passed Collection. The latter constructor allows the user to copy a Collection.

The main interface method: boolean add(Ojbect c)
Although it returns boolean, it does not indicate whether the addition is successful or not. The meaning of this return value is whether the content of the collection has changed after add() is executed (i.e. Whether the number, position, etc. of elements have changed). Similar addAll, remove, removeAll, remainAll are the same.

Use Iterator mode to traverse a collection

Collection has an important method: iterator(), which returns an Iterator (iterator) for traversing all elements of the collection. The Iterator pattern can abstract access logic from different collection classes, thereby avoiding exposing the internal structure of the collection to the client. Typical usage is as follows:

Iterator it = collection.iterator(); // 获得一个迭代器
while(it.hasNext()) {
    Object obj = it.next(); // 得到下一个元素
}

There is no need to maintain "pointers" for traversing the collection. All internal states are maintained by Iterator, and this Iterator is generated by the collection class through the factory method.

The specific type of Iterator returned by each collection class may be different, but they all implement the Iterator interface. Therefore, we do not need to care about what kind of Iterator it is. It only needs to obtain the Iterator interface. This is the benefit of the interface. , the power of object-oriented.

To ensure that the traversal process is completed smoothly, it is necessary to ensure that the contents of the collection are not changed during the traversal process (except for the remove() method of Iterator). Therefore, the principle to ensure reliable traversal is: use this collection only in one thread, or use it in multiple threads. Synchronize the traversal code in the thread.

The two interfaces derived from the Collection interface are List and Set.

List interface

List is an ordered Collection. Using this interface, you can accurately control the insertion position of each element. Users can access elements in the List using the index (the position of the element in the List, similar to an array subscript), which is similar to a Java array. Unlike the Set mentioned below, List allows the same elements.

In addition to the iterator() method necessary for the Collection interface, List also provides a listIterator() method, which returns a ListIterator interface. Compared with the standard Iterator interface, ListIterator has some more add() and other methods, allowing Add, delete, set elements, and traverse forward or backward.

Common classes that implement the List interface are LinkedList, ArrayList, Vector and Stack.

LinkedList class

LinkedList implements the List interface and allows null elements. In addition, LinkedList provides additional get, remove, and insert methods at the head or tail of LinkedList. These operations allow LinkedList to be used as a stack, queue, or deque.

Note that LinkedList has no synchronized methods. If multiple threads access a List at the same time, they must implement access synchronization themselves. One solution is to construct a synchronized List when creating the List:
List list = Collections.synchronizedList(new LinkedList(…));

ArrayList class

ArrayList implements variable size arrays. It allows all elements, including null. ArrayList is not synchronized.
size, isEmpty, get, set method running time is constant. However, the cost of the add method is an amortized constant, and adding n elements requires O(n) time. Other methods have linear running time.

Each ArrayList instance has a capacity (Capacity), which is the size of the array used to store elements. This capacity increases automatically as new elements are added, but the growth algorithm is not defined. When a large number of elements need to be inserted, the ensureCapacity method can be called to increase the capacity of the ArrayList before inserting to improve insertion efficiency.

Like LinkedList, ArrayList is also unsynchronized.

Vector class

Vector is very similar to ArrayList, but Vector is synchronized. Although the Iterator created by Vector has the same interface as the Iterator created by ArrayList, because Vector is synchronized, when an Iterator is created and is being used, another thread changes the state of the Vector (for example, adding or removing some element), ConcurrentModificationException will be thrown when calling the Iterator method, so the exception must be caught.

Stack class

Stack inherits from Vector and implements a last-in-first-out stack. Stack provides 5 additional methods that allow Vector to be used as a stack. The basic push and pop methods, as well as the peek method, get the element on the top of the stack, the empty method tests whether the stack is empty, and the search method detects the position of an element in the stack. Stack is an empty stack after it is created.

Set interface

Set is a Collection that does not contain duplicate elements, that is, any two elements e1 and e2 have e1.equals(e2)=false, and Set has at most one null element.

Obviously, the Set constructor has a constraint that the passed-in Collection parameter cannot contain duplicate elements.

Please note: Mutable Objects must be handled with care. If a mutable element in a Set changes its state causing Object.equals(Object)=true, it will cause some problems.

Map interface

Please note that Map does not inherit the Collection interface. Map provides key to value mapping. A Map cannot contain the same key, and each key can only map one value. The Map interface provides three kinds of set views. The content of the Map can be regarded as a set of key sets, a set of value sets, or a set of key-value mappings.

Hashtable class

Hashtable inherits the Map interface and implements a hash table of key-value mapping. Any non-null object can be used as key or value.

Use put(key, value) to add data, and get(key) to remove data. The time cost of these two basic operations is constant.

Hashtable adjusts performance through two parameters: initial capacity and load factor. Usually the default load factor 0.75 achieves a better balance between time and space. Increasing the load factor can save space but the corresponding search time will increase, which will affect operations like get and put.

A simple example of using Hashtable is as follows. Put 1, 2, and 3 into the Hashtable, and their keys are "one", "two", and "three" respectively:
Hashtable numbers = new Hashtable();
numbers.put (“one”, new Integer(1));
numbers.put(“two”, new Integer(2));
numbers.put(“three”, new Integer(3));

To take out a number , such as 2, use the corresponding key:
Integer n = (Integer)numbers.get(“two”);
System.out.println(“two = ” + n);

Since the object used as a key will determine the position of the corresponding value by calculating its hash function, any object used as a key must implement the hashCode and equals methods. The hashCode and equals methods inherit from the root class Object. If you use a custom class as a key, be very careful. According to the definition of the hash function, if the two objects are the same, that is, obj1.equals(obj2)=true, then Their hashCode must be the same, but if two objects are different, their hashCode is not necessarily different. If the hashCode of two different objects is the same, this phenomenon is called a conflict. The conflict will cause the time overhead of operating the hash table to increase. Therefore, try to define a well-defined hashCode() method to speed up hash table operations.

If the same object has different hashCode, the operation of the hash table will have unexpected results (the expected get method returns null). To avoid this problem, you only need to remember one thing: override the equals method and hashCode at the same time. methods, rather than just writing one of them.

Hashtable is synchronous.

HashMap class

HashMap is similar to Hashtable, except that HashMap is asynchronous and allows null, that is, null value and null key. , but when treating HashMap as a Collection (the values() method can return a Collection), its iterator operation time overhead is proportional to the capacity of the HashMap. Therefore, if the performance of iterative operations is very important, do not set the initial capacity of HashMap too high or the load factor too low.

WeakHashMap class

WeakHashMap is an improved HashMap, which implements "weak references" to keys. If a key is no longer referenced externally, the key can be recycled by GC.

Summary

If it involves stack, queue and other operations, you should consider using List. For fast insertion and deletion of elements, you should use LinkedList. If you need fast random access to elements, you should use ArrayList.

If the program is in a single-threaded environment, or access is only performed in one thread, consider asynchronous classes, which are more efficient. If multiple threads may operate a class at the same time, synchronized classes should be used.

Pay special attention to the operation of the hash table. The object used as the key must correctly overwrite the equals and hashCode methods.

Try to return the interface rather than the actual type, such as returning List instead of ArrayList, so that if you need to replace ArrayList with LinkedList in the future, the client code does not need to change. This is programming for abstraction.