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

This article mainly introduces "analyzing the principle of HashMap of JDK". In daily operation, I believe that many people have doubts in analyzing the principle of HashMap of JDK. The editor consulted all kinds of data and sorted out simple and easy-to-use operation methods. I hope it will be helpful to answer the doubts of "analyzing the principle of HashMap of JDK"! Next, please follow the editor to study!

1. Characteristics

We can use any class as the key of HashMap, but what restrictions should there be on these classes? Take a look at the following code:

Public class Person {private String name; public Person (String name) {this.name = name;}} MaptestMap = new HashMap (); testMap.put (new Person ("hello"), "world"); testMap.get (new Person ("hello")); / /-> null

I wanted to take out the value with the equivalent field value Person class, but it turned out to be null. People who know a little bit about HashMap can see that the Person class does not have an override hashcode method, which causes it to inherit the hashcode of Object (return is its memory address), and the Person object that comes out of new twice is not equals--. This is also the reason why immutable classes (such as String, Integer, etc.) are often used as key of HashMap in engineering projects. So how does HashMap use hashcode to index key?

two。 Principle

First, let's take a look at a simple HashMap implementation in "Thinking in Java":

/ /: containers/SimpleHashMap.java// A demonstration hashed Map.import java.util.*;import net.mindview.util.*;public class SimpleHashMapextends AbstractMap {/ / Choose a prime number for the hash table size, to achieve a uniform distribution: static final int SIZE = 997; / / You can't have a physical array of generics, but you can upcast to one: @ SuppressWarnings ("unchecked") LinkedList [] buckets = new LinkedList [SIZE]; public V put (K key, V value) {V oldValue = null Int index = Math.abs (key.hashCode ())% SIZE; if (buckets [index] = null) buckets [index] = new LinkedList (); LinkedList bucket = buckets [index]; MapEntrypair = new MapEntry (key, value); boolean found = false; ListIterator it = bucket.listIterator (); while (it.hasNext ()) {MapEntryiPair = it.next () If (iPair.getKey (). Equals (key)) {oldValue = iPair.getValue (); it.set (pair); / / Replace old with new found = true; break;}} if (! found) buckets [index] .add (pair); return oldValue;} public V get (Object key) {int index = Math.abs (key.hashCode ())% SIZE If return null; for (MapEntryiPair: buckets [index]) if (iPair.getKey (). Equals (key)) return iPair.getValue (); return null;} public Set entrySet () {Set set= new HashSet (); for (LinkedList bucket: buckets) {if (bucket = = null) continue; for (MapEntrympair: bucket) set.add (mpair);} return set } public static void main (String [] args) {SimpleHashMapm = new SimpleHashMap (); m.putAll (Countries.capitals (25)); System.out.println (m); System.out.println (m.get ("ERITREA")); System.out.println (m.entrySet ());}}

SimpleHashMap constructs a hash table to store the key,hash function. The modular operation Math.abs (key.hashCode ())% SIZE uses the linked table method to resolve hash conflicts. Each slot of buckets stores Map.Entry with the same (after hash) index value, as shown below:

The implementation principle of JDK's HashMap is similar, which uses the hash table table of chain address to store Map.Entry:

/ * The table, resized as necessary. Length MUST Always be a power of two. * / transient Entry [] table = (Entry []) EMPTY_TABLE;static class Entryimplements Map.Entry {final K key; V value; Entrynext; int hash; … }

The index of Map.Entry is obtained by hash the hashcode of key. When you want to get key the corresponding value, calculate its index for the key, and then extract the Map.Entry in the table to get it. For more information, please see the code:

Public V get (Object key) {if (key = = null) return getForNullKey (); Entryentry = getEntry (key); return null = = entry? Null: entry.getValue ();} final EntrygetEntry (Object key) {if (size = = 0) {return null;} int hash = (key = = null)? 0: hash (key); for (Entrye = table [indexFor (hash, table.length)]; e! = null; e = e.next) {Object k If (e.hash = = hash & & (k = e.key) = = key | | (key! = null & & key.equals (k) return e;} return null;}

It can be seen that hashcode directly affects the efficiency of HashMap's hash function-a good hashcode will greatly reduce hash conflicts and improve query performance. At the same time, this also explains the two questions raised at the beginning: if the custom class does the key of HashMap, then the calculation of hashcode should cover all fields of the constructor, otherwise it is possible to get null.

At this point, the study of "analyzing the principle of HashMap of JDK" is over. I hope to be able to solve your doubts. The collocation of theory and practice can better help you learn, go and try it! If you want to continue to learn more related knowledge, please continue to follow the website, the editor will continue to work hard to bring you more practical articles!

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.