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

Editor to share with you the analysis of the underlying principles of HashMap, I hope you will gain something after reading this article, let's discuss it together!

As we all know, HashMap is a collection used to store Key-Value key-value pairs, each of which is also called Entry. These key-value pairs (Entry) are stored separately in an array that is the backbone of HashMap.

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;}} Map testMap = 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 SimpleHashMap extends 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 (null) buckets [index] = new LinkedList > (); LinkedList > bucket = buckets [index]; MapEntry pair = new MapEntry (key, value); boolean found = false; ListIterator > it = bucket.listIterator (); while (it.hasNext ()) {MapEntry iPair = 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 (buckets [index] = = null) return null For (MapEntry iPair: 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 (MapEntry mpair: bucket) set.add (mpair);} return set;} public static void main (String [] args) {SimpleHashMap m = 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 in the following figure: the implementation principle of HashMap of JDK 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 Entry implements Map.Entry {final K key; V value; Entry next; 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 (); Entry entry = getEntry (key); return null = = entry? Null: entry.getValue ();} final Entry getEntry (Object key) {if (size = = 0) {return null;} int hash = (key = = null)? 0: hash (key); for (Entry e = 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.

After reading this article, I believe you have a certain understanding of "HashMap underlying principle Analysis". If you want to know more about it, you are welcome to follow the industry information channel. Thank you for your reading!

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.