This paper mainly analyzes the following problems of HashMap, from the shallow to the deep, from the use to the principle, from top to bottom, and from top to bottom.
-
What is a HashMap?
-
How to use HashMap?
-
How to implement the source code for several important methods of HashMap?
-
What is the difference between HashMap 1.7 and 1.8?
1. What exactly is a HashMap?
A HashMap is a thread-unsafe out-of-order hash derived from AbstractMap that implements both Map and Serializable interfaces, internally storing key-value pairs according to the hashCode of the key.
2. How to use HashMap?
Using HashMap is very simple, as follows:
public class HashMapActivity extends AppCompatActivity {
@Override
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_hash_map);
HashMap<String, String> hashMap = new HashMap();
hashMap.put("k"."v");
hashMap.put("k2"."v2");
hashMap.put("k3"."v3");
for (Map.Entry<String, String> entries : hashMap.entrySet()) {
Log.d("TAG"."key:" + entries.getKey() + " value:"+ entries.getValue()); }}} Log 2019-12-12 18:35:23.378 11510/com.test D/TAG: K2 value:v2 2019-12-12 18:35:23.378 11510-11510/com.test D/TAG: k2 value:v2 2019-12-12 18:35:23.378 11510-11510/com.test D/TAG: Key :k3 value:v3 2019-12-12 18:35:23.378 11510-11510/com.test D/TAG: key:k value:vCopy the codeThe above log output shows the disorder of the HashMap data store.
3. How are several important methods of HashMap implemented?
Let’s analyze exactly what each method is doing in terms of the order in which the HashMap is used.
3.1. A HashMap needs to be instantiated using a constructor before it is used. What does the constructor of a HashMap do?
/** * Create a HashMap object with a default initial capacity and load factor of 0.75 */ publicHashMap() {// The default value is 0.75. This variable is used to trigger capacity expansion. When the HashMap storage exceeds 75% of the preset capacity, capacity expansion is triggered. this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted} /** * create a HashMap object with an initialCapacity of initialCapacity and a default load factor of 0.75 * @param initialCapacity initialize capacity, */ public HashMap(int initialCapacity) {this(initialCapacity, int initialCapacity, int initialCapacity, int initialCapacity, int initialCapacity, int initialCapacity, int initialCapacity, DEFAULT_LOAD_FACTOR); } /** * create a HashMap object with an initialCapacity of initialCapacity and a loadFactor of loadFactor. * * @param initialCapacity initialCapacity * @param loadFactor loadFactor * @throws IllegalArgumentException This exception is thrown if either the initial capacity or the loadFactor is negative. */ public HashMap(int initialCapacity,float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: "+ initialCapacity); // initialCapacity = 2^30 if the initialCapacity is greater than 2^30if(initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; // Throw an exception if loadFactor is negative or non-numericif (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: "+ loadFactor); this.loadFactor = loadFactor; This. threshold = tableSizeFor(initialCapacity); this.threshold = tableSizeFor(initialCapacity); } /** * create a HashMap that has the same mappings as the specified Map and has an initial capacity that is sufficient for the specified Map. The load factor is 0.75 ** @param m the Map whose mappings are to be placedin this map
* @throws NullPointerException if the specified map is null
*/
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
Copy the codeThe above constructor has been commented line by line, tableSizeFor(int cap) we expand the analysis.
Static final int tableSizeFor(int); static final int tableSizeFor(int)cap) {
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 codeSo before you look at this method you need to know the shift operations and the or operations, so let me just generalize them a little bit
- First, the computer only understands binary numbers. It thinks all data is made up of 0101010.
- For example, converting decimal 24 to base 2 is 11000
- The shift operation moves the base 2 data and adds 0, for example, 11000>>> 1 is 01100,01100 >>> 2 is 00010
- Or the operation is 1 if there’s one 1, 0 if there’s all 0.
- Ok, that’s it. Let’s look at the code up there.
- Quite simply, cap-1 is done first, in case the current input parameter is a power of 2 and returns twice as many.
- It’s all followed by an or operation and a shift budget. Following my logic above, I will find that the highest bit of the input parameter will eventually become 1.
- For example, if the input parameter is 25, 25-1 =24, and the binary value is 11000, it will become 11111, and finally return 11111+1, and finally return 32.
- In fact, the above method only returns the nearest 2 to the NTH power of the input parameter. For example, if the input parameter is 3, 4 is returned, and if the input parameter is 5, 8 is returned. Let’s write a demo to verify that
public class HashMapActivity extends AppCompatActivity {
@Override
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_hash_map);
Log.d("TAG"."tableSizeFor->:" + tableSizeFor(0));
Log.d("TAG"."tableSizeFor->:" + tableSizeFor(1));
Log.d("TAG"."tableSizeFor->:" + tableSizeFor(2));
Log.d("TAG"."tableSizeFor->:" + tableSizeFor(3));
Log.d("TAG"."tableSizeFor->:" + tableSizeFor(4));
Log.d("TAG"."tableSizeFor->:" + tableSizeFor(5));
}
final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return(n < 0) ? 1 : (n >= 1 << 30) ? 1 << 30 : n + 1; }} Log 2019-12-13 18:28:22.308 5512-5512/com.test D/TAG: TableSizeFor ->:1 2019-12-13 18:28:22.308 5512-5512/com.test D/TAG: TableSizeFor ->:1 2019-12-13 18:28:22.308 5512-5512/com.test D/TAG: TableSizeFor ->:2 2019-12-13 18:28:22.308 /com.test D/TAG: TableSizeFor ->:4 2019-12-13 18:28:22.308 5512-5512/com.test D/TAG: TableSizeFor ->:4 2019-12-13 18:28:22.308 5512-5512/com.test D/TAG: tableSizeFor->:8Copy the codeNew HashMap() : new HashMap()
- A. new HashMap() assigns local variables to the default value this.loadFactor = DEFAULT_LOAD_FACTOR;
- B. New HashMap(1) calls this.HashMap(1, DEFAULT_LOAD_FACTOR)
- C. New HashMap(1, 0.8) determines the initialCapacity and load factor compliance, and calls tableSizeFor(initialCapacity) to convert the initialCapacity to 2^n.
Add data to a HashMap using the PUT method. Let’s look at the PUT method
/**
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @returnReturn null if there is no previous data under the current key, otherwise return the previous old data. */ public V put(K key, V value) {return putVal(hash(key), key, value, false.true); } /** * store data * @paramhashCalculated by keyhashCode * @param key * @param Value Value * @param onlyIfAbsent If yestrueIf there is a value under this key, the original value is not replaced * @param evict if yesfalseIt indicates that the table is in create mode. * @returnReturn null */ final V putVal(int) if there was a value beforehash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; // If TAB is null or length 0, resize() creates a Node<K,V>[] and assigns it to TAB. // The resize() method will be analyzed separatelyif((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // If there is no data in the current key position, the current data is stored directly.if ((p = tab[i = (n - 1) & hash]) == null) // Use the newNode() method to create and store data. tab[i] = newNode(hash, key, value, null);
else{// If there is data at the current key position, this occurshashConflict. Node<K,V> e; K k; // Check whether the current key is the same as the old key, if the old key is the same, then assign the old key to local variable e.if (p.hash == hash&& ((k = p.key) == key || (key ! = null && key.equals(k)))) e = p; PutTreeVal (); // If there is a red-black tree, putTreeVal() is used to process the data. If there are identical keys, the old data is assigned to the local variable eelse if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else{// The structure of the current position is a linked list, so the current data is added after the loop.for(int binCount = 0; ; ++binCount) {// Add Node<K,V> to the end of the list if there is no duplicate keyif ((e = p.next) == null) {
p.next = newNode(hash, key, value, null); // Determine the length of the current list, if the length >=8 to convert to a red-black tree.if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break; } // If the current key is the same as the current key, exit the loop and replace it in the following logic.if (e.hash == hash&& ((k = e.key) == key || (key ! = null && key.equals(k))))break; // If the key is not the same, and the current is not the end of the list, continue the next loop p = e; }} // Replace the value operationif(e ! = null) { // existing mappingfor key
V oldValue = e.value;
if(! onlyIfAbsent || oldValue == null) e.value = value; //LinkedHashMap reserved method. afterNodeAccess(e);returnoldValue; } } ++modCount; // Determine capacity expansionif(++size > threshold) resize(); //LinkedHashMap reserved method. afterNodeInsertion(evict);returnnull; } /** * Insert/update data into the red black tree * Traverses the red black tree to determine whether the key of the node is the same as the key to be inserted, if so, return the old data, PutTreeVal (HashMap<K,V> map, Node<K,V>[] TAB, int h, K K,V V) {Class<? PutTreeVal (HashMap<K,V> map, Node<K,V>[] TAB, int h, K K,V V); > kc = null; boolean searched =false; TreeNode<K,V> root = (parent ! = null) ? root() : this;for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if((pk = p.key) == k || (k ! = null && k.equals(pk)))return p;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
if(! searched) { TreeNode<K,V> q, ch; searched =true;
if(((ch = p.left) ! = null && (q = ch.find(h, k, kc)) ! = null) || ((ch = p.right) ! = null && (q = ch.find(h, k, kc)) ! = null))return q;
}
dir = tieBreakOrder(k, pk);
}
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
Node<K,V> xpn = xp.next;
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
if (dir <= 0)
xp.left = x;
else
xp.right = x;
xp.next = x;
x.parent = x.prev = xp;
if(xpn ! = null) ((TreeNode<K,V>)xpn).prev = x; moveRootToFront(tab, balanceInsertion(root, x));returnnull; }}}Copy the codePut (); put(); It is mainly divided into the following 7 steps
- First, assign global variable table to local TAB and check whether TAB is null. If it is null, call resize() to initialize and create table.
- Run TAB [I = (n-1) & hash] to obtain the hashCode value of the current key. If the value is null, the Node
object store is created using newNode().
- If the position corresponding to the key hashCode is not null, a hash collision has occurred. If the inserted key is the same as the collided key, the object is directly replaced.
- If the data structure at the collision location is a red-black tree, if so, the data is processed by putTreeVal(). If any key is found to be identical, the old data is returned and assigned to the local variable E.
- If the data at the collision location results in a linked list, then the loop checks whether there is the same as the current key. If so, the old data is returned and assigned to E. If not, the loop goes to the end of the linked list and inserts new data. Then determine the list length, and if >=8 convert it to a red-black tree via treeifyBin().
- Determine the local variable e if! =null; afterNodeAccess() is used to determine whether to replace the old value with onlyIfAbsent. AfterNodeAccess () is null by default.
- Check whether the number of data is greater than the capacity expansion threshold. If so, call resize() to expand capacity. AfterNodeInsertion (), which defaults to empty, LinkedHashMap useful.
The resize() method is used in hashmap.put ().
/** * This function has two functions * 1. InitializationhashTable * 2. Expand * * @return the table
*/
final Node<K,V>[] resize() {// save the table; Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; // Save the capacity of the previous table. int oldThr = threshold; // Save the previous threshold (oldtab. length*load_factor) int newCap, newThr = 0; // If oldCap > 0, the previous table is not emptyif(oldCap > 0) {// If the length of the old table is greater than or equal to the maximum Integer value, set the threshold to integer. MAX_VALUE.if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
returnoldTab; } // If the capacity is < the maximum integer value after doubling, and the old capacity >=16, then the new threshold is also doubled. (<<1 can mean double)else if((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold} // oldTab is null, oldCap is 0, if oldThr > 0, HashMap is called one of three constructors. //HashMap(int initialCapacity,floatloadFactor) //HashMap(int initialCapacity) //HashMap(Map<? extends K, ? Extends V> m) //oldThr is the initialCapacity (initialCapacity) of the HashMap specified by the user.else if (oldThr > 0) // initial capacity was placed inThreshold // oldThr is the initialCapacity when the table is not initialized. InitialCapacity newCap = oldThr;else{// Zero initial threshold using defaults // oldCap <= 0 and oldThr =0, indicating that the default values for the HashMap created by HashMap() are adopted. If oldTab (Table) is empty, oldCap is 0, oldThr is 0, set the new capacity to 16 and the new threshold to 16*0.75 newCap = DEFAULT_INITIAL_CAPACITY. newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } // The new threshold is 0if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes"."unchecked"}) / / initializes the table Node < K, V > [] newTab = (Node < K, V > []) new Node [newCap]; table = newTab; // If old table! =null moves the old data to the new tableif(oldTab ! = null) {for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if((e = oldTab[j]) ! = null) { oldTab[j] = null; // If it is a single node, place it directly in the newTab locationif (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if(e instanceof TreeNode) // If it is a red-black tree, it is a red-black treerehashAction ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);else{// preserve order // If it is a linked list Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next;do{ next = e.next; // Divide the elements in the same bucket into 2 different lists according to whether (e.hash & oldCap) is 0 or not, completerehash// index does not change the linked listif ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
elseloTail.next = e; loTail = e; } // List of indexed changeselse {
if (hiTail == null)
hiHead = e;
elsehiTail.next = e; hiTail = e; }}while((e = next) ! = null); // index invariant list tail pointer! If =null, the last pointer is nullif(loTail ! = null) { loTail.next = null; NewTab [j] = loHead; newTab[j] = loHead; } // Index changes to the end of the list pointer! =null, the last pointer is nullif(hiTail ! = null) { hiTail.next = null; +oldCap newTab[j +oldCap] = hiHead; } } } } }return newTab;
}
Copy the codeResize (); resize(); It is mainly divided into the following 7 steps
- Resize () has two functions, one is to initialize the table, the other is to expand the table.
- If before table! =null If (table.lenth>= maximum integer value) {set the expansion threshold to the maximum integer value and stop expansion. } else if (table.lenth*2< integer Max) {if (table.lenth*2< integer Max) {
- Capacity and threshold variables are assigned if a HashMap is created through the constructor, and default assignments are used if capacity and load factors are not set.
- If the table is not initialized, use new Node[newCap] to initialize it. If capacity expansion is performed, use new Node[newCap] to create a new container.
- If the old table! =null Moves the old data to the new container. The storage location is the original location/original location + original capacity. The relocation process uses the tail interpolation method, and the storage location is calculated during data transfer.
What is the difference between JDK1.7 and JDK1.8 in resize()?
- Expansion time: 1.7 Indicates whether to insert data before expanding the capacity. 1.8 indicates whether to insert data before expanding the capacity.
- Storage location calculation: 1.7 re-hashcode, perturbation processing and then modular calculation, and each data is calculated separately,1.8 original location/original location + old capacity, unified calculation when transferring data.
- Data transfer after capacity expansion: 1.7 If the head insertion method is used, the original location data will move backward, which will lead to the problem of reverse/circular linked list dead-loop. 1.8 If the tail insertion method is used, the problem of dead-loop, reverse and circular linked list will be prevented.
3.4. What does the hashmap.get () method mainly do? What does this method mainly do?
Public V get(Object key) {Node<K,V> e; // Return the value of the key.return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
* Implements Map.get and related methods
*
* @param hash hash for key
* @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;
if((tab = table) ! = null && (n = tab.length) > 0 && (first = tab[(n - 1) &hash])! // Return the list header if the first value isif (first.hash == hash&& // always check first node ((k = first.key) == key || (key ! = null && key.equals(k))))return first;
if((e = first.next) ! = null) {if(First instanceof TreeNode) // If it is a red-black tree, get it from getTreeNodereturn ((TreeNode<K,V>)first).getTreeNode(hash, key);
do{// loop through the listif (e.hash == hash&& ((k = e.key) == key || (key ! = null && key.equals(k))))return e;
} while ((e = e.next) != null);
}
}
return null;
}
Copy the codeNow that the core method of HashMap1.8 has been analyzed, let’s compare the differences between 1.7 and 1.8.
4. Difference analysis of HashMap 1.7/1.8
A little bit of knowledge
- How does a Hash table resolve Hash conflicts?
- Why does a HashMap have the following characteristics: key-values are allowed to be null, threads are not safe, order is not guaranteed, and storage location changes over time?
- Why wrapper classes like String and Integer in HashMap are suitable for key keys
- If the key in a HashMap is of Object type, what methods need to be implemented?
Early I also and a lot of small partners, everywhere collected a lot of information, the back found a lot of repeat! The following are arranged by themselves! Now BAT dream come true, I will contribute the information to the people in need!
By the way for a wave of attention, ha ha ~ everyone partners pay attention to my private letter [Java] can be free!
Source: www.jianshu.com/p/a7633a029…