Abstract
HashMap is the most frequently used data type for mapping (key-value pair) processing by Java programmers. With the latest JDK (Java Developmet Kit) release, JDK1.8 has optimized the underlying implementation of HashMap, such as the introduction of red-black tree data structures and capacity expansion optimizations. This article combines JDK1.7 and JDK1.8 differences, in-depth discussion of HashMap structure implementation and functional principle.
Introduction to the
Java defines an interface java.util.map for mapping in data structures. This interface mainly has four commonly used implementation classes, namely HashMap, Hashtable, LinkedHashMap and TreeMap. Class inheritance relationship is shown in the following figure:
The following are some explanations for the characteristics of each implementation class:
(1) HashMap: It stores data according to the hashCode value of the key. In most cases, its value can be directly located, so it has fast access speed, but the traversal order is uncertain. A HashMap allows at most one record to have a null key and multiple records to have a NULL value. A HashMap is not thread-safe, meaning that more than one thread can write a HashMap at any one time, which can lead to data inconsistencies. If thread-safe is desired, the Collections synchronizedMap method can be used to make HashMap thread-safe, or ConcurrentHashMap can be used.
(2) the Hashtable: Hashtable is a legacy class. Many common functions of HashMap are similar to those of Dictionary class, but it is thread-safe. Only one thread can write Hashtable at any time. ConcurrentHashMap introduces segmental locking. The use of Hashtable is not recommended in new code, and can be replaced with HashMap in cases where thread safety is not required, and ConcurrentHashMap in cases where thread safety is required.
(3) LinkedHashMap: LinkedHashMap is a subclass of HashMap, which preserves the insertion order of records. When Iterator traverses LinkedHashMap, the records obtained first must be inserted first. It can also be constructed with parameters and sorted according to the access order.
(4) TreeMap: TreeMap implements the SortedMap interface, which can sort the records it saves according to the key. The default is the ascending order of the key value. You can also specify the comparator for sorting. If sorted mappings are used, TreeMap is recommended. When using a TreeMap, key must implement the Comparable interface or in constructing TreeMap incoming custom Comparator, otherwise it will throw at runtime Java. Lang. ClassCastException type of exception.
For the four Map types mentioned above, the key in the Map is required to be an immutable object. An immutable object is an object whose hash value does not change after it is created. If the hash value of the object changes, the Map object may not be able to locate the Map.
Through the above comparison, we know that HashMap is a common member of the Java Map family, and it is the most frequently used one since it can meet the use conditions of most scenarios. The following is an in-depth explanation of the working principle of HashMap from the aspects of storage structure, common method analysis, capacity expansion and security, mainly combining the source code.
Internal implementation
To understand a HashMap, first we need to know what a HashMap is, namely its storage structure – field; Then figure out what it can do, that is, its functional realization – method. Let’s elaborate on these two aspects.
Storage structure – Fields
In terms of structure implementation, HashMap is an array + linked list + red-black tree (JDK1.8 adds red-black tree part) implementation, as shown below.
Two questions need to be addressed here: What exactly is stored underneath the data? What are the advantages of this type of storage?
(1) From the source code, there is a very important field in the HashMap class, is Node[] table, namely hash bucket array, obviously it is an array of nodes. Let’s see what Node[JDK1.8] is.
static class Node<K,V> implements Map.Entry<K,V> { final int hash; Final K key; V value; Node<K,V> next; // next node of the list node (int hash, K key, V value, node <K,V> next) {... } public final K getKey(){ ... } public final V getValue() { ... } public final String toString() { ... } public final int hashCode() { ... } public final V setValue(V newValue) { ... } public final boolean equals(Object o) { ... }}Copy the codeNode is an inner class of HashMap that implements the Map.Entry interface and is essentially a mapping (key-value pair). Each black dot in the figure above is a Node object.
(2) HashMap is stored using hash tables. Hash table to solve the conflict, can adopt open address method and chain address method to solve the problem, Java HashMap uses chain address method. Linked address method, simply put, is the combination of an array and a linked list. Each array element has a linked list structure. When the data is hashed, the array subscript is obtained and the data is placed on the linked list of the corresponding subscript element. For example, the program executes the following code:
Map. Put (" mei tuan "," xiao Mei ");Copy the codeThe system calls the hashCode() method of meituan key to get its hashCode value (which applies to every Java object), and then uses the last two steps of the Hash algorithm (high order and modulo, described below) to locate the storage location of the key-value pair. Sometimes the two keys locate to the same location, indicating that a Hash collision has occurred. Of course, the more evenly distributed the results of the Hash algorithm are, the smaller the probability of Hash collisions is, and the higher the map access efficiency is.
If the Hash bucket array is large, even a bad Hash algorithm will be scattered. If the Hash bucket array is small, even a good Hash algorithm will have a lot of collisions, so there is a trade-off between the cost of space and the cost of time. In fact, the size of the Hash bucket array is determined according to the actual situation. The hash algorithm is designed to reduce hash collisions. So how can map be controlled so that the probability of Hash collisions is small and the Hash bucket array (Node[] table) takes up less space? The answer is good Hash algorithms and scaling mechanisms.
Before we understand the Hash and expansion process, we need to take a look at a few fields of the HashMap. The default constructor for a HashMap initializes the following fields:
int threshold; Final float loadFactor; // Final float loadFactor; // load factor int modCount; int size;Copy the codeFirst, the initial length of Node[] table is length(the default is 16), Load factor is the Load factor (the default is 0.75), and threshold is the maximum number of nodes (key-value pairs) that a HashMap can hold. Threshold = length * Load factor. That is, the larger the load factor, the greater the number of key-value pairs it can hold after the array has been defined.
Based on the definition formula of Load factor, it can be seen that threshold is the maximum number of elements allowed under the corresponding Load factor and length(array length). If the number exceeds this number, the capacity of HashMap will be resized. The capacity of HashMap after expansion will be twice the previous capacity. The default Load factor of 0.75 is a balanced choice for space and time efficiency. It is recommended that you do not change it, except in special cases of time and space. If the memory space is large and time efficiency is high, you can lower the value of Load factor. Conversely, if memory is tight and time efficiency is not high, you can increase the value of the loadFactor, which can be greater than 1.
The size field is pretty straightforward and is the number of key-value pairs that actually exist in the HashMap. Note the difference between table length and the maximum number of key-value pairs threshold. The modCount field is mainly used to record the number of changes in the internal structure of the HashMap, which is mainly used for rapid iteration failures. An internal structure change is a structure change, such as putting a new key-value pair, but overwriting the value of a key is not a structure change.
In a HashMap, the length of the hash bucket array table must be 2 to the power of n (must be composite), which is an unconventional design. The conventional design is to design the bucket size as a prime number. Relatively speaking, the probability of conflicts caused by prime numbers is less than composite numbers. For proof, please refer to this article. Hashtable initializes buckets with a size of 11, which is an application whose bucket size is designed as a prime number (Hashtable cannot be guaranteed to remain prime after expansion). The unconventional design of HashMap is mainly for optimization in modulus taking and expansion. At the same time, in order to reduce conflicts, HashMap also adds high order to participate in the operation process when locating the hash bucket index position.
There is a problem here. Even if the load factor and Hash algorithm are properly designed, it is inevitable that the zipper is too long. Once the zipper is too long, the performance of the HashMap will be seriously affected. Therefore, in JDK1.8, the data structure is further optimized and red black tree is introduced. When the length of the linked list is too long (more than 8 by default), the linked list will be converted into a red-black tree, and the performance of HashMap will be improved by utilizing the characteristics of rapid addition, deletion, modification and search of red-black tree, in which the insertion, deletion and search algorithms of red-black tree will be used. Red-black trees are not discussed in this article, but more on how red-black tree data structures work can be found in this article.
Function implementation – method
The internal functions of HashMap are realized in many ways. This paper mainly explains in depth three representative points: obtaining hash bucket array index position according to key, detailed execution of PUT method, and expansion process.
1. Determine the position of the hash bucket array index
Whether adding, deleting, or finding key-value pairs, locating the hash bucket array is a critical first step. Said earlier HashMap data structure is a combination of arrays and linked list, so we certainly hope this HashMap element position as far as possible some more uniform distribution, try to ensure that only one of the number of elements in each position, so when we use the hash algorithm to obtain the location, immediately can know is the corresponding position of the element, No need to traverse the linked list, greatly optimizing the efficiency of the query. The hash map locates the index position of the array, which directly determines the discrete performance of the hash method. Take a look at the source code implementation (method 1 + method 2):
Static final int hash(Object key) {// jdk1.8&jdk1.7int h; // h ^ (h >>> 16) return (key == null)? 0 : (h = key.hashCode()) ^ (h >>> 16); } static int indexFor(int h, int length) {// static int indexFor(int h, int length) { }Copy the codeThe Hash algorithm here essentially consists of three steps: taking the hashCode value of the key, the high level operation, and the modulus operation.
For any given object, as long as its hashCode() returns the same value, the program always computes the same Hash code by calling method 1. The first thing that comes to mind is modulo the hash value over the length of the array so that the elements are relatively evenly distributed. However, modular operations are expensive, as in a HashMap: method two is called to calculate at which index of the table array the object should be stored.
This method is very clever. It uses h & (table.length-1) to get the save bit of the object, and the length of the underlying array of the HashMap is always 2 to the power of n, which is an optimization of the speed of HashMap. When length is always 2 to the n, h& (length-1) is equivalent to modulo length, that is, h%length, but & is more efficient than %.
In JDK1.8, we optimized the algorithm for high-order operations by using the high-16bit xor low-16bit hashCode() : (h = k.hashcode ()) ^ (h >>> 16), mainly from the speed, efficiency, quality, so that when the array table length is relatively small, it can also ensure that the high and low bits are involved in the Hash calculation, and at the same time there is not too much overhead.
For example, n is the length of a table.
2. Analyze the PUT method of the HashMap
HashMap put method execution process can be understood through the following figure, their interest can be compared to the source code more clearly study study.
Check whether the key-value pair array table[I] is empty or null; otherwise, perform resize() for expansion; Table [I]==null; table[I]==null; table[I]==null; Check whether the first element of the table[I] is the same as the first element of the key. If the first element of the table[I] is the same as the first element of the key. Check whether table[I] is a treeNode, i.e. whether table[I] is a red-black tree. If table[I] is a red-black tree, insert key pairs directly into the tree; otherwise, change to ⑤. (5). Traverses table[I] to determine whether the length of the linked list is greater than 8. If the length is greater than 8, the linked list is converted into a red-black tree, and the insertion operation is performed in the red-black tree; otherwise, the insertion operation of the linked list is carried out; If the key already exists in the traversal process, the value can be overwritten directly. ⑥. After the insert is successful, check whether the actual number of key value pairs size exceeds the maximum capacity threshold. If so, expand the capacity.
JDK1.8HashMap put method
1 public V put(K key, V value) {2 // Hash key hashCode() 3 return putVal(hash(key), key, value, false, true); 4 } 5 6 final V putVal(int hash, K key, V value, boolean onlyIfAbsent, 7 boolean evict) { 8 Node<K,V>[] tab; Node<K,V> p; int n, i; 9 / / steps (1) : the TAB is empty, create 10 if ((TAB = table) = = null | | (n = TAB. Length) = = 0) 11 n = (TAB = the resize ()). The length; 13 if ((p = TAB [I = (n-1) & hash]) == null) 14 TAB [I] = newNode(hash, key, value, null); 15 else { 16 Node<K,V> e; K k; 17 / / steps (3) : the key nodes exist, direct cover 18 if the value (p.h ash = = hash && 19 ((k = p.k ey) = = key | | (key! = null && key.equals(k)))) 20 e = p; 21 // Step ④ : Else if (p instanceof TreeNode) 23 e = ((TreeNode<K,V>)p). PutTreeVal (this, TAB, hash, key, value); Else {26 for (int binCount = 0; ; ++binCount) { 27 if ((e = p.next) == null) { 28 p.next = newNode(hash, key,value,null); 29 if (binCount >= treeIFy_threshthreshold -1) // -1 for 1st 30 treeifyBin(TAB, hash); 31 break; 32} / / the key already exists directly covering the value of 33 if (e.h ash = = hash && 34 ((k = e.k ey) = = key | | (key! = null && key.equals(k)))) 35 break; 36 p = e; 37 } 38 } 39 40 if (e ! = null) { // existing mapping for key 41 V oldValue = e.value; 42 if (! onlyIfAbsent || oldValue == null) 43 e.value = value; 44 afterNodeAccess(e); 45 return oldValue; 46 } 47 } 48 ++modCount; 49 // Step ⑥ : If (++size > threshold) 51 resize(); 52 afterNodeInsertion(evict); 53 return null; 54}Copy the code3. Capacity expansion mechanism
Resize is the process of adding more and more elements to a HashMap. When the array inside a HashMap cannot hold any more elements, the object needs to increase the array size to accommodate more elements. Of course, arrays in Java cannot be automatically expanded by replacing a small array with a new one, just as we use a small bucket of water to hold more water, so we have to replace it with a larger bucket.
We analyze the source code of resize, in view of JDK1.8 into red black tree, more complex, in order to facilitate understanding we still use JDK1.7 code, easy to understand some, there is no big difference in nature, specific differences later in the article again.
1 void resize(int newCapacity) {// enter a newCapacity. 2 Entry[] oldTable = table; // Reference the Entry array before capacity expansion 3 int oldCapacity = oldtable. length; 4 if (oldCapacity == MAXIMUM_CAPACITY) {// If the array size before capacity expansion has reached the maximum (2^30) 5 threshold = integer.max_value; // Change the threshold to the maximum value of int (2^31-1), so that it will not be expanded later. 7 } 8 9 Entry[] newTable = new Entry[newCapacity]; // Initialize a new Entry array 10 Transfer (newTable); / /!!!!! 11 table = newTable; // The table attribute of the HashMap refers to a new Entry array 12 threshold = (int)(newCapacity * loadFactor); // Change threshold 13}Copy the codeThe transfer() method copies the elements of the original Entry array to the new one by replacing the existing one with a larger one.
1 void transfer(Entry[] newTable) { 2 Entry[] src = table; // SRC references the old Entry array 3 int newCapacity = newtable.length; 4 for (int j = 0; j < src.length; J ++) {// Iterate through the old Entry array 5 Entry<K,V> e = SRC [j]; // Get each element of the old Entry array. = null) { 7 src[j] = null; 8 do {9 Entry<K,V> next = e.next; 10 int i = indexFor(e.hash, newCapacity); / /!!!!! Recalculate the position of each element in the array 11 e.ext = newTable[I]; // mark [1] 12 newTable[I] = e; // Place elements on array 13 e = next; // Access the next Entry chain element 14} while (e! = null); 15} 16} 17}Copy the codeThe reference to newTable[I] is assigned to e.ext, which uses single-linked header insertion, where new elements are always placed at the head of the list. Elements placed on an index will end up at the end of the Entry chain (if a hash conflict occurs), unlike Jdk1.8, which will be explained below. Elements in the same Entry chain in the old array may be placed in different positions in the new array after recalculation of index positions.
The following is an example to illustrate the expansion process. Suppose our hash algorithm simply mod the table size (that is, the length of the array) with a key. Hash bucket array table size=2, so key = 3, 7, 5, put order 5, 7, 3. All conflicts in table[1] after mod 2. Assume that loadFactor=1, that is, when the actual size of the key-value pair is greater than the actual size of the table, the capacity is expanded. The next three steps are the hash bucket array resize to 4, and then all nodes rehash.
Let’s take a look at some of the optimizations for JDK1.8. It is observed that we are using an extension of two powers, so that the element is either in its original position or moved by two powers from its original position. N is the length of the table. Figure (a) shows the example of determining the index position of key1 and KEY2 before capacity expansion. Figure (b) shows the example of determining the index position of key1 and KEY2 after capacity expansion.
After the element recalculates the hash, the mask range of n-1 is 1bit more (red) at the high end, so the new index will look like this:
Therefore, when we extend the HashMap, we don’t need to recalculate the hash as we did in JDK1.7. We just need to see if the new bit is 1 or 0. 0 is the same index, and 1 is old index +oldCap. You can see the resize from 16 to 32 below:
This design is indeed very clever, not only saves the time to recalculate the hash value, but also because the resize process can be considered random whether the new 1bit is 0 or 1, so the resize process evenly distributes the previously conflicting nodes to the new bucket. This is the new optimization point for JDK1.8. In JDK1.7, the list element will be inverted if the index position of the new table is the same as that of the old list. Resize JDK1.8 resize JDK1.8 resize
1 final Node<K,V>[] resize() { 2 Node<K,V>[] oldTab = table; 3 int oldCap = (oldTab == null) ? 0 : oldTab.length; 4 int oldThr = threshold; 5 int newCap, newThr = 0; 8 if (oldCap >= MAXIMUM_CAPACITY) {9 threshold = integer.max_value; 10 return oldTab; 11} 12 // Does not exceed the maximum, Else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && 14 oldCap >= DEFAULT_INITIAL_CAPACITY) 15 newThr = oldThr << 1; // double threshold 16 } 17 else if (oldThr > 0) // initial capacity was placed in threshold 18 newCap = oldThr; 19 else { // zero initial threshold signifies using defaults 20 newCap = DEFAULT_INITIAL_CAPACITY; 21 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); 24 if (newThr == 0) {25 26 float ft = (float)newCap * loadFactor; 27 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? 28 (int)ft : Integer.MAX_VALUE); 29 } 30 threshold = newThr; 3@SuppressWarnings ({"rawtypes", "unchecked"}) 32 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; 33 table = newTab; 34 if (oldTab ! = null) {36 for (int j = 0; j < oldCap; ++j) { 37 Node<K,V> e; 38 if ((e = oldTab[j]) ! = null) { 39 oldTab[j] = null; 40 if (e.next == null) 41 newTab[e.hash & (newCap - 1)] = e; 42 else if (e instanceof TreeNode) 43 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); 45 Node<K,V> loHead = null, loTail = null; 45 else {// List optimization rehash code block 45 Node<K,V> loHead = null, loTail = null; 46 Node<K,V> hiHead = null, hiTail = null; 47 Node<K,V> next; 48 do { 49 next = e.next; If ((e.hash & oldCap) == 0) {52 if (loTail == null) 53 loHead = e; 54 else 55 loTail.next = e; 56 loTail = e; OldCap 59 else {60 if (hiTail == null) 61 hiHead = e; 62 else 63 hiTail.next = e; 64 hiTail = e; 65 } 66 } while ((e = next) ! = null); 68 if (loTail! = null) { 69 loTail.next = null; 70 newTab[j] = loHead; If (hiTail! = null) { 74 hiTail.next = null; 75 newTab[j + oldCap] = hiHead; 76 } 77 } 78 } 79 } 80 } 81 return newTab; 82}Copy the codeThread safety
In multithreaded usage scenarios, try to avoid using a thread-safe HashMap and use a thread-safe ConcurrentHashMap instead. So why is HashMap thread unsafe? Here’s an example of how using HashMap in concurrent multithreaded usage scenarios can cause an infinite loop. Here is an example of the code (easy to understand, still using JDK1.7) :
Public class HashMapInfiniteLoop {private static HashMap<Integer,String> map = new HashMap<Integer,String>(2, 0.75f); Public static void main(String[] args) {map.put(5, "C"); new Thread("Thread1") { public void run() { map.put(7, "B"); System.out.println(map); }; }.start(); new Thread("Thread2") { public void run() { map.put(3, "A); System.out.println(map); }; }.start(); }}Copy the codeLoadFactor =0.75, threshold=2*0.75=1, that is, when the second key is put, the map needs to be resized.
Debug thread 1 and thread 2 simultaneously to the first line of the Transfer method (section 3.3 block) by setting a breakpoint. Notice that at this point both threads have successfully added data. Release thread1 breakpoints to transfer method’s “Entry Next = E.next;” This line; Then release the breakpoint on thread 2 and let thread 2 resize. The result is shown below.
Note that e of Thread1 points to key(3) and next points to key(7), which, after thread two rehash, points to the reassembled list of thread two.
As soon as the thread is scheduled to execute, newTalbe[I] = e, then e = next, causes E to point to key(7), and next = e.next causes next to point to key(3).
E.ext = newTable[I] causes key(3). Next points to key(7). Note that key(7).next already points to key(3), and the circular list appears.
So, when we call map.get(11) with the thread, the tragedy appears — Infinite Loop.
Performance comparison between JDK1.8 and JDK1.7
In HashMap, if the array index positions of the key obtained by the hash algorithm are all different, that is, the hash algorithm is very good, then the time complexity of getKey method is O(1), if the result of the hash algorithm technology is very many collisions, if the hash algorithm is extremely poor, All Hash algorithms result in the same index position, so that all key-value pairs are grouped in a bucket, or in a linked list, or in a red-black tree, with time complexity of O(n) and O(LGN), respectively. Given that JDK1.8 has been optimized in many ways and overall performance is better than JDK1.7, let’s use two examples to prove this.
Hash evenly
For testing purposes, we’ll write a class Key as follows:
class Key implements Comparable<Key> {
private final int value;
Key(int value) {
this.value = value;
}
@Override
public int compareTo(Key o) {
return Integer.compare(this.value, o.value);
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass())
return false;
Key key = (Key) o;
return value == key.value;
}
@Override
public int hashCode() {
return value;
}
}
Copy the codeThis class overwrites the equals method and provides a pretty good hashCode function. The hashCode of any value is never the same, since value is used directly as hashCode. To avoid frequent GC, I cache the invariant Key instances instead of creating them over and over again. The code is as follows:
public class Keys { public static final int MAX_KEY = 10_000_000; private static final Key[] KEYS_CACHE = new Key[MAX_KEY]; static { for (int i = 0; i < MAX_KEY; ++i) { KEYS_CACHE[i] = new Key(i); } } public static Key of(int value) { return KEYS_CACHE[value]; }}Copy the codeNow to start our experiment, all we need to do is create a HashMap of different sizes (1, 10, 100… 10000000), shielding the capacity expansion, the code is as follows:
static void test(int mapSize) { HashMap<Key, Integer> map = new HashMap<Key,Integer>(mapSize); for (int i = 0; i < mapSize; ++i) { map.put(Keys.of(i), i); } long beginTime = System.nanoTime(); For (int I = 0; i < mapSize; i++) { map.get(Keys.of(i)); } long endTime = System.nanoTime(); System.out.println(endTime - beginTime); } public static void main(String[] args) { for(int i=10; i<= 1000 0000; i*= 10){ test(i); }}Copy the codeTo calculate the average getKey time, we iterate over all the get methods, calculate the total time, divide by the number of keys, and calculate an average, mainly for comparison. Absolute values can be affected by many environmental factors. The results are as follows:
According to the observation test results, JDK1.8’s performance is more than 15% higher than JDK1.7, and even more than 100% in some size areas. Since the Hash algorithm is uniform, the effect of red-black tree introduced in JDK1.8 is not obvious. Let’s look at the case where the Hash algorithm is not uniform.
Hash is extremely uneven
Let’s say we have another very bad Key, and all of their instances return the same hashCode value. This is the worst case scenario for using HashMap. The code is modified as follows:
class Key implements Comparable<Key> { //... @Override public int hashCode() { return 1; }}Copy the codeThe main method is still executed, and the result is shown in the following table:
As can be seen from the results in the table, with the increase of size, the time spent on JDK1.7 tends to increase, while JDK1.8 tends to decrease significantly and shows a steady logarithmic growth. When a linked list becomes too long, the HashMap dynamically replaces it with a red-black tree, which reduces the time complexity from O(n) to O(logn). The time taken by a uniform hash algorithm is obviously different from that taken by an uneven hash algorithm. A comparison between the two cases illustrates the importance of a good hash algorithm.
Test environment: CPU: 2.2 GHz Intel Core I7, memory: 16 GB 1600 MHz DDR3, SSD, default JVM parameters, and running 64-bit OS X 10.10.1.
summary
- Scaling is a particularly performance intensive operation, so when using a HashMap, programmers estimate the size of the map and give it a rough value during initialization to avoid frequent scaling of the map.
- The load factor can be modified and can be greater than 1, but it is not recommended to change it unless the situation is very special.
- HashMap is not thread-safe. Do not operate HashMap simultaneously in a concurrent environment. ConcurrentHashMap is recommended.
- The introduction of red-black trees in JDK1.8 greatly optimizes the performance of HashMap.
- If you haven’t upgraded JDK1.8 yet, start upgrading now. The performance improvements of HashMap are just the tip of the iceberg for JDK1.8.
reference
- JDK1.7 & JDK1.8 source code.
- CSDN Blog channel, HashMap Multithreaded Dead-loop problem, 2014.
- Red and black Alliance, Java class set framework HashMap(JDK1.8) source analysis, 2015.
- CSDN blog channel, give you an introduction to red black trees, 2010.
- Java Code Geeks, HashMap performance improvements in Java 8,2014.
- Importnew, danger! Using mutable objects as keys in a HashMap, 2014.
- CSDN Blog channel, why the general hashtable bucket number will take a prime number, 2013.