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

HashTable source code analysis

For more resources and tutorials, please follow the official account: non-course classes.

If you think my writing is OK, please give me a like, thank you, your encouragement is the motivation of my creation.

# 1. Preface

Hashtable, a veteran collection class, was born as early as JDK 1.0.

# 1.1. Abstract

In the first chapter of the collection series, we learned that the implementation classes of Map are HashMap, LinkedHashMap, TreeMap, IdentityHashMap, WeakHashMap, HashTable, Properties, and so on.

# 1.2. Brief introduction

Hashtable, a veteran collection class, was born as early as JDK 1.0, while HashMap was born in JDK 1.2. in implementation, HashMap absorbs a lot of Hashtable ideas. Although the underlying data structures of both are array + linked list structure, with the characteristics of fast query, insertion and deletion, there are many differences between the two.

 opens the source code of Hashtable and you can see that Hashtable inherits from Dictionary and HashMap inherits from AbstractMap.

Public class Hashtableextends Dictionaryimplements Map, Cloneable, java.io.Serializable {.}

The definition that  HashMap inherits from the AbstractMap,HashMap class is as follows:

Public class HashMap extends AbstractMap implements Map, Cloneable, Serializable {.}

The underlying layer of  Hashtable and HashMap is stored in an array. At the same time, when the stored data is used to calculate the array subscript through key, it is mainly based on the hash algorithm, so the possibility of hash conflict may occur.

 popular words, that is, different key, in the calculation, may produce the same array subscript, at this time, how to put two objects into an array?

There are two ways to resolve hash conflicts by , one is open address (when a hash conflict occurs, continue to search until you find a hash value without conflict), and the other is zipper (putting conflicting elements into a linked list).

Java Hashtable uses the second way, the zipper method!

Therefore, when different key obtain the same array subscript through a series of hashing algorithms, the object will be placed in an array container, and then the object will be stored in the same array subscript container in the form of an one-way linked list, just like a chain, hanging on a node, as shown below:

