A preface
This is the second source code analysis following the core ArrayList, promise me to read it every day, ok? By the end of this article you will have a thorough understanding of the structure and methods of hashMap; Superman doesn’t know how strong he is in the interview. For example, the expansion mechanism of HashMap, what is the maximum capacity of HashMap, how to transfer HashMap linked list to red-black tree, why HashMap thread is not safe, whether HashMap key,value can be null, etc.
Inheriting the spirit of open Source, Spreading technology knowledge;
Ii Source code Analysis
2.1 Official description of practice
- **HashMap implements the Map interface and has all Map operations. And allow both key and value to be null; ** Practice if this is the case;
public static void main(String[] args) {
HashMap<String, Object> map = new HashMap<>();
map.put(null.null);
System.out.println(map);//{null=null}
}
Copy the codeSure enough, there was no error; Add a null key and value and let’s see; {null=null}; Note The key of a HashMap is unique. ? How to ensure that the key is unique
- HashMap differs from HashTable in that HashMap is not synchronized and HashTable does not allow null keys and values. Practice a
public static void main(String[] args) {
Hashtable hashtable = new Hashtable();
hashtable.put(null.null);
}
Copy the codeConsole is red!! The key and value of a HashTable cannot be null.
{null=null}Exception in thread "main"
java.lang.NullPointerException
at java.util.Hashtable.put(Hashtable.java:459)
at test.HashMapTest.main(HashMapTest.java:17)
Process finished with exit code 1
Copy the codeHashTable’s put method starts with an oversized Make to ensure that keys and values cannot be null and synchronized. Life is doubtful because no knowledge seeker has ever experimented with Hashtable code before;
public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.Entry<? ,? > tab[] = table;int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
Copy the code- Continuing with the official description, HashMap does not guarantee the order of the contents in the Map; Try again, if so, what is causing the map order to be inconsistent? Subsequent analysis
public static void main(String[] args) {
HashMap<String, Object> map = new HashMap<>();
map.put("Morning"."The baby cried.");
map.put("Noon"."Baby hungry.");
map.put("Night"."Baby doesn't want to sleep.");
System.out.println(map);//{noon = baby hungry, night = baby don't want to sleep, morning = baby cry}
}
Copy the codeThe subsequent official explanation is not only can a few words can describe the understanding, appetizers over, or look at the specific source code, review when remember to look at the Tip;
Tip:
HashMap allows both key and value to be null; Key is unique;
HashMap differs from HashTable in that HashMap is not synchronized and HashTable does not allow null keys and values.
A HashMap does not guarantee the order of the contents in the Map
2.2 Analysis of empty parameter construction method
The test code
public static void main(String[] args) {
HashMap<String, Object> map = new HashMap<>();
}
Copy the codeThe default value of loadFactor for the HashMap is 0.75.
public HashMap(a) {// DEFAULT_LOAD_FACTOR=0.75; The initial capacity is 16
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
Copy the codeGo through the parent class as follows
HashMap –> AbstractMap –> Object
If you look at the parent of a HashMap, the structure is pretty simple, right?
As you see here, the knowledge seeker has two questions
Question 1: What is load factor 0.75?
Question 2: Where is the initial capacity 16?
To answer the initial capacity 16 question, the knowledge seeker finds the member variable and the default initial capacity field value is 16; The default initialization value must be a multiple of 2;
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 default initialization capacity
Copy the codeAnswer load factor 0.75 refers to a HashMap expansion mechanism; For example, if the expansion factor is 0.7, let’s say the capacity is 10; When the inserted data reaches the 10th *0.7 = 7, expansion will occur; Then the knowledge seeker calculates the HashMap expansion algorithm, 0.75 * 16 = 12; So the HashMap expands after 12 numbers are inserted;
Tip: HashMap default factor 0.75; Initialize capacity 16. If the initial capacity is 12, data expansion occurs after 12 numbers are inserted.
2.3 Implementation principle analysis of HashMap
HashMap is implemented by buckets and hash tables. If the bucket is too large, it will be converted to a tree.
Throw up the question what is a bucket?
Before we answer buckets, let’s look at what a HashTable is.
A hash table is essentially a linked list array; The Hash algorithm calculates the int value to find the corresponding position in the array; Throw a picture to the reader;
The knowledge seeker is really worried for the reader, throw you another method to calculate the hash value; Remember to brush up on the hashCode() method of Java’s basic String class; If the two objects are the same, the hash value is the same. If two strings have the same content (equals method), the hash value is the same.
public static void main(String[] args) {
int hash_morning = Objects.hashCode("Morning");
int hash_night = Objects.hashCode("Night");
System.out.println("Morning hash value :"+hash_morning);// Morning hash value :899331
System.out.println("Hash value for the night :"+hash_night);// Hash value of the evening :832240
}
Copy the codeMoving on to buckets, a bucket is each node in a linked list, which you can also interpret as an entry in the figure below, except for the TAB entry; Look at the picture
When the bucket capacity reaches a certain number, it turns into a red black tree. Look at the picture
See here readers must have gained a lot, this is still an appetizer, into our main topic today, source code analysis;
2.4 PUT method source analysis
The test code
public static void main(String[] args) {
HashMap<String, Object> map = new HashMap<>();
map.put("Morning"."The baby cried.");
System.out.println(map);
}
Copy the codeSo the first thing that comes in is the put method which contains the putVal method
public V put(K key, V value) {
return putVal(hash(key), key, value, false.true);//
}
Copy the codeWe hash the key first and then the hash in putVal
static final int hash(Object key) {
int h;
return (key == null)?0 : (h = key.hashCode()) ^ (h >>> 16);
}
Copy the codeLook at the putVal method content, because you’re only inserting one data, and if the index is empty you’re not going to do else, the knowledge seeker is omitted here;
You can clearly see that a Node (Node
below) has been created and placed in a TAB. TAB is a list of nodes. Its index I = (capacity -1) &hash value, which is essentially the result of the hash value taken and, so it is a hash table;
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {//evict =true
Node<K,V>[] tab; Node<K,V> p; int n, i;// Declare tree array, tree node, n, I
if ((tab = table) == null || (n = tab.length) == 0)/ / table is empty
n = (tab = resize()).length; // resize() is Node
[] resize() n is the size of the tree
,v>
if ((p = tab[i = (n - 1) & hash]) == null) // I = (16-1) &hash --> 15&899342 = 14;
tab[i] = newNode(hash, key, value, null);// Create a new node and insert data
else{... } ++modCount;// Set structure changes +1
if (++size > threshold)// size=1 ; threshold=12
resize();
afterNodeInsertion(evict);
return null;
}
Copy the codeAnd I drew a little picture here for the record
The Node code is as follows
static class Node<K.V> implements Map.Entry<K.V> {
final int hash;// Hash value Key value Specifies the xor hash value
final K key;/ / key
V value;/ / value
Node<K,V> next;// Store the next node
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final int hashCode(a) {
returnObjects.hashCode(key) ^ Objects.hashCode(value); }...Copy the codeThe knowledge seeker added another night, ran through the code and turned it into the picture below
So the knowledge seeker came up with the idea that the binary of 15 is 1111, and then xor any key or value hash to get the Node hash and then match it with the original 1111, which is the last four bits of the Node hash; TAB has a capacity of 16; After storing a Node, the size is increased by 1. At most, only 12 values can be stored. In this case, as long as the hash value is the same, there will be a collision, and then there will be an else method, and the problem is how to construct two identical Node hashes; Examples are given as follows:
Reference link: blog.csdn.net/hl_java/art…
public static void main(String[] args) {
System.out.println(HashMapTest.hash("Aa"));/ / 2112
System.out.println(HashMapTest.hash("BB"));/ / 2112
}
static final int hash(Object key) {
int h;
return (key == null)?0 : (h = key.hashCode()) ^ (h >>> 16);
}
Copy the codeIf the hash value of the key is the same, the else method will be used, and a Node will be added to the original AA Node property next to store Bb. Wow, that’s an entry list
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {//evict =true
Node<K,V>[] tab; Node<K,V> p; int n, i;// Declare tree array, tree node, n, I
if ((tab = table) == null || (n = tab.length) == 0)/ / table is empty
n = (tab = resize()).length; // resize() is Node
[] resize() n is the length of Node based on the initial capacity
,v>
if ((p = tab[i = (n - 1) & hash]) == null) // I = (16-1) &hash --> 15&hash
tab[i] = newNode(hash, key, value, null);// Create a new node and insert data
else {
Node<K,V> e; K k; // Declare node k
if (p.hash == hash && // select * from node where Aa-->a; hash 2112((k = p.key) == key || (key ! =null && key.equals(k))))// The key content is not the same, so it is not the same node
e = p;
else if (p instanceof TreeNode)// p is not a TreeNode
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) { // The default number of buckets is 0
if ((e = p.next) == null) { // Assign the next Node of p to e as null; The beginning of a linked list
p.next = newNode(hash, key, value, null);// P create a node to store BB--> b
TREEIFY_THRESHOLD = 8
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);/ / tree
break;
}
if (e.hash == hash && // Check whether p and e are the same Node((k = e.key) == key || (key ! =null && key.equals(k))))
break; p = e; }}if(e ! =null) { // existing mapping for key
V oldValue = e.value;
if(! onlyIfAbsent || oldValue ==null)
e.value = value;// The new value will replace the old value
afterNodeAccess(e);
return oldValue;
}
}
++modCount;// Set structure changes +1
if (++size > threshold)// size=1 ; threshold=12
resize();
afterNodeInsertion(evict);
return null;
}
Copy the codeIf the hash value of the key is the same, a linked list will be formed. Besides the first Entry on the Tab, the Node of each subsequent Entry is a bucket. TreeifyBin (TAB, hash) is called if the key hash value reaches 8 the same number of times; The knowledge seeker understands that the list nodes will be treed as long as the number of buckets reaches 8; This is array + linked list (each list node is a bucket) –> array + red-black tree; Why should the linked list be turned into a red-black tree? It takes into account the efficiency of the algorithm, the time complexity of the linked list is O (n), while the time complexity of the red-black tree is O (logn), the tree search efficiency is higher;
Tip: A hashMap is essentially a list of hash tables; Hash table first consists of array + linked list; When the hash is collided, a linked list is formed, and each node of the list is a bucket. When the number of buckets reaches 8, the tree will be carried out, and the linked list will be transformed into a red-black tree. In this case, the HashMap structure is array + red-black tree. If the same key is inserted, the new value replaces the old value.
2.5 Source code analysis for expansion
The test code
public static void main(String[] args) {
HashMap<String, Object> map = new HashMap<>(12);
}
Copy the codeStart with the HashMap initialization code
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);// Capacity 12, load factor 0.75
}
Copy the codeLook inside the constructor; Quite simply, the maximum capacity of a HashMap is 2 to the 30th power; Secondly, since the input number is 12, not 2, it will be expanded, and the result of the expansion is also very simple: the power of 2 is larger than the output value; The power of 2 greater than 12 is 16;
public HashMap(int initialCapacity, float loadFactor) {/ / initialCapacity = 12, loadFactor = 0.75
if (initialCapacity < 0)If the capacity is less than 0, an invalid parameter exception is thrown
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)// MAXIMUM_CAPACITY = 1<<30; Remember a hashMap biggest
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor)) // loadFactor=0.75>0, otherwise an invalid parameter exception is thrown
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;// Load factor assignment
this.threshold = tableSizeFor(initialCapacity);// Return a capacity of 2 power length; Threshold = 16
}
Copy the codeClick here to see what tableSizeFor(initialCapacity) is; Multiple unsigned right bits or operations; The purpose is to construct a 2 power 1; Very simple calculation, the reader can calculate;
static final int tableSizeFor(int cap) {//cap=12
int n = cap - 1;// n =11
n |= n >>> 1;// The result of an unsigned shift of 1 bit to the right is phase or with 11; n=15
n |= n >>> 2;//n=15
n |= n >>> 4;//n=15
n |= n >>> 8;//n=15
n |= n >>> 16;//n=15
return (n < 0)?1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;/ / 15 + 1 = 16
}
Copy the codeTip: The HashMap expansion mechanism is the first second power larger than the input capacity value
2.6 GET source code analysis
The test code
public static void main(String[] args) {
HashMap<String, Object> map = new HashMap<>(12);
map.put("a"."b");
map.get("a");
}
Copy the codeGet method
public V get(Object key) {
Node<K,V> e;// Declare Node e
return (e = getNode(hash(key), key)) == null ? null : e.value;// Get Node based on the hash of key
}
Copy the codeEnter the getNode(hash(key), key) method, you can see that the entry node on the TAB is preferentially selected. If not, it will enter the linked list or red-black tree to traverse and compare hash values to obtain nodes. If you look at the PUT source, there’s no singularity in the GET source;
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;// Declare the array of nodes TAB, first, e; n ,k
if((tab = table) ! =null && (n = tab.length) > 0 &&// tab.length =16 indicates the capacity
(first = tab[(n - 1) & hash]) ! =null) { // The same hash value as get; Hash = (capacity -1) & hash yields TAB index; Then get the index value and assign it to first
if (first.hash == hash && // always check first node((k = first.key) == key || (key ! =null && key.equals(k))))// Check if it is enrty on TAB. If it is, return Node
return first;
if((e = first.next) ! =null) {
if (first instanceof TreeNode)// If it is a red-black tree, the node is traversed
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k))))
return e;
} while((e = e.next) ! =null);// Otherwise loop through the list to get the node}}return null;
}
Copy the code2.7 hashCode source code analysis
The test code
public static void main(String[] args) {
HashMap<String, Object> map = new HashMap<>(12);
map.put("a"."b");
map.put("b"."c");
int hashCode = map.hashCode();
System.out.println(hashCode);/ / 4
}
Copy the codeTo enter hashCode, you iterate over the hash values of each entrySet and add them as hash values for the HashMap
public int hashCode(a) {
int h = 0;
Iterator<Entry<K,V>> i = entrySet().iterator();/ / the iterator
while (i.hasNext())
h += i.next().hashCode();// Iterate over the hash values of each entrySet
return h;
}
Copy the codeTo do a test
public static void main(String[] args) {
HashMap<String, Object> map = new HashMap<>(12);
map.put("a"."b");
map.put("b"."c");
Set<Map.Entry<String, Object>> entries = map.entrySet();
entries.stream().forEach(entry->{
System.out.println(entry.hashCode());
});
}
Copy the codeThe output is 1,3;
Tip: The hashCode of a HashMap is the sum of hash values of an entry. The hash value of a Node is the sum of hash values of a key and value.
Three summary
- HashMap allows both key and value to be null; Key is unique;
- HashMap differs from HashTable in that HashMap is not synchronized and HashTable does not allow null keys and values.
- A HashMap does not guarantee the order of the contents in the Map
- HashMap default factor 0.75; Initialize capacity 16. If the specified capacity is 12, data expansion occurs after 12 numbers are inserted.
- A hashMap is essentially a list of hash tables; Hash table first consists of array + linked list; When the hash is collided, a linked list is formed, and each node of the list is a bucket. When the number of buckets reaches 8, the tree will be carried out, and the linked list will be transformed into a red-black tree. In this case, the HashMap structure is array + red-black tree. If the same key is inserted, the new value replaces the old value.
- The HashMap expansion mechanism is the first second power larger than the input capacity value; For example, 12 becomes 16 after expansion; 17 is 32;
- The hashCode of a HashMap is the hash value of an entry. The hash value of a Node is the sum of the hash values of a key and a value.