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

This article will explain in detail what is the implementation principle of HashMap in Java. The content of the article is of high quality, so the editor will share it with you for reference. I hope you will have a certain understanding of the relevant knowledge after reading this article.

1. HashCode and equals in Java

About hashcode

1. The existence of hashcode is mainly used for the quickness of lookup, such as Hashtable,HashMap, etc. HashCode is used to determine the storage address of objects in the hash storage structure.

2. If two objects are the same, it is applicable to the equals (java.lang.Object) method, then the hashCode of the two objects must be the same.

3. If the equals method of the object is overridden, then the hashCode of the object should be rewritten as much as possible, and the object used by hashCode must be the same as that used in the equals method, otherwise it will violate the second point mentioned above.

4. The hashCode of two objects is the same, which does not necessarily mean that the two objects are the same, that is, it is not necessarily suitable for the equals (java.lang.Object) method, but can only indicate that the two objects are in the hash storage structure, such as Hashtable. They are stored in the same basket

HashCode is used for lookup, and equals is used to compare whether two objects are equal.

About equals

1, equals and = =

= = different functions are used to compare references and compare basic data types:

Compare basic data types, and if the two values are the same, the result is true

When comparing references, if the reference points to the same object in memory, the result is true

Equals (), as a method, implements the comparison of objects. Because the = = operator does not allow us to overwrite, that is to say, it limits our expression. So we override (rewrite, subclass copy) the equals method to compare whether the object content is the same. This cannot be done through the = = operator.

2. The comparison rule of the equals () method of the Object class is: if the two objects are of the same type and content, true is returned. These classes are:

Java.io.file,java.util.Date,java.lang.string, packaging class (Integer,Double, etc.)

Second, the realization principle of HashMap

1. Overview of HashMap

HashMap is an asynchronous implementation of the Map interface based on hash tables. This implementation provides all optional mapping operations and allows the use of null values and null keys. This class does not guarantee the order of the mapping, especially it does not guarantee that the order is permanent.

In the Java programming language, there are two basic structures, one is an array, and the other is an analog pointer (reference). All data structures can be constructed with these two basic structures, including HashMap. HashMap is no exception. HashMap is actually a hash data structure of linked lists, that is, a combination of arrays and linked lists.

As you can see from the figure above, the bottom layer of HashMap is an array structure, and each item in the array is a linked list. When you create a new HashMap, an array is initialized.

