HashMap is the most commonly used collection class framework in Java and a very typical data structure in the Java language.
(indicates contrast)HashSetcap (a poem)HashMapwhich has the same implementation in Java, the former is just a layer of wrapping for the latter, that is, theHashSetThere's one inside.HashMap(adapter pattern). Therefore, it is important to understand theHashMap source code will also understand the HashSet
present (sb for a job etc)
-
The Key is stored based on a hash table
-
HashMap is the most frequently used implementation of the Map interface.
-
Null keys and null values are allowed, and like HashSet, the order of the mapping is not guaranteed.
-
The set consisting of all keys is unordered and uniquely irreducible. Therefore, the class of the key should be rewritten: equals() and hashCode().
-
The collection of all values is a Collection: unordered and repeatable. So, the class where the values are located has to be rewritten: equals()
-
A key-value constitutes an entry.
-
The set consisting of all entries is a Set: unordered, irreducible
-
The criterion for HashMap to determine the equality of two keys is that the two keys return true by equals() method, and the hashCode values are also equal.
-
The criterion for a HashMap to determine the equality of two values is that the two values return true by the equals() method.
Introduction to the underlying principles
Underlying data structures and initial properties
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // Default initial capacity of HashMap, 16
static final int MAXIMUM_CAPACITY = 1 << 30; // HashMap's maximum supported capacity, 2^30
static final float DEFAULT_LOAD_FACTOR = 0.75f;//HashMap's default load factor
static final int TREEIFY_THRESHOLD = 8;//The length of the linked table in the Bucket is greater than the default value, it will be converted into a red-black tree.
static final int UNTREEIFY_THRESHOLD = 6;//The Node stored in the red-black tree in the Bucket is smaller than the default value, it is converted into a chained table.
/**
* Minimum hash table capacity when Node in Bucket is treed.
* (When the number of Nodes in the bucket is large enough to warrant turning into a red-black tree.
* If the hash table capacity is less than MIN_TREIFY_CAPACITY.
* this MIN_TREEIFY_CAPACITY is at least 4 times the value of TREEIFY_THRESHOLD.)
*/
static final int MIN_TREEIFY_CAPACITY = 64;
// Store the elements in an array, always the nth power of 2
// Stored by array, the elements of the array are specific Node<K,V>, this Node may form a red-black tree, may be a chain table
transient Node<K,V>[] table.
// Set storing specific elements
transient Set<<K,V>> > entrySet;
// the number of key-value pairs stored in the HashMap
transient int size.
// threshold value for expansion, = capacity * loading factor
int threshold;
//The load factor for the hash table.
final float loadFactor; //The load factor for the hash table.
Why is the default load factor 0.75? The official answer is as follows:
As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but increase the lookup cost (reflected in most of the operations of the HashMap class, including get and put). The expected number of entries in the map and its load factor should be taken into account when setting its initial capacity, so as to minimize the number of rehash operations. If the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur.
The above simply means that the default load factor of 0.75 is because it provides a good balance between space and time complexity. A load factor of 0.75 provides a good balance between space and time complexity, as too low a load factor results in a lot of empty buckets wasting space, and too high a load factor results in a lot of collisions and reduced performance. That said, there is no official explanation for a load factor of 0.75, it is just a general statement that 0.75 is a balance between space and time complexity, but more details are not explained, and the load factor of 0.75 is used as a proxy for the load factor.Scientific speculation on load factorsIf you're interested, you can learn about it.
constructor method
//empty reference construction (math.)，Initialize loading factors
public HashMap() {
= DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
//parametric construction (math.)，Initial capacity size and loading factor can be initialized
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || (loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
= loadFactor;
= tableSizeFor(initialCapacity);//Thresholds for capacity expansion，= quantitative (science)*loading factor
}
put method
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
First compute the hash value of the key, then put on it
static final int hash(Object key) {
int h.
//Why shift right by 16 bits? The default length is 2^5=16, and it's easy to get the same value with hash value & operations.
return (key == null) ? 0 : (h = ()) ^ (h > > > 16);
}
Here it is divided into three steps:
- h=() //first step Fetch hashCode value
- h^(h>>>16) // Step 2 Higher level participates in arithmetic to reduce conflicts, hash is calculated here
- return h&(length-1); //third step modulo operation, calculate the position of the data in the bucket, here see the source code later
Step 3 (n-1)& hash principle:
-
Actually (n-1) & hash equals hash%n both get the position of the element in the bucket, but the (n-1)& hash operation is faster.
-
The remainder operation can be optimized as a shift operation if the divisor is an integer power of 2. This is why the expansion must be must be 2 to the nth power of 2
Bitwise operations (&) are much more efficient than substituting modulo operations (%), mainly because bitwise operations operate directly on memory data without converting it to decimal, so processing is very fast.
And the calculation of hash is achieved by using both the high 16 bits of hashCode() iso and the low 16 bits (h > > > > 16): doing so can be in the array is relatively small, but also ensures that taking into account the high and low bits are involved in the calculation of the Hash, you can reduce the conflict, at the same time, will not have too much overhead.
hash value is actually an int type, the binary bits for the 32-bit, and HashMap table array initialization size of 16, take the balance of the operation for hashCode & 15 ==> hashCode & 1111. This will have a huge problem, 1111 will only be with the lower four bits of the hashCode and operation, that is, the high bit of the hashCode is not actually involved in the operation, will lead to a lot of hash value and the high bit of the number of different, the final index are the same. For example, assuming that the hashCode for 1111110001, then 1111110001 & 1111 = 0001, if some key hash value of the low and the former is the same, but the high position has changed, such as 1011110001 & 1111 = 0001, 1001110001 & 1111 = 0001, it is clear that after the change in the high position, the index of the final calculation is still the same, which will lead to a lot of data have been put into an array, resulting in performance degradation. In order to avoid this situation, HashMap will be the high 16-bit and low 16-bit iso, which ensures that the data in the high position is also involved with the operation to increase the degree of hashing of the index, so that the data is distributed more evenly (personally, I think it is for the purpose of uniform distribution)
The put process is as follows:
// The fourth argument, onlyIfAbsent, if true, will only put if the key does not exist.
// The fifth parameter, evict, is not of interest to us here.
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { boolean onlyIfAbsent is true.
V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i.
if ((tab = table) == null || (n = ) == 0)// initial judgment, when initial array is empty
// resize() initial array, need to expand operation
n = (tab = resize()).length;
// here is the third step above, according to the key hash value to find the data in the table position
if ((p = tab[i = (n - 1) & hash]) == null)
//The subscript of the array found by hash, there is no content in it, it is directly assigned a value
tab[i] = newNode(hash, key, value, null);
else {//If there is already content in it
Node<K,V> e; K k.
if ( == hash & &
// The hash is the same and the key is the same, so we'll just modify the value directly
((k = ) == key || (key ! = null && (k))))
e = p;
else if (p instanceof TreeNode)
// key is not the same and the node is a red-black tree, then put the node into the red-black tree
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// Indicate that the node is a chained table
for (int binCount = 0; ; ++binCount) {
if ((e = ) == null) {
// Add to the end of the chain table
= newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// If the conditions for converting a linked table to a red-black tree are met, then convert to a red-black tree
treeifyBin(tab, hash);
break.
}
if ( == hash &&.
((k = ) == key || (key ! = null && (k))))
break;
p = e; }
}
}
// The passed-in k element already exists, directly overwrite the value
if (e ! = null) { // existing mapping for key
V oldValue = ;
if (!onlyIfAbsent || oldValue == null)
= value; afterNodeAccess(e)
afterNodeAccess(e); return oldValue; return oldValue.
return oldValue; }
}
}
++modCount.
if (++size > threshold)//check if the number of elements is greater than the threshold, expand if greater
resize();
afterNodeInsertion(evict);
return null; }
}
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// Check if the conditions for converting to a red-black tree are met, if the array size is still less than 64, then expand it first
if (tab == null || (n = ) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) ! = null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p; else { TreeNode<K,V> p = replacementTreeNode(e, null)
else {
= tl.
= p; }
}
tl = p; }
} while ((e = ) ! = null);
if ((tab[index] = hd) ! = null)
(tab);
}
}
Summarize the put methodology process:
-
If the table is not initialized the initialization process is performed first
-
Use the hash algorithm to calculate the index of the key to determine whether there is an element at the index, if not, insert it directly.
-
If an element exists at the index, the traversal inserts, in two cases, the
-
One form of chained table is directly traversed to the end of the insertion.
-
A red-black tree follows the red-black tree structure.
-
-
If the number of insertions is greater than the threshold of 8 and the size of the array is already greater than or equal to 64, the structure should be converted to a red-black tree.
-
After adding successfully, it will check whether it needs to be expanded or not
Array expansion
//Expansion operations for table arrays
final Node<K,V>[] resize() {
//References to the node array before resizing.
Node<K,V>[] oldTab = table;
// old capacity
int oldCap = (oldTab == null) ? 0 : ;
// old threshold
int oldThr = threshold;
//new capacity, threshold initialized to 0
int newCap, newThr = 0; //new capacity, threshold initialized to 0; //new capacity, threshold initialized to 0
// Calculate the new capacity
if (oldCap > 0) {
//If the old capacity has exceeded the maximum capacity, make the threshold equal to the maximum capacity as well, and do not expand the capacity in the future
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE; return oldTab; return oldTab; return oldTab
return oldTab.
}
// If the maximum value is not exceeded, make newcap double its original capacity.
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY))
// If the doubling of the old capacity does not exceed the maximum value, and the old capacity is not less than the initialized capacity of 16, then double it
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
// old capacity oldCap = 0, but old threshold is greater than 0, so initial capacity was placed in threshold
newCap = oldThr.
else { // zero initial threshold signifies using defaults
// both values are 0, initialize using defaults
newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
// Calculate the new threshold, if the new capacity or the new threshold is greater than or equal to the maximum capacity, then the maximum value is directly used as the threshold and no further expansion is done
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// Set the new threshold
threshold = newThr;
//create a new array with the reference
@SuppressWarnings({"rawtypes", "unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
//If the old array has data, i.e., it is expanded and not initialized, then execute the following code, otherwise the initialization can end here
if (oldTab ! = null) {
// Poll the old array for all data
for (int j = 0; j < oldCap; ++j) {
// Reference the current node with a new node, then release the reference to the original node
Node<K,V> e.
if ((e = oldTab[j]) ! = null) {// If this bucket, is not empty, it means there is data in the bucket
oldTab[j] = null;
//If e does not have a next node, it proves that there is no hash conflict on this node, then the reference to e is directly given to the new array position
if ( == null)
// Determine the position of the element in the new array
newTab[ & (newCap - 1)] = e.
//Split if it is a red-black tree
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// Indicate that it's a chained table.
else { // preserve order
Node<K,V> loHead = null, loTail = null; // show that it's a chained table.
Node<K,V> hiHead = null, hiTail = null; // preserves order
Node<K,V> next;
// Start polling from the first element on this chain, if the bit added to the current element is 0, then put it on the current chain.
//If it is 1, put it at "j+oldcap" to generate two linked lists, "low" and "high".
do {
next = ;
if (( & oldCap) == 0) {
if (loTail == null)
loHead = e; else
else
// Elements are continually added to the tail
= e;
//Added elements are always tail elements
loTail = e;
}
else {
//Higher chained lists are handled with the same logic as lower chained lists, elements are constantly added to the tail of the chained list
if (hiTail == null)
hiHead = e; } else {
if (hiTail == null) hiHead = e; else
= e; else
hiTail = e; else = e.
}
} while ((e = next) ! = null);
// Lowers the linked list to the position at index j
if (loTail ! = null) {
= null;
newTab[j] = loHead;
}
// The high level chain table is placed at the position of the index (j+oldCap)
if (hiTail ! = null) {
= null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab; }
}
Obviously, the HashMap expansion mechanism, is when the expansion conditions will be expanded. Expansion conditions is when the number of elements in the HashMap more than a threshold value will automatically expand (threshold = loadFactor * capacity). If it is the initialization of the expansion, only the first half of the resize code, but if it is with the increase of elements and expansion, HashMap needs to recalculate the position of each value in the oldTab, that is, rebuild the hash table, with the increasing number of elements, HashMap will be expanded many times, which will be very much affected by the performance. Therefore, it is generally recommended to specify the initialization capacity when creating a HashMap.
But when using HashMap (int initialCapacity) to initialize the capacity, HashMap will not use the initialCapacity passed in directly as the initial capacity.JDK will default to calculate a relatively reasonable value as the initial capacity. The so-called reasonable value, in fact, is to find the first larger than the value passed in by the user.the power of 2. That is, when new HashMap(7) creates a HashMap, JDK will create a Map with a capacity of 8 by calculation; when new HashMap(9) creates a HashMap, JDK will create a Map with a capacity of 16 by calculation. of course, when creating aHashMapThe size of the table is not allocated immediately, but at the first put element, and the allocated size will be the smallest power of 2 greater than or equal to the initial capacity.
In general, initialCapacity = (number of elements to be stored / loaderfactor) + 1. Note that the loaderfactor (i.e., loaderfactor) defaults to 0.75, and if you can't determine the initial size for the time being, please set it to 16 (i.e., the default value). 1024 elements need to be placed in the hash map, and since the initial size of the capacity has not been set, it will be forced to expand continuously as more elements are added. HashMap needs to place 1024 elements, since there is no initial size, as the number of elements increases, it is forced to continuously expand the capacity, and the resize() method will be called a total of 8 times to repeatedly rebuild the hash table and migrate the data. When the number of elements placed in the collection reaches ten million, it will affect the performance of the program.
//Initialization Capacity
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity, float loadFactor) {
//assurancesinitialCapacityWithin reason，more than0Less than maximum capacity
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || (loadFactor))
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
= loadFactor;
= tableSizeFor(initialCapacity);
}
static final int tableSizeFor(int cap) {
int n = cap - 1;
//|=calculation method：Both binary counterparts are0hour,The result is equal to0,否则The result is equal to1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
/**
* Red-black tree splitting method
*/
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
// the current reference to this node, the root node of the tree at this index
TreeNode<K,V> b = this;
// Relink into lo and hi lists, preserving order
TreeNode<K,V> loHead = null, loTail = null; // Relink into lo and hi lists, preserving order.
TreeNode<K,V> hiHead = null, hiTail = null; // Initialize high and low lists.
// The initial number of tree nodes for both high and low is set to 0
int lc = 0, hc = 0; // initial number of tree nodes is set to 0 for both high and low.
for (TreeNode<K,V> e = b, next; e ! = null; e = next) {
next = (TreeNode<K,V>); next = b, e !
= null;
//bit=oldcap, here to determine whether the new bit is 0 or 1, if it is 0 it is placed in the low tree, if it is 1 it is placed in the high tree, here is first a two-way linked table
if (( & bit) == 0) {
if (( = loTail) == null)
loHead = e;
else
= e; loHead = e; else
loTail = e; else = e.
++lc.
else = e; else = e; loTail = e; ++lc; }
else {
if (( = hiTail) == null)
hiHead = e; } else { if (( = hiTail) == null)
else { if (( = hiTail) == null) hiHead = e; } else
= e; else
hiTail = e; else = e.
++hc.
}
}
if (loHead ! = null) {
if (lc <= UNTREEIFY_THRESHOLD)
//!!! If the length of the chained table in the low position is less than the threshold 6, turn the tree into a chained table and put it in the new array at index position j
tab[index] = (map);
else {
tab[index] = loHead;
//Higher not null, do red-black tree conversion
if (hiHead ! = null) // (else is already treeified)
(tab);
}
}
if (hiHead ! = null) {
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = (map);
else {
tab[index + bit] = hiHead; if (hc <= UNTREEIFY_THRESHOLD)
if (loHead ! = null)
(tab); }
}
}
}
/**
* Transforms a tree into a unidirectional linked table
*/
final Node<K,V> untreeify(HashMap<K,V> map) {
Node<K,V> hd = null, tl = null;
for (Node<K,V> q = this; q ! = null; q = ) {
Node<K,V> p = (q, null); if (tl == null)
if (tl == null)
hd = p; else
hd = p; else
= p; tl = p; if (tl == null)
tl = p; tl = p; if (tl == null)
}
tl = p; }
}
/**
* Converting a chained table to a red-black tree，Colors will be converted according to the characteristics of the red and black trees、levitra、dextrose
*/
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
for (TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,V>);
= = null;
if (root == null) {
= null;
= false;
root = x;
}
else {
K k = ;
int h = ;
Class<?> kc = null;
for (TreeNode<K,V> p = root;;) {
int dir, ph;
K pk = ;
if ((ph = ) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? : ) == null) {
= xp;
if (dir <= 0)
= x;
else
= x;
//进行levitra、right-hand side adjustment
root = balanceInsertion(root, x);
break;
}
}
}
}
moveRootToFront(tab, root);
}
Summarize the HashMap implementation:
- The internal storage structure of HashMap is actually a combination of an array, a linked list and a red-black tree. When a HashMap is instantiated, initialCapacity and loadFactor will be initialized, and at this time, no array will be created.
- In put the first pair of mapping relationships, the system will create a length of initialCapacity (default is 16) of the Node array, this length in the hash table is called capacity (Capacity), in this array can be stored in the location of the elements we call "bucket" ( bucket), each bucket has its own index, the system can quickly find the elements in the bucket according to the index.
- Each bucket stores one element, a Node object, but each Node object can carry a reference variable next, which is used to point to the next element, so it is possible to generate a chain of Nodes in a bucket. It may also be one one TreeNode object, and each TreeNode object can have two leaf nodes left and right, therefore, in a bucket, it is possible to generate a TreeNode tree. And the newly added element serves as the last of the chain list, or the leaf node of the tree
Summarize the expansion and treeing of HashMap:
- When the number of elements in the HashMap exceeds the size of the array (the total size of the array length, not the number of arrays in the size)*loadFactor, the array will be expanded, loadFactor's default value (DEFAULT_LOAD_FACTOR) is 0.75, which is a compromise value. That is, by default, the array size (DEFAULT_INITIAL_CAPACITY) is 16, so when the number of elements in the HashMap exceeds 16, the array will be expanded.When 0.75 = 12 (this value is the threshold value in the code), the size of the array is expanded to 216 = 32, that is, doubled, and then recalculate the position of each element in the array, and this is a very performance-consuming operation, so if we have predicted the number of elements in the HashMap, then the number of pre-determined elements can effectively improve the performance of the HashMap
- When one of the chain of HashMap if the number of objects reached 8, at this time, if the capacity does not reach 64, then HashMap will be expanded first to solve, if it has reached 64, then the chain will become a tree, the node type from Node into TreeNode type. Of course, if when the mapping relationship is removed, the next resize method to determine the number of nodes of the tree is less than 6, the tree will also be converted to a chain list.
That is, when the array of an index position on the elements in the form of a linked list of data in the form of the number of >8 and the length of the current array >64, at this time the index position of all the data is changed to use the red-black tree storage
get method
public V get(Object key) {
Node<K,V> e.
return (e = getNode(hash(key), key)) == null ? null : ;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) ! = null && (n = ) >0 &&
(first = tab[(n - 1) & hash]) ! = null) {
//1. Determine if the first element matches the key
if ( == hash &&
((k = ) == key || (key ! = null && (k))))
return first;
if ((e = ) ! = null) {
//2. Determine if a chained table is a red-black tree structure.
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
//If it is not a red-black tree structure, directly loop judgment
do {
if ( == hash &&
((k = ) == key || (key ! = null && (k))))
return e; } while ((e = ) !
} while ((e = ) ! = null);
}
}
return null; }
}
/**} null
* The situation here is divided into many, mainly because of the consideration of the hash is the same but the key value of the different cases, find the most core or fall on the key value
*/The core of the lookup is still on the key value.
final TreeNode<K,V> find(int h, Object k, Class<? > kc) {
TreeNode<K,V> p = this.
do {
int ph, dir; K pk;
TreeNode<K,V> pl = , pr = , q;
// Determine if the hash of the element to be queried is on the left side of the tree
if ((ph = ) > h)
p = pl;
// determine if the hash of the element to be queried is on the right side of the tree
else if (ph < h)
p = pr;
// query element hash and the current tree node hash the same case
else if ((pk = ) == k || (k ! = null && (pk))))
return p.
//The above three steps are the normal way to find an object in a binary lookup tree.
//If the hashes are equal, but the contents are not
else if (pl == null)
p = pr.
else if (pr == null)
p = pl;
// Compare based on compareTo if possible
else if ((kc ! = null || if (kc = comparableClass)
(kc = comparableClassFor(k)) ! = null) & &
(dir = compareComparables(kc, k, pk)) ! = 0)
p = (dir < 0) ? pl : pr;
// Continue querying on the right child based on the result of compareTo
else if ((q = (h, k, kc)) ! = null)
return q.
// continue querying on the left child based on the result of compareTo
else
p = pl; } while (p !
} while (p ! = null); }
return null; }
}
Summarize the get method:
- First get the corresponding array subscripts through the hash() function, and then judge them in turn.
- Determines whether the first element matches the key, and returns the parameter value if it does;
- Determines if the linked table is a red-black tree, and if it is, enters the red-black tree method to get the parameter values;
- If it is not a red-black tree structure, directly loop traversing the chain table to determine until the parameter is obtained;
remove method
The deletion logic of jdk1.8 is more complex to implement, with red-black tree node deletion and adjustment when deleting:
- Defaults to determining whether the first element of a linked table is the element to be deleted;
- If the first one is not, it continues to determine whether the current conflict chain table is a red-black tree, and if it is, it goes inside the red-black tree to find it;
- If the current conflict linking table is not a red-black tree, it is straightforward to loop through the linking table until it is found;
- The nodes that are found, are removed, and if it is a red-black tree structure, it will be adjusted for color conversion, left-handedness, and right-handedness until it satisfies the red-black tree characteristics;
HashSet
-
Set can not store duplicate elements, unordered, allowing a null (based on HashMap implementation, HashMap key can be null);
-
Set based on the Map implementation, the value of the elements in the Set is the key value of the Map.
HashSet based on HashMap implementation. Elements put into the HashSet by the HashMap key to save the HashMap value is stored in a static Object object.
underlying source code
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, {
static final long serialVersionUID = -5024744406713321676L;
private transient HashMap<E,Object> map; //on the basis ofHashMaprealization
//...
}
About the Author.
From the first-line programmer Seven's exploration and practice, continuous learning iteration in the~
This article is included in my personal blog:https://
Public number: seven97, welcome to follow~