Shulou(Shulou.com)06/02 Report--

Today, I will talk to you about how to write the HashMap source code, many people may not know much about it. In order to make you understand better, the editor has summarized the following content for you. I hope you can get something according to this article.

Source code learning, while watching the source code while adding comments, while debug, while understanding.

Basic attribute constant

DEFAULT_INITIAL_CAPACITY: the initial capacity of the default array-must be a power of 2.

MAXIMUM_CAPACITY: maximum capacity of the array

DEFAULT_LOAD_FACTOR: load factor of hash table 0.75

TREEIFY_THRESHOLD: the threshold for converting a tree to a linked list in a bucket

UNTREEIFY_THRESHOLD: the threshold for converting another tree to a linked list

MIN_TREEIFY_CAPACITY: the linked list will be converted into a tree only when the array length is greater than or equal to 64, otherwise the capacity will be expanded directly.

Global variable

Table: array object

Size:HashMap Siz

ModCount: the total number of operations HashMap for fast-fail

Threshold: threshold for capacity expansion

LoadFactor: the load factor of the hash table. Default is DEFAULT_LOAD_ fact value.

Data structure

The data structure of HashMap uses array + linked list before jdk1.8, and array + linked list / red-black tree structure after jdk1.8, as shown in the figure:

As shown in the figure, when the length of the linked list is greater than 8, the linked list is converted to a red-black tree.

There are two types of nodes that store data in jdk1.8: a linked list node Node and a tree node TreeNode:

Node:static class Node implements Map.Entry {final int hash; final K key; V value; Node next;...TreeNode: static final class TreeNode extends LinkedHashMap.Entry {TreeNode parent; / / red-black tree links TreeNode left; TreeNode right; TreeNode prev; / / needed to unlink next upon deletion boolean red;...

From the inheritance relationship above, we find that TreeNode inherits from Node.

If the number of elements is less than 8, the cost of linked list query is high, and the new cost is low. If the number of elements is greater than 8, the query cost of red-black tree is low, and the new cost is high.

Common usage @ Test public void testHashMap () {Map map = new HashMap (); map.put ("1", "1"); map.get ("1"); map.size ();}

This is the most common way we use HashMap, so let's take a look at how each step is implemented. Test the code:

Public class HashMapTest {public static void main (String [] args) {Map map = new HashMap (); for (;;) {map.put (new User (), map.size ()); if (map.size () > 1000) {break;}} map.size () } static class User {@ Override public int hashCode () {return 1;} constructor

The first step in using HashMap is to create a HashMap. From the above statement, HashMap inherits from the Map interface. Let's take a look at what new HashMap () has done:

Public HashMap () {this.loadFactor = DEFAULT_LOAD_FACTOR; / / all other fields defaulted}

It turns out that I did nothing but assign an initial value to a member variable. It seems that the initialization of arrays and linked lists takes place later.

Put () method public V put (K key, V value) {return putVal (hash (key), key, value, false, true);} hash () method static final int hash (Object key) {int h; / / calculates key.hashCode () and reduces the higher hash extension (XOR). The main purpose of bit operation is to speed up the calculation of return (key = = null)? 0: (h = key.hashCode ()) ^ (h > 16);} putVal () method final V putVal (int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {/ / array object Node [] tab / / find out the data of the corresponding array index bits by the key value p = tab [I = (n-1) & hash] Node p; / / n represents the array length, and I represents the index bit int n, I of the key value on the array. If ((tab = table) = = null | | (n = tab.length) = = 0) / / determine whether the array is null. If so, call the resize () method to initialize n = (tab = resize ()) .length If ((p = tab [I = (NMur1) & hash]) = = null) / / (NMur1) & hash= hash% (NMur1), find out the index bit of the value on the array through this formula. Make sure that the array does not cross the bounds. / / if the index bit is null, put the data directly to the index bit tab [I] = newNode (hash, key, value, null); else {Node e; K k If (p.hash = = hash & & (k = p.key) = = key | | (key! = null & & key.equals (k) / / indicates that the key is exactly the same e = p The else if (p instanceof TreeNode) / / bucket is already a red-black tree node e = ((TreeNode) p) .putTreeVal (this, tab, hash, key, value), else {/ / bucket or linked list node for (int binCount = 0; + + binCount) {if ((e = p.next) = = null) {/ / find the tail node by spinning and add the new data after the tail node p.next = newNode (hash, key, value, null) If (binCount > = TREEIFY_THRESHOLD-1) / /-1 for 1st / / if there are more than 8 data in the linked list, try to convert the linked list into a red-black tree (in fact, the linked list already has 9 nodes, and the last node was added in the previous step) treeifyBin (tab, hash) Break;} if (e.hash = = hash & & (k = e.key) = = key | | (key! = null & & key.equals (k) / / key is exactly the same, then follow the value replacement process break P = e;}} if (e! = null) {/ / existing mapping for key V oldValue = e.value If (! onlyIfAbsent | | oldValue = = null) / / when the key is exactly the same, overwrite the value of the old data with the new data and return the value of the old data e.value = value; afterNodeAccess (e); return oldValue;}} + + modCount / / determine if the total number of hash tables is greater than the expansion threshold, you need to expand if (+ + size > threshold) resize (); afterNodeInsertion (evict); return null } putTreeVal () insert red-black tree node final TreeNode putTreeVal (HashMap map, Node [] tab, int h, K k, V v) {Class kc = null; boolean searched = false; / / find the root node TreeNode root = (parent! = null)? Root (): this; for (TreeNode p = root;;) {/ / dir represents the comparison result of two key, ph indicates the hash value of p node int dir, ph; K competes If ((ph = p.hash) > h) / / the hash value of the parent node is greater than the hash value of the new node dir =-1; the hash value of the else if (ph < h) / / parent node is less than the hash value of the new node dir = 1 Else if ((Competition = p.key) = = k | (k! = null & & k.equals (Competition)) / / indicates that key is exactly the same as return p Else if ((kc = = null & & / / determine whether to implement the Comparable interface for key (kc = comparableClassFor (k)) = = null) | | / use Comparable to compare the key values of the parent node and the new node (dir = compareComparables (kc K, competitive)) = 0) {/ / this lookup will only be performed once if (! searched) {TreeNode Q, ch Searched = true / / find the corresponding key node if ((ch = p.left)! = null & & (Q = ch.find (h, k)) from the left subtree of p Kc)! = null) | | / / find the node corresponding to key from the right subtree of p ((ch = p.right)! = null & & (Q = ch.find (h, k) Kc)! = null)) / / indicates the node return Q that has exactly the same key } / / use the default comparator to compare the size of the two key dir = tieBreakOrder (k, contention);} TreeNode xp = p; / / spin to find the parent node if of the new node (p = (dir)

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.