Based on JDK1.8, the source code of Java Hashtable collection is analyzed in depth, including various methods, capacity expansion mechanism, hash algorithm, traversal method and other methods of the underlying implementation, finally, the detailed comparison of Hashtable and HashMap and the use of suggestions are given.
1 Overview of Hashtable
public class Hashtable< K,V > extends Dictionary< K,V > implements Map< K,V >, Cloneable, Serializable
Hashtable is an ancient key-value collection class from the JDK1.0 era. All methods in the class are synchronous, data security, low efficiency.
In JDK1.0, Hashtable was an abstract class inherited from Dictionary. After the creation of JDK1.2 collection framework, the Map interface was implemented and became a member of the Java collection system.
Cloneable and Serializable interface are implemented to support cloning and serialization operations.
Since maps are not part of the Collection system and do not implement Iterable, the iterator() method is not supported, or the Map Collection system does not have real iterators. But they have their own way of traversing the data.
The bottom layer of the Hashtable is actually a “zipper” method, which uses an array as the skeleton of the Hashtable. Each element of the array is located in a “bucket”, which contains key pairs with the same hash value. If there are multiple key pairs in a bucket, then there is a hash conflict. Hashtable resolves conflicts using the “zipper method,” where the size of each bucket is the number of linked list nodes at that location. Neither the key nor value of a Hashtable is allowed to be null.
The hash table in the data structure is explained in detail in this article:Data structure – hash table (hash table) principle and Java code implementation.
2 Hashtable source parsing
2.1 Main class attributes
/** * Internal Entry[] array, which is used as the skeleton of the Hashtable. Each Entry element in the array represents the head node of a linked list. The key-value pairs of the Hashtable are stored in the Entry nodes. * /
private transientEntry<? ,? >[] table;/** * The size of the HashTable. Note that this size is not the size of the HashTable container, but the number of Entry key-value pairs it contains. * /
private transient int count;
/** * Specifies the threshold of the Hashtable to determine whether the capacity of the Hashtable needs to be adjusted. The value of threshold =" capacity * loading factor ". When the count is greater than or equal to the threshold, you need to adjust the capacity (try expanding it). * /
private int threshold;
/** * The load factor can be greater than 1. * /
private float loadFactor;
/** * is used to implement the fail-fast mechanism. * /
private transient int modCount = 0;
Copy the codeThe capacity expansion threshold is determined by the initial capacity and the loading factor, usually threshold=table.length*loadFactor. The larger the initial capacity and the loading factor are, the less frequent “capacity expansion” is needed. If the initial capacity is too large, more space may be wasted, and the larger the loading factor is, the higher the risk of hash conflict is. It takes too long to find the data. Default capacity (11) and load factor (0.75) seek a compromise in time and space costs.
The function of modCount and fail-fast mechanism have already been explained in the source article of ArrayLsit collection. The fail-fast mechanism of collection under java.util package is the same, and more details can be read in this article:Java collections – ArrayList source depth analysis and application introduction.
2.2 Entry node
An Entry is actually an inner class of a Hashtable. It is used as an internal container for storing keys and values, as well as the hashCode value of the key. At the same time, since Hashtable uses the “zipper method” to implement the Hashtable, each Entry is also a node of the linked list. So there is also an internal reference property to the next node.
Entry actually implements the Map.entry interface, so it also implements the related methods called externally. The may.entry element of the set returned by the EntrySet() method is actually an instance of the Entry node returned, as explained later!
private static class Entry<K.V> implements Map.Entry<K.V> {
// The hash value is stored for later use and avoids repeated operations
final int hash;
//key
final K key;
//value
V value;
// The next node reference with the same bucket bit
Entry<K,V> next;
protected Entry(int hash, K key, V value, Entry<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
@SuppressWarnings("unchecked")
protected Object clone(a) {
return new Entry<>(hash, key, value,
(next==null ? null : (Entry<K,V>) next.clone()));
}
public K getKey(a) {
return key;
}
public V getValue(a) {
return value;
}
public V setValue(V value) {
if (value == null)
throw new NullPointerException();
V oldValue = this.value;
this.value = value;
return oldValue;
}
public boolean equals(Object o) {
if(! (oinstanceof Map.Entry))
return false; Map.Entry<? ,? > e = (Map.Entry<? ,? >)o;return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&
(value==null ? e.getValue()==null : value.equals(e.getValue()));
}
public int hashCode(a) {
return hash ^ Objects.hashCode(value);
}
public String toString(a) {
return key.toString()+"="+value.toString(); }}Copy the codeFrom this, we can draw a general data structure of Hashtable:
2.3 Constructors and initialization parameters
2.3.1 Hashtable ()
public Hashtable()
Construct a new, empty hash table with a default initial capacity (11) and load factor (0.75).
public Hashtable(a) {
// Internally calls another constructor with an initial capacity of 11 and a load factor of 0.75
this(11.0.75 f);
}
Copy the code2.3.2 Hashtable (int initialCapacity)
public Hashtable(int initialCapacity)
Constructs a new empty hash table with the specified initial capacity and the default load factor (0.75).
public Hashtable(int initialCapacity) {
// Internally calls another constructor to construct a new empty hash table with the specified initial capacity and the default load factor (0.75).
this(initialCapacity, 0.75 f);
}
Copy the code2.3.3 Hashtable(int initialCapacity, float loadFactor)
public Hashtable(int initialCapacity,float loadFactor)
Constructs a new empty hash table with the specified initial capacity and the specified load factor. The load factor can be greater than one, but obviously, the higher the load factor, the greater the probability of hash collisions!
Here initialCapacity is not required to be a power of 2, but the initialCapacity in the HashMap must be a power of 2.
/** * Suggest a maximum array size, as some VM implementations may require a partial array size to hold array header information * However, in HotSopt VMS, the array size can exceed this limit. We can reach the length * of Integer.MAX_VALUE - 2 and as you can see from the source above, we can allocate initialCapacity that is completely larger than MAX_ARRAY_SIZE */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
public Hashtable(int initialCapacity, float loadFactor) {
// Initial capacity check
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: " +
initialCapacity);
// Load factor detection
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal Load: " + loadFactor);
// If the initial capacity is 0, then it becomes 1
if (initialCapacity == 0)
initialCapacity = 1;
this.loadFactor = loadFactor;
// Create an array
table = newEntry<? ,? >[initialCapacity];// To calculate the capacity expansion threshold, take the minimum value of initialCapacity * loadFactor and MAX_ARRAY_SIZE + 1
threshold = (int) Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
}
Copy the code2.3.4 Hashtable (Map <? extends K,? extends V> t)
public Hashtable(Map<? extends K,? extends V> t)
Construct a new hash table that has the same mapping relationship as the given Map. The hash table is created with an initial capacity sufficient to hold the mappings in a given Map and a default load factor (0.75).
public Hashtable(Map<? extends K, ? extends V> t) {
// First initialize the HashTable
this(Math.max(2*t.size(), 11), 0.75 f);
// The underlying method calls putAll
putAll(t);
}
Copy the code2.4 PUT method and Expansion Mechanism
public synchronized V put(K key, V value)
Maps the specified key to the specified value in this hash table. If the key or value is NULL, a NullPointerException is thrown.
The PUT method has a lot of source code and is a key part of Hashtable, but it’s not hard to understand! Let’s break it down into three parts: put, addEntry, and Rehash.
Against 2.4.1 put
The PUT method that is open to external calls can be divided into four main steps:
- The hash algorithm is used to calculate the position of the new key-value pair.
- Determine whether there is an element in this position, and whether there is an element with the same key;
- If it exists, and the same key is found, replace the value, return the old value, and the method ends;
- If no element exists, or the same key is not found, then call the addEntry method to add a new element node, return NULL, and the method ends.
/** * Open the method of adding nodes to external calls. Use the hash algorithm to calculate the position of the new key-value pair * 2. Determine whether there is an element in the position and whether there is an element with the same key * 3. If there is an element and the same key is found, replace the value and return the old value. Then add a new element node, return NULL, and the method ends * *@paramThe key key *@paramThe value value *@returnOld value * /
public synchronized V put(K key, V value) {
/*1 Calculates the location of the new key-value pair using the hash algorithm */
// Ensure that value is not null
if (value == null) {
throw new NullPointerException();
}
// Get the table arrayEntry<? ,? > tab[] = table;/*Hash algorithm for Hashtable */
// Get the hash value of key, which is a method in Object, and which can be overridden by key,
int hash = key.hashCode();
// Calculate the hash value to determine the index position of key-value stored in table[]
int index = (hash & 0x7FFFFFFF) % tab.length;
// Obtain the entry of the array at the index location
Entry<K, V> entry = (Entry<K, V>) tab[index];
If the entry is not null, then there are elements, and there may be more than one element */
// Then iterates over the list at index position. If there is an identical key in the list at that position, replace its value and return the old value
for(; entry ! =null; entry = entry.next) {
// To determine whether the hash value returned by the hashCode() method is equal to the hash value returned by the two keys.
if ((entry.hash == hash) && entry.key.equals(key)) {
// If so, replace the old value and return
V old = entry.value;
entry.value = value;
returnold; }}// If the entry is null, the entry is null. The other is when the entry is not null, but the same key is not found
// Call the addEntry method
addEntry(hash, key, value, index);
// The old value returns null
return null;
}
Copy the codeHere is the key source code analysis:
The hash algorithm of the hashtable is:
(hash & 0x7FFFFFFF) % tab.length;
Hash is the return value of the key’s hashCode method. 0x7FFFFFFF represents the largest int, which is 2147483647, and its binary representation is 1 except for the first sign bit, which is 0.
Since the hash returned by the hashCode method is an integer of type int and can be positive or negative, the purpose of the first hash & 0x7FFFFFFF is to convert the hash to an integer that must be greater than or equal to 0.
Then we mod the length of the underlying array. We know that the remainder must be smaller than the divisor. The remainder of a dividend greater than or equal to 0 divided by a positive integer must be in the range of [0, divisor), that is, [0, tab.length-1].
The location of the bucket calculated by the hash algorithm is just enough to cover all the index values of the entire array, and does not exceed its range!
We can also see that since the final bucket position is calculated by remainder “%”, the remainder will be more uniform if the dividend is odd, that is, if the array size is odd (why does the hash function choose odd to remainder?). OldCapacity << 1) + 1 makes the new capacity odd. However, hashtable does not force the capacity to be prime because the capacity can be set by the constructor. This may be because HashTable is no longer recommended by Sun.
Then there is the key to judge the repetition, which is determined by:
(entry.hash == hash) && entry.key.equals(key)
It is a two-step process to determine whether the hashCode values of the two keys are equal, and to determine whether the equals method of the two keys returns true!
Finally, if no element exists, or if the same key is not found, then call the addEntry method to add a new element node, returning NULL, and the method ends.
Let’s look at the source code of the addEntry method!
2.4.2 addEntry
The addEntry method for adding new element nodes can be divided into three steps:
- Determine whether to expand the capacity.
- If we need to expand, we call the rehash method to expand and recalculate the position of the new key in the new array.
- Adopt the head insertion method, insert the node, the end of the method;
/** * The method of adding a new node is divided into three steps * 1. Determine whether to expand the capacity. * 2. If expansion is needed, then rehash() expands and recalculates the new key row in the array; * 3. Use head insert method to insert nodes; * *@paramHash Hash value * of the key obtained by the hashcode method@paramThe key key *@paramThe value value *@paramIndex Location of the key-value pairs calculated by the Hashtable hash algorithm */
private void addEntry(int hash, K key, V value, int index) {
// The number of hash table structure changes increases by 1, which is only related to the fail-fast mechanismmodCount++; Entry<? ,? > tab[] = table;/*1 If the number of nodes is greater than or equal to the threshold, expand the capacity of nodes */
if (count >= threshold) {
/*2 Expand the underlying array and re-hash the internal elements in the new array and move them to the new array */
rehash();
/* Recalculate the position in the new array */ for the new k-v
tab = table;
hash = key.hashCode();
index = (hash & 0x7FFFFFFF) % tab.length;
}
/*3 Create a new entry node and add it to the list header to make it a new head node
// Get the node at the index of the array, which is actually the head node of the list
Entry<K, V> e = (Entry<K, V>) tab[index];
// Create a new entry node. Next refers to the original head node at that location. The new node is placed in the array at the location of the index and becomes the new node.
tab[index] = new Entry<>(hash, key, value, e);
// The number of nodes increases by 1
count++;
}
Copy the codeHere is the key source code analysis:
The first is to determine whether to expand the source code:
count >= threshold
This is where the threshold is called the scaling threshold, and the number of elements is greater than or equal to this value.
Then use the rehash() method to expand, and then note that the array length may have changed as a result of the expansion, so you need to recalculate the insertion position of the new node!
Finally, the new node is inserted, using the “head plug” method. The so-called “head insertion” method is very simple, in fact, it is to insert the new point as the head node of the list, in Haashtable, it is expressed as: the new node is stored in the array corresponding to the index position, the original index position of the node becomes the next node of the new node! The main reason for using header inserts is that newly inserted data is more likely to be used as hot data, which can be placed in the header to reduce search time.
Before JDK1.8, HashMap also used “head interpolation” to insert element nodes, but in JDK1.8, it is changed to “tail interpolation”, because the head interpolation may form a circular linked list in multithreaded operation, resulting in an infinite loop. The specific principle of HashMap principles will be explained in the article. But since Hashtable is thread-safe, no changes need to be made!
Let’s take a look at the rehash() method in isolation!
2.4.3 rehash
The rehash method for capacity expansion can be divided into two steps:
- Array expansion, which attempts to create a larger array;
- If the expansion is successful, then loop through the old array, transfer nodes to the new array, the method ends;
/** * Internal array expansion method and data transfer mechanism, mainly divided into two steps: * 1, array expansion * 2, loop through the old array, transfer node */
protected void rehash(a) {
/*1 Array expansion */
// Get the old capacity
int oldCapacity = table.length;
// Get the old array referenceEntry<? ,? >[] oldMap = table;// oldCapacity*2+1 = oldCapacity*2+1 = oldCapacity*2+1
int newCapacity = (oldCapacity << 1) + 1;
// If the new capacity minus MAX_ARRAY_SIZE is greater than 0, note that the new capacity is not necessarily greater than MAX_ARRAY_SIZE, and may be negative
if (newCapacity - MAX_ARRAY_SIZE > 0) {
// If the old capacity is equal to MAX_ARRAY_SIZE
if (oldCapacity == MAX_ARRAY_SIZE)
// Then continue to use the old capacity to continue to run, the expansion is finished, that is, reached the maximum capacity of the array, no further expansion
return;
// Otherwise, the new capacity is equal to MAX_ARRAY_SIZE
newCapacity = MAX_ARRAY_SIZE;
}
// Create an array with new capacityEntry<? ,? >[] newMap =newEntry<? ,? >[newCapacity];// The number of changes to the array structure is increased by 1
modCount++;
// Calculate the new capacity expansion threshold
threshold = (int) Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
// Table points to the new array
table = newMap;
/*2 loops through the old array, transferring the old array element nodes */
for (int i = oldCapacity; i-- > 0;) {// Loop through the linked list at each array node
for(Entry<K, V> old = (Entry<K, V>) oldMap[i]; old ! =null;) {// Get an old node at the index, and use e to hold it. The first time e is obtained, it is the head node of the list at the index
Entry<K, V> e = old;
// Get the next node from the old node
old = old.next;
// Calculate the index position of the old node e in the new array
int index = (e.hash & 0x7FFFFFFF) % newCapacity;
/* Insert the element */ in the next two steps
// The next node of this node points to the head node of the new array position
e.next = (Entry<K, V>) newMap[index];
// The head node of the new array points to that nodenewMap[index] = e; }}}Copy the codeHere is the key source code analysis:
First is the source code to try to expand:
int newCapacity = (oldCapacity << 1) + 1;
The above code is used to calculate the new capacity. The new capacity is shifted one bit to the left of the old capacity and then added one. The << is the 3 operator, which can speed up the operation.newCapacity=oldCapacity*2+1, the key is the following code:
if (newCapacity – MAX_ARRAY_SIZE > 0)
This code is used to determine if “the capacity really can be expanded and if the new maximum capacity needs to be reallocated.” Because of the binary algorithm of the computer, if the original oldCapacity is large, the new capacity may be less than zero, leading to unexpected situations.
For more information on binary computing pits, see ArrayLsit’s previous analysis and this article:Computer base conversion details and Java binary operation methodsI will not repeat it here.
Therefore, when we try to expand, since we can set the initial capacity at will in the constructor, there are three cases based on the size of oldCapacity:
- OldCapacity is located in [1, integer.max_value /2-4]
- NewCapacity will be positive, and the judgment in if will be false. At this point, you will not enter the if code block, and you can create a new array for expansion. Interestingly, if oldCapacity is Integer.MAX_VALUE /2-4, then newCapacity is exactly MAX_ARRAY_SIZE, and the value computed in the if statement is exactly 0.
- OldCapacity is located in [integer.max_value /2-3, integer.max_value -5]
- Because of the rules of binary computing, newCapacity may be positive or negative, but the judgment in if will always be true. If oldCapacity is equal to MAX_ARRAY_SIZE, then no expansion is performed. Otherwise, newCapacity is equal to MAX_ARRAY_SIZE, which makes it possible to shrink rather than expand (when oldCapacity is greater than MAX_ARRAY_SIZE, the newCapacity is equal to MAX_ARRAY_SIZE, which means the capacity is reduced). If the initial capacity is set to INTEger.max_value -5, then newCapacity is calculated to be -11 and -11 -max_array_size is equal to 2147483646 and greater than 0. We know that MAX_ARRAY_SIZE (integer.max_value – 8) is less than integer.max_value – 5.
- OldCapacity in [integer.max_value -4, integer.max_value]
- NewCapacity is still negative, and the judgment in if will be false. This will not go into the if block, and an exception will be thrown when a new array is created for expansion! If the initial capacity is set to Integer.MAX_VALUE -4, then newCapacity will be calculated as -9, and -9 -max_array_size is equal to -2147483648, less than 0. In this case, the new array will be created with -9 as capacity. Lead to abnormal NegativeArraySizeException.
Then there is the part of the array node transfer:
- Start from the end of the old array and loop through each node of the list in each bucket, using “head insertion” to move to the corresponding position in the new array.
- If the nodes in the original list are still in the same position in the new array, then the order of the nodes in the new array is the reverse of the original list order!
2.5 putAll method
public synchronized void putAll(Map<? extends K, ? extends V> t)
Copies all mappings of the specified mapping into this hash table, and these mappings replace all mappings that this hash table has for all keys in the currently specified mapping. If the specified map is NULL, a NullPointerException is thrown.
public synchronized void putAll(Map<? extends K, ? extends V> t) {
// The internal processing is very simple, just loop through the set of parameters, and then call the put method to add nodes one by one
for (Map.Entry<? extends K, ? extends V> e : t.entrySet())
put(e.getKey(), e.getValue());
}
Copy the code2.6 the remove method
public synchronized V remove(Object key)
Removes the key and its corresponding value from the hash table. If the key is not in the hash table, this method does nothing. If the key is NULL, a NullPointerException is thrown.
The remove method is relatively simple, which is to first calculate the bucket position of key, then loop through the linked list of this position, find the node with the same key, remove this node and return value. If not found, return null.
public synchronized V remove(Object key) { Entry<? ,? > tab[] = table;// Locate the bucket according to the key
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
// Get the list head node at that location
Entry<K, V> e = (Entry<K, V>) tab[index];
// Select * from the list where the key is the same as the hashcode and equals ()
// Use prev to save the predrive of e
for (Entry<K, V> prev = null; e ! =null; prev = e, e = e.next) {
/* If the keys are the same, then */ is found
if ((e.hash == hash) && e.key.equals(key)) {
modCount++;
// If the predrive is not null
if(prev ! =null) {
// Then the next node of the previous drive points to the next node of e
prev.next = e.next;
} else {
// Otherwise, the e.ext node is the head node and the e node is removed
tab[index] = e.next;
}
// Reduce the number of nodes by 1
count--;
// Return the value of the e node
V oldValue = e.value;
// Set value to null to facilitate GC collection
e.value = null;
returnoldValue; }}// But this step indicates that the same key is not found, and returns null
return null;
}
Copy the code2.7 the get method
public synchronized V get(Object key)
Returns the value to which the specified key is mapped, or null if the mapping does not contain a mapping for that key. If the key is NULL, a NullPointerException is thrown.
The get method is much simpler. It computes the hash value of the key, determines the index position in the table array, and iterates through the list until it finds an equal key, returning value, or null if it does not.
public synchronized V get(Object key) { Hashtable.Entry<? ,? > tab[] = table;int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
for(Hashtable.Entry<? ,? > e = tab[index]; e ! =null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return(V)e.value; }}return null;
}
Copy the code2.8 clear method
public synchronized void clear()
Clear the hash table. Loop to empty the array index position, and the GC will collect the list that is not referenced.
public synchronized void clear(a) { Entry<? ,? > tab[] = table; modCount++;// Loop to empty the index position of the array. The GC will collect the list that is not referenced
for (int index = tab.length; --index >= 0;) tab[index] =null;
/ / count set to 0
count = 0;
}
Copy the code2.9 Methods of traversal
Although the sets under the Map system do not have more advanced iterators (like liisiterator, which can add, delete, and look up data in an iterator), they do have their own methods of traversing and setting values.
There are four methods of traversing Hashtable. Three are implemented based on the Map interface: entrySet(), keySet(), and values(). One is born with elements() and keys().
We’ll focus on the traversal methods from the Map interface. We won’t cover much of the older methods:
Public synchronized Enumeration Elements () returns an Enumeration of values in this hash table. Public synchronized Enumeration keys() returns an Enumeration of the keys in this hash table.
2.9.1 Main class attributes
The first time a result view is requested through some traversal method, a view object is created and assigned to the corresponding field below for storage. Because these result views are directly related to the Map’s underlying hash table, changes to the hash table will be reflected in the result view’s traversal. So later call the same method, directly return the result view has been generated, do not need to create a new view object, very clever!
/* Save the result view returned by the keySet method */
private transient volatile Set<K> keySet;
/* Save the result view returned by the entrySet method */
private transient volatile Set<Map.Entry<K, V>> entrySet;
/* Save the result view returned by the values method */
private transient volatile Collection<V> values;
Copy the codeThe following int constants are mainly used for the collection of views returned by the keySet, values, and entrySet methods. When the collection of views gets an iterator, it actually calls the same iterator method internally: GetIterator (int type), which returns the same iterator implementation, returns a different result based on the iterator type passed in when the iterator was built! The specific judgment rules are explained in the section of “Map.entry <K,V> interface”.
/* The returned iterator collection type */
// The set of iterators used by the set returned by the keyset method
private static final int KEYS = 0;
// The Collection of iterators used by the Collection returned by the values method
private static final int VALUES = 1;
// Set of iterators used by the set returned by the entrySet method
private static final int ENTRIES = 2;
Copy the code2.9.2 entrySet method
public synchronized Set<Map.Entry<K,V>> entrySet()
Returns a set of key-value key-value pairs contained in this Map. Remove, Set. Remove, removeAll, retainAll, and clear operations are supported. That is, this set supports element removal, removing the corresponding mapping from the mapping, but it does not support add or addAll operations.
2.9.2.1 entrySet method
First look at the source code for the entrySet method:
public Set<Map.Entry<K, V>> entrySet() {
// Check whether the entrySet view is null
if (entrySet == null)
// If null indicates that the entrySet method has been called for the first time, then the attempt object is created and assigned to the entrySet field
entrySet = Collections.synchronizedSet(new EntrySet(), this);
// Return the entrySet view object
return entrySet;
}
Copy the codeWe see that the synchronizedSet method of the Collections utility class is actually called internally. This method will be wrapped around the original collection and return a new synchronized wrapped collection of type synchronizedSet that operates on elements using the same methods as the original collection that was called. The set passed in here is an EntrySet.
2.9.2.2 EntrySet Internal class
Look at the source code for EntrySet:
private class EntrySet extends AbstractSet<Map.Entry<K.V>> {
/** * Supports iterator operations */
public Iterator<Map.Entry<K, V>> iterator() {
return getIterator(ENTRIES);
}
/** * does not support add or addAll operations, because its add method calls methods of the parent class AbstractSet, and the implementation of the add method in AbstractSet throws an exception */
public boolean add(Map.Entry<K, V> o) {
return super.add(o);
}
/** * supports the contains operation. In fact, the underlying operation is the table array */
public boolean contains(Object o) {
if(! (oinstanceof Map.Entry))
return false; Map.Entry<? ,? > entry = (Map.Entry<? ,? >)o; Object key = entry.getKey(); Hashtable.Entry<? ,? >[] tab = table;int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
for(Hashtable.Entry<? ,? > e = tab[index]; e ! =null; e = e.next)
if (e.hash==hash && e.equals(entry))
return true;
return false;
}
/** * supports the remove operation. In fact, the underlying operation is the table array */
public boolean remove(Object o) {
if(! (oinstanceof Map.Entry))
return false; Map.Entry<? ,? > entry = (Map.Entry<? ,? >) o; Object key = entry.getKey(); Hashtable.Entry<? ,? >[] tab = table;int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Hashtable.Entry<K,V> e = (Hashtable.Entry<K,V>)tab[index];
for(Hashtable.Entry<K,V> prev = null; e ! =null; prev = e, e = e.next) {
if (e.hash==hash && e.equals(entry)) {
modCount++;
if(prev ! =null)
prev.next = e.next;
else
tab[index] = e.next;
count--;
e.value = null;
return true; }}return false;
}
/** * Support size operation **@return* /
public int size(a) {
return count;
}
/** * Supports the clear operation */
public void clear(a) {
Hashtable.this.clear(); }}Copy the codeEntrySet indicates the set set of the Map key-value pair object (map.entry <K, V>).
The EntrySet here is actually an inner class in a Hashtable, and the methods that operate on the elements are based on the underlying Hashtable.
Remove, Set. Remove, removeAll, retainAll, and clear. This Set supports the removal of elements and can remove the corresponding mapping from the mapping.
The Add or addAll operations are not supported because its add methods call methods of the parent class AbstractSet, and the implementation of the add methods in the AbstractSet is to throw exceptions.
2.9.2.3 synchronizedSet method
Take a look at the Collections. SynchronizedSet source code:
/** * return a synchronization set **@paramS original set *@paramThe object that a mutex uses as a lock *@returnThe new collection to be synchronized is SynchronizedSet */
static <T> Set<T> synchronizedSet(Set<T> s, Object mutex) {
return new SynchronizedSet<>(s, mutex);
}
/** * SynchronizedSet (); /** * SynchronizedSet ()
static class SynchronizedSet<E> extends SynchronizedCollection<E> implements Set<E> {
private static final long serialVersionUID = 487447009682186044L;
SynchronizedSet(Set<E> s) {
super(s);
}
SynchronizedSet(Set<E> s, Object mutex) {
super(s, mutex);
}
public boolean equals(Object o) {
if (this == o)
return true;
synchronized (mutex) {
returnc.equals(o); }}public int hashCode(a) {
synchronized (mutex) {
returnc.hashCode(); }}}/** * SynchronizedCollection implements most of the methods used to synchronize a collection. * Its methods of the same name are all methods of the set of passed (first argument) that are called, and it uses the passed second argument as the lock object to synchronize the methods of the block. * This is actually an application of the Java design pattern, "Decorative design pattern" */
static class SynchronizedCollection<E> implements Collection<E>, Serializable {
private static final long serialVersionUID = 3053995032091335093L;
// The first argument, the original set
final Collection<E> c; // Backing Collection
// The second argument is used as the lock
final Object mutex; // Object on which to synchronize
SynchronizedCollection(Collection<E> c) {
this.c = Objects.requireNonNull(c);
mutex = this;
}
SynchronizedCollection(Collection<E> c, Object mutex) {
this.c = Objects.requireNonNull(c);
this.mutex = Objects.requireNonNull(mutex);
}
/** * Decorative method after strengthening **@return* /
public int size(a) {
/ / the synchronized block
synchronized (mutex) {
// Call the method that decorates the collection
returnc.size(); }}public boolean isEmpty(a) {
synchronized (mutex) {
returnc.isEmpty(); }}public boolean contains(Object o) {
synchronized (mutex) {
returnc.contains(o); }}/ /.....................
}
Copy the codeFrom the source code can see, in fact, the Collections. SynchronizedSet method, is a decorative design model, the method of passing a EntrySet object and this object, and then return a synchronizedSet object, the object inside the two parameters of the incoming saved Its method of the same name, the bottom or call EntrySet object method of the same name, and the use of this object as a lock, so that the completion of the EntrySet object method decoration strengthening, to achieve synchronization!
2.9.2.4 Map. Entry < K, V > interface
We see that the elements of the returned set are of type Map.entry <K,V>, which actually represent the mapping entries (key-value pairs) in the set. A map. Entry object represents a key-value pair. How does this key-value pair relate to an Entry node object in a Hashtable?
In fact, map. Entry goes back to the very top, it appears on the Map interface, and it serves as the internal interface of the Map interface. Now we can guess that this Entry interface is actually the super interface of the nodes in the Map collection system. The map.entry interface needs to be implemented by the internal node classes of the concrete implementation class of Map.
Here we know that the map. Entry object we get actually returns the node objects of the Map implementation class, and in Hashtable we get the Entry node (the Entry inner class that implements the Map.entry interface). In HashMap we get the Node Node (the Node inner class also implements the Map.entry interface)…
The map. Entry interface provides the following methods, which are also methods of the Entry node, as described earlier in the introduction of the Entry inner class:
| boolean | Equals (Object O) Compares the equality of a specified Object to this item. |
| K | GetKey () returns the key corresponding to this item. |
| V | GetValue () returns the value corresponding to this item. |
| int | HashCode () returns the hashCode value for this mapping entry. |
| V | SetValue (V value) Replaces the value corresponding to this item with the specified value (optional). |
Map.entry is obtained from the iterator(int Type) method of the set set obtained through the entrySet() method. The iterator method of EntrySet is implemented as follows:
public Iterator<Map.Entry<K,V>> iterator() {
return getIterator(ENTRIES);
}
Copy the codeWe can see that the type passed in is “ENTRIES”, so the element type obtained by the iterator will be an Entry.
In fact, the inner Enumerator iterator returns different elements depending on the type passed in:
return type == KEYS ? (T)e.key : (type == VALUES ? (T)e.value : (T)e);
Copy the codeAs you can see, if it is of type KEYS, then the key of the entry node is returned; Return the value of the entry node if it is of type VALUES; Otherwise, it’s ENTRIES, and the entry node is returned directly.
2.9.3 keySet method
public synchronized Set keySet()
Returns the set of keys in this hash table.
Looking at the source code for keySet, you can see that it is very similar to the source code for EntrySet:
public Set<K> keySet(a) {
if (keySet == null)
keySet = Collections.synchronizedSet(new KeySet(), this);
return keySet;
}
Copy the codeThe same decorative design pattern is used, but here the decorated class becomes the KeySet class. Remove, Set. Remove, removeAll, retainAll, and clear are also supported. That is, this set supports element removal, removing the corresponding mapping from the mapping, but it does not support add or addAll operations.
private class KeySet extends AbstractSet<K> {
/** * Get the iterator for the set KeySet. You can see the type KEYS passed in */
public Iterator<K> iterator(a) {
return getIterator(KEYS);
}
/** * Supports the size operation */
public int size(a) {
return count;
}
/** * supports the contains operation, which actually calls the containsKey method */ of the external Hashtable class
public boolean contains(Object o) {
return containsKey(o);
}
/** * supports the remove operation, which actually calls the added hashtable. this before the remove method * of the external class Hashtable. The prefix is used to guide calls to methods of the same name */ of the external class
public boolean remove(Object o) {
return Hashtable.this.remove(o) ! =null;
}
/** * supports the clear operation, which actually calls the clear method of the external class Hashtable * added before hashtable.this. The prefix is used to guide calls to methods of the same name */ of the external class
public void clear(a) {
Hashtable.this.clear(); }}Copy the code2.9.4 values method
public synchronized Collection values()
Returns a Collection of values in this hash table.
Looking at the source code for VALUES, you can see that it is very similar to the source code for EntrySet and keySet:
public Collection<V> values(a) {
if (values==null)
values = Collections.synchronizedCollection(new ValueCollection(), this);
return values;
}
Copy the codeThe same decorative design pattern is used, but here the decorated class becomes a ValueCollection class. Remove, collection. remove, removeAll, retainAll, and clear are also supported for the Collection. That is, this Collection supports element removal and can remove the corresponding mapping from the mapping, but it does not support add or addAll operations.
Note that since values in the Map can be equal, the collection. remove method here removes the first equal key-value pair found.
3. Similarities, differences and applications of HashMap and Hashtable
3.1 Similarities and Differences between JDK1.8-based HashMap and Hashtable
Similarities:
- Both are Map interface implementation classes, belong to the set of Map system, can store key and value pairs, both belong to the implementation of hash table, stored key and value pairs are unordered.
Difference:
- Overall: HashMap is a new class added to JDK1.2. All implementations of the methods in the class are asynchronous, data insecure, and efficient. Hashtable is an inherent class in JDK1.0. All methods in the class are implemented synchronously, making the data safe and inefficient.
- Whether to allow NULL: The key and value of a HashMap are allowed to be null. Hashtable keys and values are not allowed to be null;
- Traversal mode: hashMap has three traversal modes of the Map interface: keySet(), values(), and entrySet(). In addition to the three traversal modes of the Map interface, Hashtable also has its own keys() and elements() methods to traverse the Map.
- Initial capacity: The default initial capacity of a HashMap is 11; The default initial capacity of Hashtable is 16.
- Hash algorithm: The hash algorithm of a HashMap perturbates the hash value of the key (JDK1.8 is 1 bit + 1 XOR), and then uses the result sum (capacity -1) to perform the & operation. The Hashtable hash algorithm takes & of the hash value of the key and the maximum int value (0x7FFFFFFF), and uses the result to take a % remainder of the capacity. There is no perturbation, so the elements of the HashMap are more evenly distributed (perturbation allows the hash values to be divided more regularly).
- Expansion increment: The capacity of Hashtable after expansion is doubled by 1. The capacity of the HashMap is twice that of the original capacity. The capacity of a HashMap must be a power of two, whether it is the initial capacity or the expanded capacity. The initial capacity of a Hashtable is not required.
- Data structure: in JDK1.8, HashMap uses an array + linked list + red-black tree data structure to implement the Hashtable, while Hashtable uses an array + linked list data structure to implement the Hashtable. The implementation of HashMap is more complex, but the lookup efficiency is higher.
- Inserting a node: in JDK1.8, HashMap inserts a new node using “tail insert” and Hashtable inserts a new node using “head insert”. In fact, before JDK1.8, HashMap was also used to insert element nodes by head interpolation, but in JDK1.8, it is changed to tail interpolation, because the head interpolation may form a circular list in multithreaded operation, resulting in an infinite loop, but because Hashtable is thread safe, so no change is needed!
3.2 Application of HashMap and Hashtable
In a single-threaded environment, HashMap is recommended because there is no synchronization and the underlying data structure is more advanced and faster; In a concurrent environment, you cannot use HashMap, but you are also not recommended to use Hashtable, because Hashtable locks the entire method, the Lock granularity is too large, only one Lock, serious performance impact, recommended to use ConcurrentHashMap under the JUC package, which uses Lock and CAS mechanism. Reduced lock granularity, multiple locks, and increased concurrency!
If you don’t understand or need to communicate, you can leave a message. Also hope to like, collect, follow, I will continue to update a variety of Java learning blog!