Similar to HashMap, Hashtable also includes five member variables: / * * an array of Entry objects * / private transient Entry [] the number of Entry objects in table;/**Hashtable * / threshold for private transient int count;/**Hashtable expansion * / private int threshold;/** load factor. The default number of 0.75*/private float loadFactor;/** record modifications * / private transient int modCount = 0

The specific meanings of each variable are as follows:

 table: represents an array of linked lists made up of Entry objects. Entry is a unidirectional linked list. The key-value key-value pairs of hash tables are stored in the Entry array.

 count: indicates the size of the Hashtable, which is used to record the number of key-value pairs saved

 threshold: indicates the threshold of Hashtable, which is used to determine whether the capacity of Hashtable needs to be adjusted. Threshold is equal to capacity * load factor.

 loadFactor: indicates the load factor. Default is .75

 modCount: indicates the number of Hashtable modifications recorded, which is used to implement fast failure and exception handling

Next, let's take a look at Entry, an internal class. Entry is used to store linked list data and implements the Map.Entry interface, which is essentially a mapping (key-value pair). The source code is as follows:

Private static class Entry implements Map.Entry {/ * * hash value * / final int hash;/**key indicates key * / final K key;/**value represents value * / V next element of value;/** node * / Entry next;.}

Let's move on to the initialization process of Hashtable. The core source code is as follows:

Public Hashtable () {this (11,0.75f);}

This calls its own constructor. The core source code is as follows:

Public Hashtable (int initialCapacity, float loadFactor) {. / / default initial size is 11max / and the threshold for calculating capacity expansion is this.loadFactor = loadFactor;table = new Entry [initialCapacity]; threshold = (int) Math.min (initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);}

You can see that the default initial size of HashTable is 11. If you initialize a given capacity size, then HashTable will directly use your given size.

The threshold threshold for capacity expansion is equal to initialCapacity * loadFactor. Let's take a look at HashTable expansion as follows:

Protected void rehash () {int oldCapacity = table.length;// performs bit operations on the length of the old array, and then + 1 2n+1int newCapacity / equals each expansion to the original 2n+1int newCapacity = (oldCapacity [newCapacity];}

As you can see, HashTable expands to the original 2n+1 each time.

Let's take a look at HashMap. If the default construction method is executed, the size will be initialized at the step of capacity expansion. The core source code is as follows:

Final Node [] resize () {int newCap = 0rampact / some codes are omitted. NewCap = DEFAULT_INITIAL_CAPACITY;// default capacity is 16Node [] newTab = (Node []) new Node [newCap];}

You can see that the default initialization size of HashMap is 16. Let's take a look at the HashMap expansion method. The core source code is as follows:

Final Node [] resize () {/ / get the length of the old array Node [] oldTab = table;int oldCap = (oldTab = = null)? 0: oldTab.length;int newCap = 0 oldCap / partial code omitted. / / when the capacity is expanded, the multiple of capacity 2 newCap = oldCap > > 16) is the second step of high participation operation (jdk1.7) return (key = = null)? 0: (h = key.hashCode ()) ^ (h > 16) / / jdk1.8} / * * get the source code of array subscript method * / static int indexFor (int h, int length) {/ / jdk1.7. Jdk1.8 does not have this method, but it implements return h & (length-1) with the same principle; / / the third step takes module operation}

Because HashMap uses the power of 2, there is no need to do division in the modular operation, only the sum of bits is needed. However, due to the aggravation of the hash conflict, HashMap does some high-level operations, that is, the second step, after calling the object's hashCode method, to break up the data and make the hash results more uniform.

# 1.3. Introduction of common methods

# 1.3.1.put method

The put method adds the specified key and value pairs to the map.

The put flow chart is as follows:

Open the put method of HashTable. The source code is as follows:

Public synchronized V put (K key, V value) {/ / throw an exception when the value value is empty! If (value = = null) {throw new NullPointerException ();} Entry tab [] = table;// calculates the storage subscript int hash = key.hashCode (); int index = (hash & 0x7FFFFFFF)% tab.length;// loops through the array linked list / / if there is the same key and the hash is the same, overwrite Entry entry = (Entry) tab [index]; for (; entry! = null Entry = entry.next) {if ((entry.hash = = hash) & & entry.key.equals (key)) {V old = entry.value;entry.value = value;return old;}} / / add addEntry (hash, key, value, index) to the array linked list; return null;}

The source code of the addEntry method in the put method is as follows:

Private void addEntry (int hash, K key, V value, int index) {/ / number of new modifications modCount++; Entry tab [] = table; if (count > = threshold) {/ / the array capacity is larger than the expansion threshold, rehash (); tab = table; / / recalculate the object storage subscript hash = key.hashCode () Index = (hash & 0x7FFFFFFF)% tab.length;} / / Store objects in the array Entry e = (Entry) tab [index]; tab [index] = new Entry (hash, key, value, e); count++;}

The source code of the rehash method in the addEntry method is as follows:

Protected void rehash () {int oldCapacity = table.length; Entry [] oldMap = table; / / each expansion to the original 2n+1 int newCapacity = (oldCapacity 0) {if (oldCapacity = = MAX_ARRAY_SIZE) / / is greater than the maximum threshold, and the capacity is no longer expanded return; newCapacity = MAX_ARRAY_SIZE;} Entry [] newMap = new Entry [newCapacity]; modCount++ / / recalculate the expansion threshold threshold = (int) Math.min (newCapacity * loadFactor, MAX_ARRAY_SIZE + 1); table = newMap; / / copy the data from the old array to the new array for (int I = oldCapacity; Imam-> 0;) {for (Entry old = (Entry) oldMap [I]; old! = null;) {Entry e = old; old = old.next Int index = (e.hash & 0x7FFFFFFF)% newCapacity; e.next = (Entry) newMap [index]; newMap [index] = e;}

The summary process is as follows:

1. Calculate the subscript of an object stored in an array through key

2. If there is key in the linked list, overwrite the old and new values directly.

3. If there is no key in the linked list, determine whether you need to expand the capacity. If you need to expand the capacity, expand the capacity first, then insert the data.

It is worth noting that the put method adds the synchronized keyword, so it is thread-safe when synchronizing.

# 1.3.2.get method

The get method returns the corresponding value based on the specified key value.

The get flow chart is as follows:

Open the get method of HashTable. The source code is as follows:

Public synchronized V get (Object key) {Entry tab [] = table; / / storing subscripts int hash = key.hashCode () through key compute nodes; int index = (hash & 0x7FFFFFFF)% tab.length; for (Entry e = tab [index]; e! = null; e = e.next) {if ((e.hash = = hash) & & e.key.equals (key)) {return (V) e.value }} return null;}

Again, it is worth noting that the get method adds the synchronized keyword, so it is thread-safe when synchronizing.

# 1.3.3.remove method

The role of remove is to delete the corresponding elements through key.

The remove flow chart is as follows:

Open the remove method of HashTable. The source code is as follows:

Public synchronized V remove (Object key) {Entry tab [] = table; / / storing subscripts int hash = key.hashCode () through key compute nodes; int index = (hash & 0x7FFFFFFF)% tab.length; Entry e = (Entry) tab [index] / / cycle through the linked list to determine whether the key exists by hash and key / / if so, directly set the change node to empty and remove for (Entry prev = null; e! = null; prev = e, e = e.next) {if ((e.hash = = hash) & & e.key.equals (key)) {modCount++) from the linked list If (prev! = null) {prev.next = e.next;} else {tab [index] = e.next;} count--; V oldValue = e.value; e.value = null; return oldValue;}} return null;}

Again, it is worth noting that the remove method adds the synchronized keyword, so it is thread-safe when synchronizing.

# 1..3.4. Summary

Summarize the connections and differences between Hashtable and HashMap. The contents are as follows:

 1. Although both HashMap and Hashtable implement the Map interface, Hashtable inherits from the Dictionary class, while HashMap inherits from AbstractMap

 2 and HashMap can allow a key of null and any value of null, but key and value in HashTable are not allowed to be null

The methods of  3 and Hashtable are synchronous because the synchronized synchronization lock is added to the method, and HashMap is not thread safe.

Although Hashtable is thread-safe, it is generally not recommended because there is a more efficient and better choice of ConcurrentHashMap, which we will talk about later.

Finally, an annotated description from HashTable is introduced:

If a thread-safe implementation is not needed, it is recommended to use HashMap in place of Hashtable. If a thread-safe highly-concurrent implementation is desired, then it is recommended to use java.util.concurrent.ConcurrentHashMap in place of Hashtable.

To put it simply, if you don't need thread safety, use HashMap, and if you need thread safety, use ConcurrentHashMap.

For more resources and tutorials, please follow the official account: non-course classes.

Efforts do not necessarily succeed, but give up must fail, leave the process to yourself, leave the results to others, when your talent can not support your ambition, you should work hard

Finally, share a wave of java resources, including a full set of videos from entry to development of java, as well as 26 projects of java. The resources are relatively large, the size is about 290g, and the link is easy to fail. The way to get it is to follow the official account: non-subject class, and then reply: java project can be obtained, I wish you all a happy study.

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.