Java collection: summary of the four systems of Set, List, Queue, and Map

Java collections are roughly divided into four systems: Set, List, Queue, and Map

Set represents an unordered, non-repeatable collection; List represents an ordered, repeating collection; Map represents a mapping A collection of relationships; Queue is the implementation of a queue.

Collections are different from arrays. Array elements can be either basic type values ​​or objects (actually, the reference variables of objects are saved). Collections can only store objects (actually only objects are saved. reference variable).

There are two derived interfaces in Java collections: Collection and Map
Inheritance tree of Collection collection system:

Inheritance tree of the Map collection system:

The following describes the
Set collection:
Set collection is similar to a jar, program You can "throw" multiple objects into it in sequence. Set will not remember the order in which elements are added, and Set collections do not allow the same elements.

HashSet:
Features:
The order of elements is not guaranteed
HashSet is not synchronized
The set element value can be null
The standard for HashSet to judge the equality of two elements is: The two objects are compared equal through the equals() method, and the return values ​​of the hashcode() method of the two objects are also equal.
Note: When putting an object into a HashSet, if you need to override the equals() method of the object, you should override its hashCode() method. The rule is: if two objects are compared and return true through the equals() method, the hashCode values ​​of the two objects should be the same.

LinkedSet:
LinkedSet determines the storage location of elements based on the original hashCode value, but it also uses a linked list to maintain the order of elements, so that the elements The order of insertion is preserved. LinkedSet accesses the elements in the set in the order in which they are added.
LinkedSet needs to maintain the insertion position of elements, so the performance will be slightly lower than that of HashSet.

TreeSet:
TreeSet ensures that the collection elements are in a sorted state.
TreeSet is not sorted according to the insertion order of the elements, but according to the actual value of the elements.
TreeSet uses the red-black tree data structure to store set elements.
TreeSet supports two sorting methods: natural sorting and customized sorting. By default, TreeSet uses natural ordering.

Natural sorting: TreeSet will call the compareTo (Object obj) method of the collection elements to compare the size relationship between the elements, and then arrange the collection elements in ascending order. By default, TreeSet uses natural ordering.
When an object is added to the TreeSet collection, TreeSet calls the compareTo (Object obj) method of the object to compare the size with other objects in the container, and then finds its storage location according to the red-black tree structure.
The only criterion for judging whether two objects are equal is: Whether two objects return 0 through the compareTo (Object obj) method.
If two objects are compared and return true through the equals() method, the comparison of the two objects through the compareTo (Object obj) method should return 0.

Customized sorting: If you need to implement customized sorting, you need to provide a Comparator object associated with the TreeSet collection when you create the TreeSet collection object. The Comparator object is responsible for the sorting logic of the collection elements.

EnumSet:
The set elements of EnumSet are also ordered. EnumSet determines the order of set elements based on the positioning order of the enumeration values ​​within the Enum class.
EnumSet is internally stored in the form of a bit vector.
The EnumSet collection does not allow adding null elements.

Performance analysis of each Set implementation class:
The performance of HashSet is always better than TreeSet, because TreeSet requires additional red-black tree algorithm to maintain the order of the set.
LinkedSet For ordinary insertion and deletion operations, LinkedSet is slightly slower than HashSet. This is caused by the additional overhead caused by maintaining the linked list. But because of the linked list, traversing the LinkedSet is faster.
EnumSet has the best performance, but it can only save enumeration values ​​of the same enumeration class as set elements.

List:
List represents an ordered, repeatable combination of elements. Each element in the collection has a corresponding sequential index.
The List collection can access the elements in the collection based on the position index, so the List can be traversed using a for loop.

ArrayList, LinkedList and Vector
ArrayList source code analysis:
LinkedList source code analysis:

Queue:
Queue is used It is used to simulate the data structure of queue.
PriorityQueue:
The order in which the queue elements are saved by PriorityQueue is not in the order of joining, but in accordance with the size of the queue elements.
PriorityQueue does not allow the insertion of null elements.

Deque:
The Deque interface is a sub-interface of the Queue interface, which represents a double-ended queue.
When a data structure like "stack" needs to be used in the program, it is recommended to use ArrayDeque.

Performance analysis of various linear tables:
1. If you need to traverse List collection elements, for ArrayList and Vector collections, you should use the random access method (get) to traverse the collection elements, so that the performance Better; for LinkedList collections you should use an Iterator to traverse the collection elements.
2. If you need to perform insertion and deletion frequently, LinkedList should be used.
3. If multiple threads access elements in the List collection at the same time, Collections should be used to wrap the collection into a thread-safe collection.

Map:
Map keys are not allowed to be repeated, that is, any two keys of the same Map object will always return false when compared with the equals method.
There is a keySet() method in Map, which is used to return a Set composed of all keys in the Map.

HashMap, Hashtable:
The difference between HashMap and Hashtable:
1.Hashtable is a thread-safe Map, HashMap is non-thread-safe, so HashMap has better performance .
2.Hashtable does not allow the use of null as key and value, and HashMap allows the use of null as key or value.

The criterion for judging the equality of two keys in Hashtable and HashMap is: the equals() method of the two keys returns true, and the HashCode values ​​of the two keys are the same; the criterion for judging the equality of two values ​​is the equals() of the value ) method returns the same value.

LinkedMap:
LinkedMap will remember the order in which key-value is added.

TreeMap:
TreeMap also uses a red-black tree structure. The standard for judging the equality of two keys in TreeMap is:
Two keys pass the compareTo() method The return value is 0. (Under natural sorting)
The return value of the two keys through the compareTo() method is 0. At the same time, the equals() method returns true. (Under custom sorting).

EnumMap:
EnumMap is internally saved in the form of an array.
EnumMap does not allow null as key, but allows value to be null.

Map performance analysis:
The performance of HashMap is better than that of Hashtable.
The key-value pairs in TreeMap are always in an ordered state, and no special sorting operation is required.
For general application scenarios, consider using HashMap.
LinkedMap is slower than HashMap because it needs to maintain a linked list to maintain the order of key-value addition.
EnumMap has the best performance, but it can only use enumeration values ​​of the same enumeration class as keys.

Related recommendations:

Traversal methods of Java collection Set, List, Map

A piece of code to understand about Java Use of List, Set and Map

The above is the detailed content of Java collection: summary of the four systems of Set, List, Queue, and Map. For more information, please follow other related articles on the PHP Chinese website!