/ * Basic hash bin node, used for most entries. (See below for * TreeNode subclass, and in LinkedHashMap for its Entry subclass.) * / static class Node implements Map.Entry {final int hash; final K key; V value; Node next; Node (int hash, K key, V value, Node next) {this.hash = hash; this.key = key; this.value = value; this.next = next;} public final K getKey () {return key } public final V getValue () {return value;} public final String toString () {return key + "=" > you can see that Node is an element in an array, and each Map.Entry is actually a key-value pair, which holds a reference to the next element, which constitutes linked list 2, HashMap implementation storage and reading 1) store / * * Associates the specified value with the specified key in this map. * If the map previously contained a mapping for the key, the old * value is replaced. * * @ param key key with which the specified value is to be associated * @ param value value to be associated with the specified key * @ return the previous value associated with key, or * null if there was no mapping for key. * (A null return can also indicate that the map * previously associated null with key.) * / 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 onlyIfAbsent if true, don't change existing value * @ param evict if false, the table is in creation mode. * @ return previous value, or null if none * / final V putVal (int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {Node [] tab; Node p; int n, I; if ((tab = table) = = null | | (n = tab.length) = = 0) n = (tab = resize ()) .length If ((p = tab [I = (n-1) & hash]) = = null) 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) e = p Else if (p instanceof TreeNode) e = ((TreeNode) p) .putTreeVal (this, tab, hash, key, value); else {for (int binCount = 0;; + + binCount) {if ((e = p.next) = = null) {p.next = newNode (hash, key, value, null) If (binCount > = TREEIFY_THRESHOLD-1) / /-1 for 1st treeifyBin (tab, hash); break } if (e.hash = = hash & & (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; afterNodeAccess (e); return oldValue;}} + modCount; if (+ + size > threshold) resize (); afterNodeInsertion (evict); return null } get the position of this element in the array according to the hash value (that is, the subscript). If there are other elements in the array at this position, then the elements in this position will be stored in the form of a linked list, and the newly added elements will be placed at the head of the chain. the first to add is at the end of the chain. If there is no element at that position in the array, place the element directly at that position in the array. / * Computes key.hashCode () and spreads (XORs) higher bits of hash * to lower. Because the table uses power-of-two masking, sets of * hashes that vary only in bits above the current mask will * always collide. (Among known examples are sets of Float keys * holding consecutive whole numbers in small tables.) So we * apply a transform that spreads the impact of higher bits * downward. There is a tradeoff between speed, utility, and * quality of bit-spreading. Because many common sets of hashes * are already reasonably distributed (so don't benefit from * spreading), and because we use trees to handle large sets of * collisions in bins, we just XOR some shifted bits in the * cheapest possible way to reduce systematic lossage, as well as * to incorporate impact of the highest bits that would otherwise * never be used in index calculations because of table bounds. * / static final int hash (Object key) {int h; return (key = = null)? 0: (h = key.hashCode ()) ^ (h > 16);} We can see that to find an element in hashMap, we need to find the position in the corresponding array based on the hash value of key. How to calculate this location is the hash algorithm. As mentioned earlier, the data structure of HashMap is a combination of arrays and linked lists, so we want the elements in this HashMap to be evenly distributed as far as possible. Try to make only one number of elements in each location, then when we use the hash algorithm to find this location, we can immediately know that the elements of the corresponding location are what we want, instead of having to traverse the linked list, which greatly optimizes the query efficiency. HashMap treats key-value as a whole at the bottom, which is a Node object. The bottom layer of HashMap uses a Node [] array to save all key-value pairs. When you need to store a Node object, it will determine its storage location in the array according to the hash algorithm, and determine its storage location in the linked list on the array location according to the equals method; when you need to take out an Entry, it will also find its storage location in the array according to the hash algorithm, and then extract the Node from the linked list on the location according to the equals method. 3. Resize of HashMap when there are more and more elements in hashmap, the probability of collision becomes higher and higher (because the length of the array is fixed), so in order to improve the efficiency of query, it is necessary to expand the array of hashMap, and the operation of array expansion will also appear in ArrayList, so this is a general operation, similar to equal allocation. After the expansion of hashmap, the most performance-consuming point appears: the data in the original array must recalculate its position in the new array and put it in, that is, resize. So when will hashmap expand its capacity? When the number of elements in hashmap exceeds the array size * loadFactor, the array will be expanded. The default value of loadFactor is 0.75. that is to say, by default, the size of the array is 16. When the number of elements in hashmap exceeds 16 "0.75" 12, the size of the array will be expanded to 2 "16" 32, that is, double, and then recalculate the position of each element in the new array, which is resize. Summary: the implementation principle of HashMap: 1. The hashCode to achieve key re-hash to calculate the subscript of the elements of the current object in the array. 2. When storing, if a key with the same hash value appears, there are two cases. (1) if the key is the same, the original value is overwritten; (2) if the key is different (there is a conflict), the current key-value is put into the linked list. 3. When obtaining, directly find the subscript corresponding to the hash value, and further determine whether the key is the same, so as to find the corresponding value. 4. If you understand the above process, it is not difficult to understand how HashMap solves the problem of hash conflicts. The core is to use the array storage method, and then put the conflicting key objects into the linked list. Once the conflict is found, make further comparison in the linked list. What is the implementation principle of HashMap in Java is shared here, I hope that the above content can be of some help to you, can learn more knowledge. If you think the article is good, you can share it for more people to see.

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.