Java collection is I think the most important knowledge in the Java foundation, Java collection is must master. When I interview, as long as the face of Java, it must be a Java collection.
Java has a rich family of collections, including ArrayList, HashMap, HashSet, Stack, Queue, thread-safe Vector, HashTable, etc. There are also thread-unsafe linkedLists, TreeMap, and so on! The diagram above shows the members of the entire collection family and their relationships. The following is a brief introduction to the above various interfaces and base classes (mainly introduces the characteristics of each collection. Difference).
List Collection The List interface is the direct interface of Collection. What a List represents is an ordered Collection, that is, it maintains the order of elements with some particular insertion order. The user has precise control over the insertion position of each element in the list, and can access elements based on their integer index (position in the list) and search for elements in the list. List interface implementation of the main set of: ArrayList, LinkedList, Vector, Stack.
The most common collection classes under List collections are ArrayList and LinkedList
ArrayList ArrayList uses arrays as storage structures, which are thread-unsafe collections. It is fast to query and slow to add and delete in the middle or head of an array, so it can replace a Vector except that it is not thread-safe, and a thread-safe ArrayList can use CopyOnWriteArrayList instead of a Vector.
There are a few important points to note about ArrayList:
With random access, ArrayList is efficient in accessing elements. ArrayList is inefficient in frequently inserting and deleting collection elements.
Underlying data structure: ArrayList The underlying data structure uses arrays as storage structures, which are fast in searching and slow in adding and deleting
Thread-safety: An ArrayList is a collection of thread-unsafe objects
When the ArrayList is expanded for the first time, the length is 10, and the minimum size of the container is calculated when add() is called. You can see that if the array elementData is empty, the minimum size is set to 10, and then the array length is expanded to 10 for the first time.
From the second expansion of the collection, the array size is increased by 1.5 times, that is, newLength = oldLength * 1.5\
LinkedList
The underlying LinkedList uses bidirectional LinkedList data structure to store elements. Since the memory address of the LinkedList is not continuous, it does not have the characteristics of random access. However, because it uses Pointers to connect various elements, it only needs to operate Pointers to insert and delete elements, without moving elements, so it has the characteristics of fast addition and deletion and slow query. It is also a non-thread-safe collection.
Because of the bidirectional linked list as the data structure, it is a thread unsafe collection; Each stored Node is called a Node. As you can see in the figure below, Node holds Pointers to next and prev, and item is the value of this Node. The time complexity remains O(1) for both inserts and deletions
In addition to being a collection implemented as a LinkedList, there are some special features to note about LinkedList.
Advantages: there is no capacity expansion mechanism at the bottom of LinkedList and bidirectional LinkedList is used to store elements, so it is efficient to insert and delete elements. It is suitable for scenes with frequent operation of elements. Disadvantages: LinkedList does not have random access, and searching for an element can only be compared one by one from the head or tail pointer, so it is inefficient to find elements in the middle
Search optimization: LinkedList is optimized to search for elements with index > (size / 2) from head, otherwise from tail: It is implemented using a double-ended LinkedList, and the Deque interface is implemented so that the LinkedList can be used as a double-ended queue. As you can see in the figure below, Node is an element in a collection that provides a precursor pointer and a successor pointer, as well as a set of methods for manipulating head and tail nodes, and features a double-endian queue.
The Set collection
The Set interface inherits from the Collection interface. It is a Set that does not contain duplicate elements. More specifically, no two elements of the Set appear o1.equals(O2), and the Set can store at most one null-valued element.
In the Set system, we need to focus on two points:
When storing mutable elements, you must be very careful, because at any time a change in the state of the elements can cause two equal elements to appear inside the Set, o1.equals(O2) = true, so don’t change the elements stored in the Set, otherwise you will break equals()!
Set’s biggest role is to judge weight, in the project’s biggest role is also to judge weight!
The underlying implementation of a HashSet is implemented using a HashMap, and we can observe its multiple constructors, which essentially new a HashMap
The underlying data structure: HashSet also uses array + linked list + red-black tree to achieve thread safety: Since HashMap is not thread safe, no additional synchronization policy has been added to the HashSet. Therefore, HashSet is not thread safe. It is best not to change the state of objects stored in a HashSet, because it is possible to change the state. The presence of two elements o1.equals(o2) inside the collection breaks the semantics of equals().
TreeSet
TreeSet is an implementation based on TreeMap, so the stored elements are ordered and the underlying data structure is array + red-black tree.
TreeSet uses the default natural sort. If you want to customize a sort, you need to pass in a Comparator.
TreeSet is introduced to its main implementation and application scenarios, with a few notable points:
All operations of TreeSet are converted to operations on TreeMap. TreeMap is implemented by red-black tree, and the average time complexity of any operation is O(logN). TreeSet is a thread-unsafe set. For example, leaderboards of player power
Map collections
The most common subclasses of the Map set are HashMap, LinkedHashMap, and TreeMap
If you’re thinking about thread safety, ConcurrentHashMap is one of the things to think about, and Hashtable is one of the things to be aware of, because interviews ask too many questions.
HashMap is also used a lot in practical development, as long as the key-value structure, we generally use HashMap. LinkedHashMap and TreeMap are not used much for the same reason as HashSet and TreeSet.
HashMap A HashMap is a collection of elements that are stored in a hash table. When an element is put into a HashMap, the hash value of the key is converted to the index subscript of the array to determine the location of the element. When a HashMap is searched, the hash address of the key is converted to the index subscript of the array to determine the location of the element.
At the bottom of HashMap, three data structures, array + linked list + red-black tree, are used to implement it. It is a non-thread-safe collection.
When sending hash collisions, a HashMap solves the problem by concatenating elements of the same mapped address into a linked list. If the list length is greater than 8 and the array length is greater than 64, it is converted into a red-black tree data structure.
A brief summary of HashMap:
It is the most commonly used Map set type in the set. The bottom layer consists of array + linked list + red-black tree. LinkedHashMap LinkedHashMap can be seen as a combination of HashMap and LinkedList: It adds a bidirectional list to the HashMap, which by default stores the insertion order of each element, but this bidirectional list allows LinkedHashMap to implement LRU cache elimination because we can set the bidirectional list to sort elements by their access order
There are two main points about LinkedHashMap:
It maintains a bidirectional linked list underneath, and since it inherits HashMap, it is not a thread-safe LinkedHashMap that implements LRU cache flushing. This works by setting accessOrder to true and rewriting the removeEldestEntry method to define the conditions that must be met to eliminate elements. TreeMap TreeMap is a subclass of SortedMap, so it has sorting functions. It is implemented based on a red-black tree data structure, where each key-value pair <key, value> is a node and is sorted naturally by key by default, or by custom rules that can be sorted by passing in a custom Comparator.
There are two main points about TreeMap:
The bottom layer of TreeMap is implemented by red-black tree data structure, so the operation time complexity is always O(logN) TreeMap can carry out natural sort or custom sort on keys, and the custom sort needs to pass in the Comparator. While natural ordering requires that the Key implements the Comparable interface, TreeMap is not thread-safe.
When you think about thread-safe collection classes, of course, that’s when you’re not thread-safe. So when are threads unsafe? Most commonly, the object being operated on is stateful
While we hear a lot about thread insecurity, there are very few places in business development where we programmers have to deal with thread insecurity. For example: Have you ever added a SYN /lock lock when writing servlets? I don’t think so?
Because the objects we operate on tend to be stateless. Without shared variables being accessed by multiple threads, there are naturally no thread-safety issues.
SpringMVC is a singleton, but SpringMVC operates on data within a method. Each thread that enters a method generates stack frames, and each stack frame’s data is thread specific. If you don’t set shared variables, there is no thread safety issue.
The above is just a brief example of SpringMVC (just to get a better understanding);
In a word: consider using thread-safe collection classes whenever multiple threads are involved with a shared variable.
More details will come when I write a summary of Java multithreading
In the end, this article has some flavor of point and stop for each set. The purpose of this article is to have a more comprehensive understanding of the whole set framework and analyze the related characteristics of the most commonly used sets.
In this paper, the whole system of collection of all common collections are analyzed, there is no set for the realization of the internal, I want to let everybody know from the perspective of the macro each set of the function, application scenarios, and a simple comparison, will take time for a common set of source code, and look forward to, thank you for reading!
If you want to go to the interview, Java set is certainly not, must ask a knowledge point, you learned is to send points.