In the autumn recruitment interview preparation, the blogger looked for many blogs about HashMap, but after the autumn recruitment, looking back, I felt that there was no comprehensive and easy to understand article on HashMap (maybe the blogger did not find it), so after the autumn recruitment, I wrote this article, and tried my best to explain the HashMap source code in easy to understand. And try to cover the HashMap points of the interview.
In the bloggers’ experience, HashMap is the star of the job interview scene. Almost every company the blogger interviews with has some sort of question about the underlying implementation of HashMap.
This article will be organized in the following order:
HashMap interview “star” question summary, and answer to the star question
HashMap in JDK8
Note: In the source code analysis below,
The number of comments is proportional to the importance
The number of comments is proportional to the importance
The number of comments is proportional to the importance
HashMap member attribute source code analysis
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { private static final long serialVersionUID = 362498820763181265L; /** * The default initial capacity - MUST be a power of two. */ Static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 /** * The maximum capacity, used if a higher value is implicitly specified * by either of the constructors with arguments. * MUST be a power of two Static final int MAXIMUM_CAPACITY = 1<<30; /** * The load factor used when none specified in constructor. */ ** * One of the parameters that affects the performance of a HashMap is the weight between time and space, and we'll see later that the elements of the HashMap are stored in the Node array, which is called the size of the "bucket". * When size== number of buckets *DEFAULT_LOAD_FACTOR, the HashMap must be expanded. DEFAULT_LOAD_FACTOR measures bucket utilization: when DEFAULT_LOAD_FACTOR is small (bucket utilization is small), * more space is wasted (because only the number of buckets can be stored *DEFAULT_LOAD_FACTOR). * In this case, the probability of putting elements in a HashMap into a conflict is also very low. * The operation cost of a HashMap, such as PUT and get, is O(1). * When the bucket utilization is large (DEFAULT_LOAD_FACTOR is large, but can be greater than 1 because conflicting elements are joined using linked lists or red-black trees) * space utilization is high, * this also means that there are many elements in a bucket, The cost of each put or GET operation is greater than O(1). DEFAULT_LOAD_FACTOR is a balancing point between space and time. * DEFAULT_LOAD_FACTOR is small, which requires more space but costs less to put and get; * DEFAULT_LOAD_FACTOR large requires less space, but puts and gets are expensive). * * Increase the number of buckets *2, i.e. increase the size of the Node array by twice. * * Increase the size of the Node array by twice. Each bucket in the Node array stores a Node list. When the list length is greater than or equal to 8, * the list will change to a red-black tree structure (because the red-black tree complexity is logn, the list is N, the red-black tree structure is less expensive than the linked list). */ static final float DEFAULT_LOAD_FACTOR = 0.75f; /** * The bin count threshold for using a tree rather than list for a * bin. Bins are converted to trees when adding an element to a * bin with at least this many nodes. The value must be greater * than 2 and should be at least 8 to mesh Life in * tree removal about conversion back to plain bins upon * Shrinkage. */ / When the length of a list in a bucket >=8 Static final int TREEIFY_THRESHOLD = 8; static final int TREEIFY_THRESHOLD = 8; /** * The bin count threshold for untreeifying a (split) bin during a * resize operation. Should be less than TREEIFY_THRESHOLD, and at * most 6 to mesh with shrinkage detection under removal. */ / Static final int UNTREEIFY_THRESHOLD = 6; /** * The smallest table capacity for which bins may be treeified. * (Otherwise the table is resized if too many nodes in a bin.) * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts * between resizing and treeification Static final int MIN_TREEIFY_CAPACITY =64 static final int MIN_TREEIFY_CAPACITY =64 static final int MIN_TREEIFY_CAPACITY =64 }Copy the codeAll data in a HashMap is stored in an array of nodes. What is a Node?
Static class Node<K,V> implements map. Entry<K,V> {// Save key hashcode=key hashcode ^ // When we put(k,v) into a map, the k and v key pairs are encapsulated as nodes. Where is this Node in the Node array? Index =hash&(n-1) where n is the length of the Node array. So why does this hash reduce conflict? If // uses hashCode&(n-1) directly to calculate the index, the high-order randomness of hashCode is completely ignored because n is small relative to // hashCode. Based on this, the random final int hash of the lower 16 bits of HashCode is enhanced by xor mixing the higher 16 bits of hashcode into the lower 16 bits of Hashcode; final K key; // Save the map key V value; // Save the map value Node<K,V> next; // hash (int hash, K key, V value, Node<K,V> next); this.key = key; this.value = value; this.next = next; }Copy the codeHashMap hash function and tableSizeFor hash function
/** * HashMap allows keys to be null and hash values to be 0 (which also means that HashMap allows key-value pairs with keys to be null). * Non-null keys hash 16 bits higher and 16 bits lower by: The hashCode * high 16 bits of key and the high 16 bits of hashCode xor the low 16 bits of hashCode. To enhance the randomness of hash and reduce the * randomness of hash&(n-1), that is, reduce hash conflicts and improve the performance of HashMap. So the implementation of the hashCode function as the key of a HashMap has a significant impact on the performance of a HashMap *. In extreme cases, all keys have the same hashCode, which makes the performance of a HashMap very poor! */ static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); * tableSizeFor (tableSizeFor); tableSizeFor (tableSizeFor); This number is the smallest of all numbers greater than or equal to cap and is an integer power of 2 *, that is, returns the number closest to cap(>=cap) and is an integer power of 2. * The logic is as follows: if a number is an integer power of 2, then the binary of that number minus 1 is a mask. */ static final int tableSizeFor(int cap) {// For example, if the third bit of n is 1, int n = cap-1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; / / for example: if n is: 00010000 00000000 00000000 000 / * n | = n > > > 1; - > n: 00011000, 00000000, 00000000, 0000 n | = n > > > 2. ->n: 00011110 00000000 00000000 0000 n |= n >>> 4; ->n: 00011111 11100000 00000000 0000 n |= n >>> 8; ->n: 00011111 11111111 11100000 0000 n |= n >>> 16; ->n:00011111 11111111 11111111 1111 return n+1: 00010000 00000000 00000000 00000000 000(>=cap and is an integer power of 2, the smallest difference between cap and n+1 must be an integer power of 2, and must be >=cap If n binary first k is 1, then through the above four [0, k] after the '|' operations are turned into 1, i.e., a series of consecutive binary "1" (mask), and finally the n + 1 must be an integer power of 2 (if not overflow) * / return (n < 0)? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }Copy the codeHashMap member attribute source code analysis
/** * The table, initialized on first use, and resized as * necessary. When allocated, length is always a power of two. * (We also tolerate length zero in some operations to allow * bootstrapping mechanics */ / All the (k,v) we put into map are wrapped in Node, all the nodes are stored in table array transient Node< k, V>[] table; /** * Holds cached entrySet(). Note that AbstractMap fields are used * for keySet() and values() transient Set<Map.Entry<K,V>> entrySet; /** * The number of key-value mappings contained in this map. /** * The number of times this HashMap has been structurally modified * Structural modifications are those that change the number of mappings in * the HashMap or otherwise modify its internal structure (e.g., * rehash). This field is used to make iterators on Collection-views of * the HashMap fail-fast. (See ConcurrentModificationException). * / / / failFast mechanism, as has been said in the article explain ArrayList, and LinkedList the transient int modCount; /** * The next size value at which to resize (capacity * load factor). * * @serial */ // (The javadoc description is true upon serialization. // Additionally, if the table array has not been allocated, This // field holds the initial array capacity, or zero signal_capacity.) // When creating a HashMap, the change value is: initial capacity (integer power of 2) // After the threshold value is the HashMap expansion threshold: For example, if the capacity we pass to the HashMap constructor is 9, then the initial threshold value is 16. After // putting the first element into the HashMap, An internal Node array of 16 length is created, and the value of threshold is updated to 16*0.75=12. // If the number of elements in the Node array is 13 after we put an element to the HashMap, the Node array will be expanded (if the number of elements in the array >threshold, 13>threshold=12). The specific expansion operation will be analyzed in detail after //. And move all the original elements into the new Node array. int threshold; /** * The load factor for The hash table. ** @serial */ / The default is 0.75 final float loadFactor;Copy the codeHashMap constructor:
// constructor: Specify the size of the map, And loadFactor 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 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; TableSizeFor (loadFactor) {tableSizeFor (loadfactor); Threshold = tableSizeFor(initialCapacity); initialCapacity = tableSizeFor(initialCapacity); } // Just specify the HashMap capacity constructor, Public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR); } // No argument constructor, default loadfactor: 0.75 public HashMap() {this.loadfactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted} // All other fields defaultedCopy the codeWe can see from the constructor that the HashMap is “lazy loading”. In the constructor, the values retain the reserved values, and the table array is not initialized. The map is initialized when we put the first element into the map!
HashMap get function source analysis
Public V get(Object key) {Node<K,V> e; //hash: This function is analyzed above. HashCode // getNode returns the type Node: if the value is null, there is no corresponding key in the map. If the value corresponding to the key is null, then the return value of getNode is null, and the return value is also null. If the return value of get is null, the key may not be included or the value of the key may be null! How do you determine if a map contains a key? Return (e = getNode(hash(key), key)) == null? null : e.value; } public Boolean containsKey(Object key) {// Make sure that all <key,value> we put into the map are encapsulated in Node. Return getNode(hash(key), key)! = null; /** * Implements map. get and related methods ** @param hash hash for key // Implements map. get and related methods ** @param hash hash for key Key hash * @param key the key * @return the node, or null if none */ final node <K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; Hash =(n-1)&hash =(n-1)&hash =(n-1)&hash =(n-1)&hash =(n-1)&hash =(n-1)&hash =(n-1)&hash =(n-1)&hash =(n-1)&hash =(n-1)&hash =(n-1)&hash =(n-1)&hash =(n-1)&hash =(n-1)&hash =(n-1)&hash =(n-1)&hash =(n-1)&hash =(n-1)&hash =(n-1) // Otherwise: if the table[index] position is searched, check whether there is a Node with the target key: // Red black tree is a kind of weakly balanced (relative to AVL)BST, // Red black tree search, delete, insert and other operations can be guaranteed within O(lon(n)) time complexity, red black tree principle is not covered in this article // If ((TAB = table)! If (TAB = table)! If (TAB = table)! = null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) ! = null) { if (first.hash == hash && // always check first node ((k = first.key) == key || (key ! = null && key.equals(k)))) return first; If ((e = first.next)! If (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreenode (hash, key); Do {/ / list search (find) if (e.h ash = = hash && ((k = e.k ey) = = key | | (key! = null && key.equals(k)))) return e; } while ((e = e.next)! = null); } } return null; // Return null}Copy the codeGet function is essentially a linked list or red-black tree traversal search node specified key process; In addition, the return value of the HashMap get function does not determine whether a key is contained in the map. The return value of get may not contain the key. The value of the key may be NULL. A HashMap allows a null key and a null value.
HashMap put function source analysis
//put function entry, two arguments: Key and value public V put(K key, V value) {// Return putVal(hash(key), key, value, false, true); /** * Implements Map. Put and related methods ** @param hash Hash for key * @param key the key * @param value the value to put * @param onlyIfAbsent if true, don't change existing value * @param evict if false, * @return previous value, or null if None */ //hash: Key hashCode final V putVal(int hash, K key, V value, Boolean onlyIfAbsent, Boolean evict) {Node<K,V>[] TAB; Node<K,V> p; int n, i; // If you put a HashMap, you need to check whether the table array has been initialized. Ensure table array must initialize the if ((TAB = table) = = null | | (n = TAB. Length) = = 0) n = (TAB = the resize ()). The length; // Same as the get function above, specify the Node of the key, put in the table array I =(n-1)&hash subscript position, If ((p = TAB [I = (n-1) & hash]) == null) // If (p = TAB [I = (n-1) & hash]) == null) // If (p = TAB [I = (n-1) & hash]) == null) Store in table[I] TAB [I] = newNode(Hash, key, value, null); Else {// If table[I] already has elements, then do: // Insert the current key and value into the end of the list or into the red black tree. // If Node. Key = key is already in the list or the red black tree. E. value Node<K,V> e; e<K,V> e; e<K,V> e; K k; Hash ==hash; // Why do get and put check p.hash==hash? // Since hash is a comparison of two integers, the comparison is relatively cheap. Key is generic, and the comparison of objects is more expensive than integer comparison. Hash is equal in the comparison of the key if (p.h ash = = hash && / / ((k = p.k ey) = = key | | (key! = null && key.equals(k)))) e = p; //e points to a Node: Else if (p instanceof TreeNode) // Insert a TreeNode with this key, return the TreeNode with this key, Otherwise null e = ((TreeNode<K,V>)p). PutTreeVal (this, TAB, hash, key, value); Else {//table[I] stores the linked list, similar to TreeNode // Check whether key exists before traversing the linked list, if so, e points to the Node // Otherwise, insert the Node to the end of the linked list, check whether the length of the linked list >=8 after insertion. // the last value is the length of the list. For (int binCount = 0; ; ++binCount) {if ((e = p.ext) == null) {// If (e = p.ext) == null) {// If (e = p.ext) == null) {// If (e = p.ext) == null) { P.ext = newNode(hash, key, value, null); If (binCount >= treeify_threshold-1) // -1 for 1st // If (binCount >= treeify_threshold-1) // -1 for 1st // If (binCount >= treeify_threshold-1) // If (binCount >= treeify_threshold-1) // -1 for 1st // // We will analyze treeifyBin source code implementation treeifyBin(TAB, hash); break; } // If p does not point to the end of the list, the value of e will be updated; // If p is not the end of the list, the value of e will be updated. / / wait to prepare the next traversal, p = p.n ext, namely the if p = e (e.h ash = = hash && ((k = e.k ey) = = key | | (key! = null && key.equals(k)))) break; p = e; } } if (e ! = null) {// existing mapping for key = // existing mapping for key = // existing mapping for key = // // Save oldValue //onlyIfAbsent (false), evict (true), and onlyIfAbsent (true). Instead of updating the previous value, connect if (! onlyIfAbsent || oldValue == null) e.value = value; // Update e.value // The default implementation of this function is "empty", that is, this function does nothing by default, so why have it? AfterNodeAccess (e); afterNodeAccess(e); afterNodeAccess(e); afterNodeAccess(e); return oldValue; // Return the old value}} // if the key is inserted for the first time, it is executed here. //failFast //size stores the number of key-value pairs stored in the current HashMap. The size method of HashMap directly returns size. // Threshold stores the current table array length *loadfactor. If the number of // nodes stored in the table array exceeds threshold, the capacity of the table array will be doubled. //resize if (++size > threshold) resize(); AfterNodeAccess afterNodeInsertion(evict); return null; } // Convert the list to a red-black tree structure, Replaces all Linked Nodes in bin at index for given hash unless * table is too small, in which case resizes instead. */ final void treeifyBin(Node<K,V>[] tab, int hash) { int n, index; Node<K,V> e; // The MIN_TREEIFY_CAPACITY value is 64, so when the list length is greater than 8, there are two cases: // If the length of the table array is <64, expand the table array. // If the length of the table array is >64, transform the list to a red-black tree. // If the length of the table array is >64, transform the list to a red-black tree. if (tab == null || (n = tab.length) < 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 { p.prev = tl; tl.next = p; } tl = p; } while ((e = e.next) ! = null); if ((tab[index] = hd) ! = null) hd.treeify(tab); }}Copy the codeHashMap resize function source code analysis key key, interview talked about HashMap must test resize related knowledge
/** * The current function is called in two cases: The first hHashMap put method is used before the table is initialized. The first hHashMap put method is used before the table is initialized. The initial capacity of the table array is stored in threshold (if an initial capacity is passed in from the constructor *). If the capacity was not specified when the HashMap was created, the initial capacity of the table array is the default: 16. That is, resize * 2 is executed when the table array is initialized. When the value of size is greater than threshold, the capacity expansion will be triggered. That is, the resize method will be executed. In this case, the size of the table array will be doubled. * * The capacity of a HashMap must be an integer power of 2. * index = hash & (n-1) * index = hash & (n-1) * index = hash & (n-1) Hash %n is used to hash the current key and value pairs into each bucket. * So why don't we use mod (%) here? The reason is that THE CPU is better to support the bit operation, that is, the bit operation speed is very fast. * In addition, when n is an integer power of 2: Hash &(n-1) is equivalent to hash%(n-1), but the efficiency of the two is different, with bit operations * much more efficient than % operations. Based on this, hash&(n-1) is used in the HashMap. This has the added benefit of having a handy feature when migrating nodes from an old array to a new one: A HashMap uses a table array to hold nodes, so when you expand the table array (array expansion), you must first create a new array, and then rehash the elements of that array into the new array. The default Hash capacity is n=16, and the default loadfactor=0.75 (other integer powers of 2 are similar) : default capacity: n=16, binary: 10000; N-1:15, * N-1 binary: 01111, a series of 1's. At some point, the map element is larger than 16*0.75=12, that is, size>12, then we create a new array, * twice the size before the expansion, newtab, len=32; Next we need to rehash the Node in the table to newTab. Start with table I =0 *. Assuming we are currently dealing with a node at index I of the table array, where should this node be placed in newTab? The following hash table * shows the hash value for node.key, which is the same as the node. Len = hash index = the hash % & (len - 1) = hash & (32-1) = hash & 31 * = hash & (0 x0001_1111); I =hash&(16-1)=hash&15 * =hash&(0x0000_1111). Note the similarities and differences between the two: I =hash&(0x0000_1111); Index =hash&(0x0001_1111) * Index = hash & x0001_1111 (0) = hash & (0 x0000_1111) | * hash & x0001_0000 (0) = hash & (0 x0000_1111) | hash&n) = I + (hash&n). * hash&n is either equal to n or zero; That is, inde is either equal to I or equal to I +n; More specifically: when hash&n==0, index= I; * index= I +n when hash&n==n; How does that help? * all nodes in table[I] are either in newTab I (unchanged) or newTab I +n (I +n); If hash&n==0, the current node is connected to l1; if hash&n==0, the current node is connected to L1. Otherwise connect to l2 linked list. Table [I] newtab[I]=l1,newtab[I +n]=l2, newTab [I +n]=l2 This is also the convenience of a HashMap where the capacity must be an integer power of 2. * The following resize logic is the same as above. Split nodes at table[I] into two linked lists The two lists are then placed newtab[I] * and newtab[I + N] * initializing or doubles table size. If null, allocates in * accord with initial capacity target held in field threshold. * Otherwise, because we are using power-of-two expansion, the * elements from each bin must either stay at same index, or move * with a power of two offset in the new table. * * @return the table */ final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; Int oldCap = (oldTab == null)? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; if (oldCap > 0) { if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } // Normal capacity expansion: NewCap = oldCap << 1 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) NewThr = oldThr << 1; // double threshold } else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; // Zero initial threshold using defaults newCap = DEFAULT_INITIAL_CAPACITY; // Default capacity newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); //threshold } if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; // Update threshold @suppressWarnings ({"rawtypes","unchecked"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; // Update threshold @suppressWarnings ({"rawtypes","unchecked"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; // New array table = newTab; // Execute a new array with double capacity if (oldTab! = null) { for (int j = 0; j < oldCap; ++j) {// oldTab Node<K,V> e; if ((e = oldTab[j]) ! = null) { oldTab[j] = null; NewTab [e.hash & (newcap-1)] = e; newTab[e.hash & (newcap-1)] = e; Else if (e instanceof TreeNode) // If (e instanceof TreeNode) (TreeNode<K,V>)e).split(this, newTab, j, oldCap); Else {// preserve order // Node<K,V> loHead = null, loTail = null; L1 Node<K,V> hiHead = null, hiTail = null; // second list l2 Node<K,V> next; do { next = e.next; If ((e.hash & oldCap) == 0) {//rehash to table[j] // connect current node to l1 if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else {// Connect current node to l2 if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) ! = null); if (loTail ! Next = null; // table[j] lotail.next = null; newTab[j] = loHead; } if (hiTail ! = null) {//l1 into table[j+oldCap] hitail. next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }Copy the codeHashMap interview “star” questions and answers:
Do you know HashMap? Talk about HashMap?
This question not only tests your knowledge of Hashmaps, but also your ability to express and organize problems. In my opinion, we should start from the following perspectives (summary of all common HashMap questions) :
Size must be an integer power of 2 Cause GET and PUT method Flow Resize method Factors that affect the performance of a HashMap (implementation of the hashCode function for key, loadFactor, and initial capacity) HashMap Hash table[I] : hash table[I] : hash table[I] : hash table Can the get method of a HashMap determine whether an element is in a map or not? Is it thread safe to use HashMap? Which links are most likely to fail? HashMap value is null but HashTable and ConcurrentHashMap values are not allowed to be null. The hook function in HashMap (explained later in the section on LinkedHashMap, as an extension of HashMap to increase your interviewer’s impression of you)
The answers to the above questions can be found in the above source code analysis, the following three additions:
How does the initial capacity design of the HashMap affect the performance of the HashMap? If you estimate that you are storing up to 64 elements in a HashMap, then when you create a HashMap: The default capacity is 16, which needs to be expanded after storing 16 loadfactor elements (array expansion involves allocation of continuous space and Node rehash, which is expensive, so it should be avoided as much as possible). If 64 is passed to the constructor, the HashMap will be expanded after storing 64loadFactor elements. However, if you pass the constructor (int)(64/0.75)+1, then you can ensure that the HashMap does not need to be expanded, avoiding the cost of expansion.
Are HashMap threads safe, which ones are most likely to fail, and why? We all know that the HashMap thread is not safe, so what is the best way to break the thread and why? ConcurrentHashMap, because we all know that HashMap is not thread-safe, ConcurrentHashMap is thread-safe, and ConcurrentHashMap, Take a look at what security measures ConcurrentHashMap adds to HashMap to solve the problem. The ConcurrentHashMap article will briefly answer this question: The HashMap put operation is not secure because no lock is used; The biggest security risk for HashMap with multiple threads is when it comes to capacity expansion. Think of a situation where the HashMap uses a default capacity of 16 and 100 threads put elements into the HashMap at the same time. Capacity expansion is messy because there is no lock for concurrency security, and ConcurrentHashMap concurrent capacity expansion is a core method of ConcurrentHashMap as discussed in a later blog post.
HashMap value is null but HashTable and ConcurrentHashMap values are not allowed to be null. ConcurrentHashMap and Hashtable are technically allowed to be null. But it is not actually allowed. This must be to solve some problem. To illustrate this problem, let’s look at the following example (here we use ConcurrentHashMap, HashTable is similar).
HashMap allows a null value. If the get method returns null, the map may have no corresponding key. The value of the key may be NULL. Therefore, get cannot determine whether a map contains a key. Only contains can be used to determine whether a map contains a key.
Return a value if the map contains a key, otherwise raise an exception:
if (map.containsKey(k)) {
return map.get(k);
} else {
throw new KeyNotPresentException();
}
Copy the codeIf the above map is a HashMap, then there is no problem, because hashmaps are inherently thread-unsafe and ConcurrentHashMap should be used if there is a concurrency problem, so the correct result is returned under a single thread. If the above map is a ConcurrentHashMap, There is a concurrency problem: It is possible that between map.containsKey(k) and map.get, another thread may delete the key, and map.get will return null. ConcurrentHashMap does not allow value to be null. A value that is not allowed at all? ConcurrentHashMap does not allow a value to be null. Therefore, map.get(key) can be used to determine whether the map contains the key.