Java collection framework study notes

The java collection class can be used to store multiple objects of varying numbers, and can implement common data structures such as stacks, queues, etc. Unlike arrays, the length of arrays is immutable. Array elements can store basic types and object types, while collections can only store objects (essentially object referencesvariables), Java Sets can be roughly divided into Set, List, and Map, where Set represents an unordered, non-repeatable collection, and List represents an ordered, repeatable collection. , Map represents a collection with a mapping relationship, the key is unique in the map, and the value is repeatable. Among them, Set, List and the Queue queue newly added after java5 are subclasses derived from CollectionInterface

Set collection is not allowed to contain the same elements, and there is no obvious order between objects in the collection

HashSet, LinkedHashSet, and TreeSet are the main implementation classes of Set

HashSet cannot guarantee the order of elements, HashSet is not synchronized, and HashSet set elements are allowed to be null, When an object is stored in a HashSet, the HashSet will call the hashCode method of the object to obtain the hashCode value of the object, and determine the storage location of the object in the HashSet based on the hashCode value. In HashSet, whether two objects are equal is judged by comparing the return values ​​​​of the equals() and hashCode() methods.
LinkedHashSet is a subclass of HashSet, but it also uses a linked list to maintain the order of elements, so that The elements seem to be saved in the order of insertion. Because it needs to maintain the insertion order of the elements, the performance is slightly lower than that of HashSet. Since it is still a HashSet, the same element cannot be repeated

TreeSet

TreeSet is the implementation class of the SortedSet interface. Similarly, TreeSet can ensure that the collection elements are in the sorted state. TreeSet will call the comparTo (Object obj) method of the collection elements to compare the size relationship between the elements, and then set the collection The elements are arranged in ascending order, that is, natural sorting. TreeSet can also implement customized sorting through the Comparator interface. When creating a TreeSet collection object, a Comparator object is provided to be associated with the TreeSet collection, and the Comparator object is responsible for the sorting logic of the collection elements.

Comparison of various Set performance

The performance of HashSet is always better than TreeSet, because TreeSet requires additional algorithms to maintain the order of set elements. TreeSet should only be used when a sorted set needs to be maintained. Otherwise, HashSet should be used. In addition, LinkedHashSet is a subclass of HashSet, corresponding to ordinary insertion and delete operations. The performance of LinkedHashSet is slightly slower than that of HashSet. This is due to the overhead caused by maintaining the linked list, but because of the linked list , it will be faster when traversing LinkedHashSet. However, none of the three implementation classes of set are thread-safe. You can usually use the synchronizedSortedSet method of the Collections tool class to wrap the set collection. This operation is best performed at creation time. For example: SortedSet s = Collections.synchronizedSortedSet(
new TreeSet(...));<a href="http://www.php.cn/wiki/165.html" target="_blank"></a><h4>List collection represents an ordered and repeatable collection. The elements in the collection have their corresponding <a href="http://www.php.cn/code/229.html" target="_blank">indexes</a> </h4> <h5> <a href="http://www.php.cn/wiki/1041.html" target="_blank">Array</a>List and Vector are Lists Two typical implementations, and a Linke<a href="http://www.php.cn/wiki/596.html" target="_blank">dL</a>ist</h5> <p> where the ArrayList and Vector classes encapsulate a dynamic Object[] array that allows reallocation, when the number of elements is added When the array length is exceeded, the initial length is automatically increased. The significant difference between ArrayList and Vector is that ArrayList is not thread-safe, while Vector is thread-safe and does not require a program to ensure the synchronization of the collection. Because Vector is thread-safe, Vector color performance is lower than ArrayList. Even if thread safety needs to be ensured, it is generally not recommended to use Vector. Instead, use the relevant methods of the Collections tool class to wrap the ArrayList into a thread-safe class. <br>Vector also has a subclass called Stack, which is used to simulate the data structure of a stack. Last in, first out. Since it is an <a href="http://www.php.cn/code/6064.html" target="_blank"> inheritance </a> relationship, Stack is also thread-safe, so its performance is relatively poor. It is recommended. If you need to use a data structure such as a stack, you can consider using LinkedList.<br>LinkedList is also an implementation class of List. It is a List based on linked list implementation. It is optimized for sequential access to elements in the collection, especially insertion. It is very fast to delete elements. LinkedList implements both the List interface and the Deque interface. Because it implements the Deque interface, it can be used as a stack. The Queue collection is used to simulate the data structure of a queue, first in, last out. Deque is a sub-interface of Queue, representing a double-ended queue, allowing elements of the queue to be manipulated from both ends. </p> <h5 id="The-difference-between-LinkedList-and-ArrayList">The difference between LinkedList and ArrayList</h5> <p>Since ArrayList stores the elements in the collection internally in the form of an array, it has better performance when randomly accessing collection elements, while LinkedList uses a linked list. It is used to save the elements of the collection, so the random access performance is poor, but the performance when inserting and deleting elements is very good. </p> <h4 id="Map-is-used-to-save-data-with-mapping-relationships-Both-key-and-value-can-be-any-reference-type-of-data-but-the-key-value-of-the-map-is-unique-and-cannot-be-repeated">Map is used to save data with mapping relationships. Both key and value can be any reference type of data, but the key value of the map is unique and cannot be repeated. </h4> <h5 id="HashMap-and-Hashtable-are-Maps-Two-implementation-classes">HashMap and Hashtable are Maps Two implementation classes </h5> <p>Hashtable is a thread-safe Map implementation class, but HashMap is not thread-safe, so the performance of HashMap is slightly better. <br> In addition, Hashtable does not allow the use of null as key and value. Trying to put null into Hashtable will cause a null pointer exception, but HashMap can use null as key and value. Since keys cannot be repeated, HashMap has at most one key that is null. But there can be multiple values ​​that are null. <br>The standard for HashMap and Hashtable to judge whether two keys are equal is that the return values ​​​​of the two keys through the equals() and hashCode() methods are equal. <br>LinkedHashMap is a subclass of HashMap. LinkedHashMap also uses a doubly linked list to maintain the order of keys, that is, the iteration order is consistent with the insertion order. Because the insertion order of elements needs to be maintained, the overall performance is slightly lower than HashMap. </p> <h5 id="TreeMap">TreeMap</h5> <p>There is also a SortedMap interface under Map. The SortedMap interface is another TreeMap implementation class. When TreeMap saves key-value pairs, it needs to sort the nodes according to the key. TreeMap sorting is divided into natural sorting. And customized sorting. In natural sorting, keys must implement the Comparable interface. In scheduled sorting, a Comparator object needs to be passed in when creating a TreeMap, and this object will sort the keys in the TreeMap. Similar to TreeSet. TreeMap is slower than HashMap and Hashtable because it needs to maintain ordering. </p> <h4 id="The-difference-between-Collection-and-Collections">The difference between Collection and Collections</h4> <p>Collection is an interface of Java collection<a href="http://www.php.cn/css/css-rwd-frameworks.html" target="_blank">Framework</a><br>Collections is a tool class in the collection framework, which provides A large number of methods are provided to sort collection elements, <a href="http://www.php.cn/php/php-tp-demand.html" target="_blank">query</a>, modify and other operations. It also provides some methods for setting collection objects to be immutable and achieving synchronization control of object collections. </p>

The above is the detailed content of Java collection framework study notes. For more information, please follow other related articles on the PHP Chinese website!