1. Inheritance relationship
The difference between HashMap and Hashtable
1. The difference between:
-
The main difference is that Hashtable is thread-safe, while HashMap is not.
-
A Hashtable does not allow null keys or values, whereas a HashMap can have null keys. Hashtable directly throws nullpointer exceptions when we put null values, but HashMap does something special.
static final int hash(Object key) { int h; return (key == null)?0 : (h = key.hashCode()) ^ (h >>> 16); } Copy the codeBecause Hashtable uses a fail-safe mechanism, the data you’re reading isn’t necessarily the most recent.
If you use null, it will not be able to contain the key because it cannot contain(key) again to contain the key. The same goes for ConcurrentHashMap.
-
The implementation is different: Hashtable inherits from Dictionary classes, while HashMap inherits from AbstractMap classes.
-
The initial capacity of HashMap is 16, and that of Hashtable is 11. The default load factor of both is 0.75.
-
The capacity expansion mechanisms are different. If the existing capacity is greater than the total capacity x load factor, the HashMap capacity expansion rule is double the current capacity, and the Hashtable capacity expansion rule is double the current capacity + 1.
-
Iterators are different: The Iterator in a HashMap is fail-fast, while the Enumerator in a Hashtable is not fail-fast.
2. Fail fast and fail – safe
-
Fail — Fast is a mechanism in Java collections that throws Concurrent Modification Exceptions when iterators iterate over a collection object and the contents of the collection object are modified (added, deleted, modified) during the iteration.
-
How it works: Iterators directly access the contents of a collection during traversal and use a modCount variable during traversal.
If the contents of the collection change during traversal, the value of modCount is changed.
Whenever the iterator iterates over the next element using hashNext()/next(), it checks whether the modCount variable is the expectedmodCount value and returns the traversal if it is; Otherwise, an exception is thrown and the traversal is terminated.
-
Tip: This exception is thrown if modCount is detected! =expectedmodCount This condition. If the set changes when the modCount value is just set to the expectedmodCount value, the exception will not be thrown.
Therefore, concurrent operations cannot be programmed depending on whether or not this exception is thrown; this exception is only recommended for detecting concurrent modification bugs.
-
Usage scenario: Collection classes in the ava.util package fail quickly and cannot be modified concurrently (iteratively) in multiple threads as a safety mechanism.
-
-
Fail — safe: Containers under the java.util.concurrent package are safe failures and can be used and modified concurrently in multiple threads.
Underlying data structures and stored procedures
1.hashMap
The pre-jdk1.8 data structure is linked list + array.
After JDk1.8, linked list + array + red-black tree
1 the initialization
HashMap<String, Integer> map = new HashMap<>();
Copy the codeBefore jdK8, the constructor creates an Entry[] table of length 16 to store key-value pair data.
In JDk8, instead of creating an array underneath the constructor of a HashMap, the array Node[] table is created when the put method is first called to store key-value pair data.
2 storage
The underlying hashCode method for key combines array length with unsigned right shift (>>>), bitwise xor (^) hash value, bitwise and (&) index
static final int hash(Object key) {
int h;
return (key == null)?0 : (h = key.hashCode()) ^ (h >>> 16);
}
// Calculate the index,n is the length of the array
(n-1) & hash
// In addition, you can also use: square in Chinese, not in English
Copy the codeWhen two Hashcodes are equal, a hash collision occurs, replacing the old value if the key value is the same, or joining the end of the list, which becomes a red-black tree if its length exceeds the threshold of 8.
3 summary
1. Size indicates the real-time number of k-vs in the hashMap, not the array length. 2. Threshold = Capacity * loadFactor. This value is the maximum length currently occupied by the array. If the size exceeds this threshold, the size of the hashMap will be resized, and the capacity of the hashMap will be doubled.
4. HashMap member variables
4.1 Member Variables
1. Serialize the version number
private static final long serialVersionUID = 362498820763181265L;
Copy the code2. Set initialization capacity (must be 2 to the NTH power)
// The default initial capacity is 16. 1 << 4 equals 1*2 ^ 4
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
Copy the codeQuestion: Why does it have to be 2 to the NTH power? What if the input value is not a power of two like 10?
Efficient storage, minimizes collisions, and is more uniform when indexing (n-1) & hashes. Problem: If the incoming capacity is not a power of 2 by default
// Perform 5 or operations to change the right side of the highest binary 1 in the current number to 1, and return +1
static final int tableSizeFor(int cap) {
// the purpose of -1 is to find a target value greater than or equal to the original value
int n = cap - 1;
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;
}
Copy the code3. The default load factor is 0.75
static final float DEFAULT_LOAD_FACTOR = 0.75 f;
Copy the code4. Maximum collection capacity
static final int MAXIMUM_CAPACITY = 1 << 30; // 2 to the 30th
Copy the code5. If the list value exceeds 8, it will become a red-black tree.
// When the number of nodes on the bucket is greater than this value, it becomes a red-black tree
static final int TREEIFY_THRESHOLD = 8;
Copy the codeQ: Why does a Map bucket become a red-black tree when the number of nodes exceeds 8?
TreeNode takes up twice as much space as a normal Node. The tradeoff between space and time is that if TreeNode is 8, log (8) =3, less than the average of the linked list 8/2=4. In other words, we’re going to pick 8 because it fits the Poisson distribution, so we’re going to pick 8 because the probability of going beyond 8 is very low.
6. When the value of the list is less than 6, the list is returned from the red-black tree
// When the number of nodes on a bucket is less than this value, the tree becomes a linked list
static final int UNTREEIFY_THRESHOLD = 6;
Copy the code7. The size threshold of the array when the list is turned into a red-black tree, that is, if the array size is greater than this number, the list length is greater than 8 before it is turned into a red-black tree
// The structure is converted to the value of the smallest array length corresponding to the red-black tree
static final int MIN_TREEIFY_CAPACITY = 64;
Copy the code8. Table is used to initialize arrays
// An array of elements
transient Node<K,V>[] table;
Copy the code9. Cache (for traversal)
// Store a collection of specific elements
transient Set<Map.Entry<K,V>> entrySet;
Copy the code10. Number of elements in HashMap (key)
// The number of elements stored in the HashMap, size is the real-time number of k-v, not the length of array table.
transient int size;
Copy the code11. Record the number of changes to the HashMap
// Expand and change the map counter each time
transient int modCount;
Copy the code12. The value used to resize the next capacity is calculated as (capacity * load factor)
// Threshold When the actual capacity (capacity x load factor) exceeds the threshold, the system expands the capacity
int threshold;
Copy the code13. Load factor of hash table (emphasis)
// Load factor
final float loadFactor;
Copy the codeNote: loadFactor indicates the density of a hashMap. Impact Affects the probability of hash operations to the same array location. The default value is 0.75 and you are not recommended to change the value.
4.2 Construction Method
1. Construct an empty HashMap with default initial capacity (16) and default load factor (0.75)
// assign the default loadFactor 0.75 to loadFactor without creating an array
public HashMap(a) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
Copy the code2. Construct a HashMap with the specified initial capacity and default load factor (0.75)
// Specifies the "capacity size" constructor
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
Copy the code3. Construct a HashMap with the specified initial capacity and load factor
InitialCapacity: the specified capacity loadFactor: the specified loadFactor */
public HashMap(int initialCapacity, float loadFactor) {
// Determine whether initialCapacity is less than 0
if (initialCapacity < 0)
// If less than 0, an invalid argument exception IllegalArgumentException is thrown
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
// Determine whether initialCapacity is greater than the maximum capacity of the collection MAXIMUM_CAPACITY
if (initialCapacity > MAXIMUM_CAPACITY)
// If MAXIMUM_CAPACITY is exceeded, MAXIMUM_CAPACITY is assigned to initialCapacity
initialCapacity = MAXIMUM_CAPACITY;
// Check whether the loadFactor is less than or equal to 0 or whether it is a non-number
if (loadFactor <= 0 || Float.isNaN(loadFactor))
// if one of the above is true, an IllegalArgumentException IllegalArgumentException is thrown
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
// assigns the specified loadFactor to the loadFactor of the HashMap member variable
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
Copy the code4. Constructor that contains another “Map”
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
// Get the length of the parameter set
int s = m.size();
if (s > 0) {
// Check whether the length of the parameter set is greater than 0
if (table == null) { // Check whether the table has been initialized
// uninitialized, s is the actual number of elements in m
float ft = ((float)s / loadFactor) + 1.0 F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY);
// If t is greater than the threshold, initialize the threshold
if (t > threshold)
threshold = tableSizeFor(t);
}
// The system has been initialized and the number of M elements exceeds the threshold
else if (s > threshold)
resize();
// Add all elements in m to the HashMap
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict); }}}Copy the code4.3 Membership Method
1. Add method (PUT)
- First check whether the array is initialized. If not, perform an initialization operation (expansion) and assign the array size to N
- Find the bucket and determine if there is an element there. If there is no element, create a Node and insert it directly
- If there are elements, a conflict occurs
- If it is a red-black tree node, call the red-black tree method to insert
- If it is a common node, insert the end of the linked list and turn the list into a red-black tree when the length reaches a critical point
- If duplicate keys exist in the bucket, replace the key with the new value value
- If size is greater than threshold, capacity expansion is performed
public V put(K key, V value) {
return putVal(hash(key), key, value, false.true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
/* 1) Transient Node
[] table; Represents an array that stores elements in the Map collection. 2) (TAB = table) == null N = (TAB = resize()).length; n = (TAB = resize()).length; Initialize the array and assign the initialized array length to n. 4) execute n = (TAB = resize()).length, array TAB each space is null. * /
,v>
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
/* 1) I = (n-1) &hash evaluates the index of the array assigned to I, i.e. determines which bucket the element is stored in. 2) p = TAB [I = (n-1) & hash] means to obtain the calculated position of the data assigned to node P. 3) (p = TAB [I = (n-1) & hash]) == null; New nodes are created based on key-value pairs and placed into buckets at that location. Summary: If the bucket has no hash collisions, the key-value pair is inserted directly into the spatial location. * /
if ((p = tab[i = (n - 1) & hash]) == null)
// create a new node and store it in the bucket
tab[i] = newNode(hash, key, value, null);
else {
// Else TAB [I] does not equal null, indicating that this position already has a value
Node<K,V> e; K k;
/* Compare the hash value of the first element (node in array) in the bucket with the key. 1) p.hash == hash: p.hash specifies the hash value of the existing data. P represents TAB [I], which is the Node object returned by the hash, key, value, null (newNode) method. Node
newNode(int hash, K key, V value, Node
next) { return new Node<>(hash, key, value, next); } The Node class has a hash member variable that records the hash value of the previous data. 2) (k = P. key) == key: P. key obtains the key of the original data, assigns the value to k key, and compares the address values of the two keys. 3) the key! = null && key. Equals (k) : to perform here show the address of the two key values are not equal, then the judgment before adding the key whether is equal to null, if is not equal to null to invoke the equals method to judge whether the content of the two key equal. * /
,v>
,v>
if(p.hash == hash && ((k = p.key) == key || (key ! =null && key.equals(k))))
/* The hash values of the two elements are equal, and the key value is also equal. Assign the old element whole object to e, and use e to record */
e = p;
// Hash value is not equal or key is not equal; Determine whether P is a red-black tree
else if (p instanceof TreeNode)
// Put it in the tree
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// it is a linked list node
else {
/* 1) If it is a linked list, it is necessary to iterate to the last node and insert 2) It is necessary to iterate to check whether there are duplicate keys */ in the linked list
for (int binCount = 0; ; ++binCount) {
/* 1)e = p.next gets the next element of p and assigns it to e. 2)(e = p.ext) == null Determine whether p.ext is equal to null, equal to null, p has no next element, then the tail of the linked list has been reached, and no duplicate key has been found, then the HashMap does not contain the key, insert the key value pair into the linked list. * /
if ((e = p.next) == null) {
/* 1) create a newNode and insert it into the end. Node
newNode(int hash, K key, V value, Node
next) { return new Node<>(hash, key, value, next); } Notice that the fourth argument next is null, because the current element is inserted at the end of the list, so the next node must be NULL. 2) This method also meets the characteristics of the linked list data structure, adding new elements backwards each time. * /
,v>
,v>
p.next = newNode(hash, key, value, null);
/* 1) After the node is added, determine whether the number of nodes is greater than TREEIFY_THRESHOLD critical value 8. If so, convert the linked list to red-black tree. 2) int binCount = 0: indicates the initialization value of the for loop. Count from 0. It keeps track of the number of nodes traversed. The value is 0 for the first node, 1 for the second node... Seven is the eighth node, plus one element in the array, which is nine. Treeify_threshold-1 -- "8-1 --" 7 If the value of binCount is 7(plus one element in the array, the number of elements is 9), the value of treeify_threshold-1 is also 7, and the red-black tree is converted. * /
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// Convert to a red-black tree
treeifyBin(tab, hash);
// Break the loop
break;
}
/* e = p.ext is not null and is not the last element. Continue to determine whether the key value of the node in the list is the same as the key value of the inserted element. * /
if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k))))
// equal, out of the loop
/* If the element to be added has the same key as the existing element in the list, the for loop is broken. Instead of continuing the comparison, execute the following if statement to replace if (e! = null) */
break;
/* Indicates that the newly added element is not equal to the current node. Proceed to the next node. Used to iterate over the linked list in the bucket, combined with the previous e = p.ext to iterate over the linked list */p = e; }}/* = insert key (hash) = insert key (hash) = insert key (hash) = insert key (hash
if(e ! =null) {
// Record the value of e
V oldValue = e.value;
// onlyIfAbsent Is false or the old value is null
if(! onlyIfAbsent || oldValue ==null)
// Replace the old value with the new value
// e.value indicates the old value. Value indicates the new value
e.value = value;
// Callback after access
afterNodeAccess(e);
// Return the old value
returnoldValue; }}// Number of times to modify records
++modCount;
// Check whether the actual size is greater than threshold. If so, expand the capacity
if (++size > threshold)
resize();
// Callback after insertion
afterNodeInsertion(evict);
return null;
}
Copy the code2. TreeifyBin
/* Replace all link nodes in the bucket at the index of the specified hash table, resize the table unless it is too small. Node
[] TAB = TAB Array name int hash = hash indicates the hash value */
,v>
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
/* If the current array is empty or the size of the array is smaller than the tree threshold (MIN_TREEIFY_CAPACITY = 64), the array is expanded. Instead of turning nodes into red-black trees. Purpose: If the array is small, it is less efficient to convert the red-black tree and then traverse. If you do that, you recalculate the hash, the list might get shorter, and you put the data in an array, which is relatively efficient. * /
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
// Capacity expansion method
resize();
else if ((e = tab[index = (n - 1) & hash]) ! =null) {
/* 2) e = TAB [index = (n-1) &hash] (hash) = TAB [index = (n-1) &hash] (hash) = TAB [index = (n-1) &hash
// hd: head of red-black tree tl: tail of red-black tree
TreeNode<K,V> hd = null, tl = null;
do {
// Create a new tree node with the same content as the current list node e
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p; // Assign the new key p to the head of the red-black tree
else {
p.prev = tl; // Assign the previous node p to the previous node of the present p
tl.next = p; // use the present node p as the next node of the tree's tail
}
tl = p;
/* e = e.next assigns the value of the next node of the current node to e. If the next node is not null, go back to the top of the list to convert the node to a red-black tree */
} while((e = e.next) ! =null);
/* Make the first element in the bucket, that is, the element in the array, point to the node of the newly created red-black tree
if((tab[index] = hd) ! =null) hd.treeify(tab); }}Copy the code3. Expansion method resize()
final Node<K,V>[] resize() {
// Get the current array
Node<K,V>[] oldTab = table;
// Returns 0 if the current array is equal to null, otherwise returns the current array length
int oldCap = (oldTab == null)?0 : oldTab.length;
// The default threshold is 12(16*0.75)
int oldThr = threshold;
int newCap, newThr = 0;
// If the old array length is greater than 0
// Start to calculate the size after expansion
if (oldCap > 0) {
// If it exceeds the maximum value, it will no longer be expanded
if (oldCap >= MAXIMUM_CAPACITY) {
// Change the threshold to the maximum value of int
threshold = Integer.MAX_VALUE;
return oldTab;
}
/* Does not exceed the maximum value, 1) (newCap = oldCap << 1) < MAXIMUM_CAPACITY 2) oldCap >= DEFAULT_INITIAL_CAPACITY The original array length is greater than or equal to the array initialization length 16 */
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// The threshold is doubled
newThr = oldThr << 1; // double threshold
}
// The old threshold point is greater than 0
else if (oldThr > 0) // The old threshold is assigned to the new array length
newCap = oldThr;
else { // Use the default values
newCap = DEFAULT_INITIAL_CAPACITY;/ / 16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// Calculate the new maximum resize limit
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// The new threshold defaults to 24 after multiplying 12 by 2
threshold = newThr;
// Create a new hash table
@SuppressWarnings({"rawtypes","unchecked"})
//newCap is the new array length -- 32
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// Check whether the old array is empty
if(oldTab ! =null) {
// Move each bucket to the new buckets
// Iterate over each bucket of the old hash table, recalculating the new positions of elements in the bucket
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if((e = oldTab[j]) ! =null) {
// The original data is assigned null to facilitate GC collection
oldTab[j] = null;
// Determine if the array has the next reference
if (e.next == null)
// There is no next reference, it is not a linked list, there is only one key pair on the bucket, directly insert
newTab[e.hash & (newCap - 1)] = e;
// Check if it is a red black tree
else if (e instanceof TreeNode)
// Call the corresponding method to split the tree
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // Use linked lists to handle conflicts
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
// Use the principle explained above to calculate the new position of the node
do {
/ / the original indexes
next = e.next;
If e = true, the node does not need to move after resize
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// Old index +oldCap
else {
if (hiTail == null)
hiHead = e;
elsehiTail.next = e; hiTail = e; }}while((e = next) ! =null);
// Put the original index in the bucket
if(loTail ! =null) {
loTail.next = null;
newTab[j] = loHead;
}
// Add oldCap to bucket
if(hiTail ! =null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
Copy the code4. Delete method remove()
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
// Find the location based on the hash
// If the bucket mapped to the current key is not empty
if((tab = table) ! =null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) ! =null) {
Node<K,V> node = null, e; K k; V v;
// If the node on the bucket is the key, point node to that node
if(p.hash == hash && ((k = p.key) == key || (key ! =null && key.equals(k))))
node = p;
else if((e = p.next) ! =null) {
// Indicates that the node exists in the next node
if (p instanceof TreeNode)
// If the conflict is handled by the red-black tree, the node to be deleted from the red-black tree is obtained
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
// Determine whether to handle hash collisions as a list, and if so, traverse the list to find nodes to delete
do {
if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while((e = e.next) ! =null); }}// Compare the value of the found key with that of the deleted key
if(node ! =null&& (! matchValue || (v = node.value) == value || (value ! =null && value.equals(v)))) {
// Delete nodes by calling the red-black tree method
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
// Delete the list
tab[index] = node.next;
else
p.next = node.next;
// Record the number of changes
++modCount;
// The number of changes
--size;
afterNodeRemoval(node);
returnnode; }}return null;
}
Copy the code5. Find element method get()
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// If the hash table is not empty and the bucket corresponding to the key is not empty
if((tab = table) ! =null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) ! =null) {
Note: always check the first element */
if (first.hash == hash && // always check first node((k = first.key) == key || (key ! =null && key.equals(k))))
return first;
// If it is not the first element, determine whether there are any subsequent nodes
if((e = first.next) ! =null) {
// Check if it is a red-black tree. If it is, call getTreeNode to get the node
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
// If it is not a red-black tree, it is a linked list structure
if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k))))
return e;
} while((e = e.next) ! =null); }}return null;
}
Copy the codeHow to ensure thread safety
1. The use of the Collections. SynchronizedMap (Map) create a thread safe Map Collections
A generic object Map is maintained within SynchronizedMap, along with the exclusion lock mutex.
If not, the object exclusion lock is assigned to this, the object on which synchronizedMap is called, which is the Map above.
After a synchronizedMap is created, methods are locked when the map is manipulated
2. ConcurrentHashMap
1. Underlying data structure (JDK1.7)
The Segment is an internal class of ConcurrentHashMap.
static final class Segment<K.V> extends ReentrantLock implements Serializable {
private static final long serialVersionUID = 2249069246763182397L;
// Just like HashEntry in HashMap, it is a bucket that actually holds data
transient volatile HashEntry<K,V>[] table;
transient int count;
// Remember fail -- fast?
transient int modCount;
/ / size
transient int threshold;
// Load factor
final float loadFactor;
}
Copy the codeA HashEntry is similar to a HashMap, except that it uses volatile to modify its data Value and the next node, next.
2. Reasons for high concurrency (JDK1.7)
In principle, ConcurrentHashMap uses segmented locking, where segments inherit from ReentrantLock.
ConcurrentHashMap supports concurrent CurrencyLevel (number of segments).
Every time a thread holds a lock on one Segment, it does not affect the other segments.
If the size is 16, the concurrency is 16. You can allow 16 threads to operate 16 segments at the same time and still be thread-safe.
public V put(K key, V value) {
Segment<K,V> s;
if (value == null)
throw new NullPointerException();// This is why he can't put null
int hash = hash(key);
int j = (hash >>> segmentShift) & segmentMask;
if ((s = (Segment<K,V>)UNSAFE.getObject
(segments, (j << SSHIFT) + SBASE)) == null)
s = ensureSegment(j);
return s.put(key, hash, value, false);
}
Copy the codeLocate the Segment first, and then put it.
/ / put the source code
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
// Locate the table in the current Segment to HashEntry using the hashcode of the key
HashEntry<K,V> node = tryLock() ? null :
scanAndLockForPut(key, hash, value);
V oldValue;
try {
HashEntry<K,V>[] tab = table;
int index = (tab.length - 1) & hash;
HashEntry<K,V> first = entryAt(tab, index);
for (HashEntry<K,V> e = first;;) {
if(e ! =null) {
K k;
// Iterate over the HashEntry. If it is not empty, it determines whether the passed key is equal to the current one, and if it is, it overwrites the old value.
if ((k = e.key) == key ||
(e.hash == hash && key.equals(k))) {
oldValue = e.value;
if(! onlyIfAbsent) { e.value = value; ++modCount; }break;
}
e = e.next;
}
else {
// If it is not empty, create a HashEntry and add it to the Segment.
if(node ! =null)
node.setNext(first);
else
node = new HashEntry<K,V>(hash, key, value, first);
int c = count + 1;
if (c > threshold && tab.length < MAXIMUM_CAPACITY)
rehash(node);
else
setEntryAt(tab, index, node);
++modCount;
count = c;
oldValue = null;
break; }}}finally {
/ / releases the lock
unlock();
}
return oldValue;
}
Copy the codeThe first step is to try to acquire the lock. If the lock fails and there is no doubt that other threads are competing, use the spin of scanAndLockForPut() to acquire the lock.
- Try to spin the lock.
- If the number of retries is reached
MAX_SCAN_RETRIESBlock lock acquisition to ensure success.
Get the logical
The get logic is simple. You just Hash the Key to the Segment and then Hash it to the element.
Because the value attribute in HashEntry is decorated with a volatile keyword to ensure memory visibility, it is retrieved with the latest value each time.
The Get method of ConcurrentHashMap is very efficient because the entire process does not require locking.
1.3 Underlying Data Structure (JDK1.8)
The original Segment Segment lock is abandoned, and CAS + synchronized is used to ensure concurrency security.
Much like HashMap, HashEntry is changed to Node, but its effects remain the same. Values and next are volatile to ensure visibility, and a red-black tree is introduced that converts when the list is greater than a certain value (the default is 8).
1.4 Access Operation? And how is thread safety guaranteed? (jdk1.8)
- Put Procedure:
-
Calculate the Hashcode based on the key.
-
Check whether initialization is required.
-
That is, the Node located for the current key. If it is empty, data can be written to the current position. CAS is used to attempt to write data.
-
If the current location hashCode == MOVED == -1, you need to expand the capacity.
-
If none is met, data is written using a synchronized lock.
-
If the number is greater than TREEIFY_THRESHOLD, it is converted to a red-black tree.
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
// Compute the hash value
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
// Determine whether initialization is required
if (tab == null || (n = tab.length) == 0)
tab = initTable();
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
If the value is empty, data can be written to the current node. Use CAS to attempt to write data to the node.
if (casTabAt(tab, i, null.new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
// If the current location of hashCode == MOVED == -1, the capacity needs to be expanded.
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
// Synchronized locks are used to write data.
V oldVal = null;
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
if(e.hash == hash && ((ek = e.key) == key || (ek ! =null && key.equals(ek)))) {
oldVal = e.val;
if(! onlyIfAbsent) e.val = value;break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break; }}}else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
if((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) ! =null) {
oldVal = p.val;
if(! onlyIfAbsent) p.val = value; }}}}if(binCount ! =0) {
// If the number is greater than 'TREEIFY_THRESHOLD', the tree is converted to red-black.
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if(oldVal ! =null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}
Copy the code+ get operation steps:
1. Based on the calculated HashCode addressing, return the value directly if it is on the bucket.
2. If it’s a red-black tree, get the value as a tree.
3. If not, then follow the linked list to iterate to get the value.
1.5 What is CAS? What’s the spin?
CAS is an implementation of optimistic locking. It is a lightweight lock, and many implementations of JUC tool classes are based on CAS.
The process of CAS operation is as follows: The thread does not lock data when reading data. When preparing to write back data, the thread compares whether the original value is modified. If the data is not modified by other threads, the thread writes back the data.
This is an optimistic strategy, assuming that concurrent operations will not always happen.
1.6 CAS performance is very high, but synchronized performance is not very good.
Synchronized has always been a heavyweight lock, but since Java has officially upgraded it, it now uses lock upgrades.
For synchronized lock acquisition, the JVM uses an optimized lock upgrade method, which is to use a biased lock to give priority to the same thread and then acquire the lock again. If the lock fails, it is upgraded to a CAS lightweight lock. If the lock fails, it will spin briefly to prevent the thread from being suspended. If all else fails, upgrade to a heavyweight lock.
So it was a step up, and initially it was locked in a lot of lightweight ways.