Table of Contents

  • Colletion, Iterator, Comparable
  • List
  • Map
  • CHM
  • Set
  • Linkedhashmap
  • The Collections and Arrays utility classes
  • Comparable and comparator
  • Treemap and treeset

This summary is based on a compilation and review of previous blog content.

The following summary is not guaranteed to be correct. If there are any mistakes, please point them out. thank you

Colletion, Iterator, Comparable

Collection is generally thought of as the top-level interface, but HashMap actually implements the Map interface. Iterator is an iterator that A class that implements the Iterable interface must provide. Types that can be implemented using for(I: A) provide iterators that used to be enumerations, but are now deprecated.

List

List interface implementation classes include ArrayList, LinkedList, vector, etc. ArrayList’s capacity expansion method is 1.5 times that of ArrayList, which is a compromise solution to avoid space waste caused by 2 times expansion. Additionally, it is not thread-safe. Vector is thread-safe, and it is double scaled.

Linkedlist is nothing to write home about, mostly used to implement linked lists.

Map

Map is always the big story.

A hashmap is a combination structure of an array and a linked list. An array is an Entry array, and the Entry is a K-V key-value pair type. Therefore, an Entry array holds many Entry nodes. Finally, the hash operation is performed with the table length -1, which is the last n-1 bit of the hash value. N indicates that the table length is 2 to the n power.

The default load factor for hashMap is 0.75 and the threshold is 16 * 0.75 = 12; The initial length is 16;

The add, delete, change and search methods of hashMap are relatively simple, which are traversal and replacement. One thing to note is that if keys are equal, replace elements, and if keys are not equal, join lists.

In addition, the 1.8 JDK improved the HashMap, which automatically converts to a red-black tree and nodes to tree nodes when the number of linked list elements exceeds 8, to improve search efficiency and insert efficiency to logn.

Another point worth mentioning is the capacity expansion operation of Hashmap. Since Hashmap is not thread-safe, if multiple threads operate concurrently during capacity expansion, two threads may operate the new table and the old table respectively, resulting in node ring and deadlock in query. CHM avoids this problem.

In addition, the old table elements will be moved to the new table when the original version is moved, and every node will have to be rehash, which is very inconvenient. However, 1.8 is changed to another way. For linked list elements under the same index, there are only two cases of the hash value of an element after expansion, either the hash value remains unchanged. It’s either going to be the hash value plus 2 to the NTH power, because the table is twice as long, so if you take the last n bits of the hash value, the first digit is either 0 or 1, so there’s only two ways to hash. The elements in both cases are added to two different lists. These two lists just need to be placed in two different places in the new list. Isn’t that cool?

In addition, hashmap.1.8 uses tail insertions and head insertions to ensure the same order. In addition, hashmap.1.8 uses head insertions to ensure the same order.

CHM

Chm1.7 uses segmentlock to control concurrency. Each segment corresponds to a Segmentmask. The segment location is obtained by matching the hash value of the key with the segmentmask. Then find the subscript of the specific entry array. So CHM needs to maintain multiple segments, each of which corresponds to an array. Segmented locking uses the ReetreetLock reentrant lock implementation. Query without locking.

1.8 Abandon the piecewise lock and use CAS +synchronized to realize concurrency control. No lock is added during query. If there is no conflict during insertion, cas will be directly inserted until it succeeds, and synchronized will be used if there is conflict.

Set

A set is a hashmap that binds a value to an object and wraps the key element into an entry.

Linkedhashmap

Add all nodes to a linked list based on the original HashMap in the order in which they were inserted. To preserve order, you can use it to implement an LRU cache that moves nodes to the head of the queue when an access hit occurs, and removes elements at the end of the queue when inserted elements exceed their length.

The Collections and Arrays utility classes

The two utility classes work with collections and arrays, and can do common sorting, merging, and so on.

Comparable and comparator

Implement the Comparable interface to allow instances of a class to compare sizes to each other using the compareTo method. You can customize the comparison rules. The Comparator is a generic comparator that compares the size relationships between two elements of a specified type.

Treemap and treeset

It is mainly two data structures based on red-black tree, which can ensure that the key sequence is orderly, and the key values can be printed sequentially by obtaining sortedset. It involves the insertion and deletion of red-black trees, adjustment and other operations, which are more complicated, so I won’t go into details here.