Hashtable

1. The Hashtable statement

public class Hashtable<K,V> extends Dictionary<K,V> implements Map<K,V>, Cloneable, Java.io.Serializable {} // Key-value pair /Entry array, each Entry is essentially a unidirectional linked list header private TRANSIENT Entry<? ,? >[] table; // If the number of entries in the current table exceeds the threshold, the number of entries will be expanded. // Rehash threshold private int threshold; // Private float loadFactor; // The number of times the HashMap data has been modified. This variable is used in the fail-fast mechanism during iteration. Its purpose is to ensure that if a thread safety problem occurs, it can be detected in a timely manner (the count backed up before operation is not equal to the current modCount) and throw an exception abort operation. private transient int modCount = 0;Copy the code

Like a HashMap, a Hashtable is a Hashtable that stores a key-value mapping. Hashtable inherits from Dictionary and implements Map, Cloneable, java.io.Serializable interfaces

2. Construction method

Public Hashtable(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal Load: "+loadFactor); if (initialCapacity==0) initialCapacity = 1; // assign loadFactor this.loadFactor = loadFactor; Table = new Entry<? ,? >[initialCapacity]; -8+1 threshold = (int) math. min(initialCapacity * loadFactor, MAX_ARRAY_SIZE +1); } public Hashtable(int initialCapacity) {this(initialCapacity, 0.75f); Public Hashtable() {this(11, 0.75f);} public Hashtable() {this(11, 0.75f); } // We can see that the size of 2 is the size of Map, or 11 is the size of 11, and call the putall method to store the value, which we will learn later. public Hashtable(Map<? extends K, ? Extends V> t) {this(math.max (2*t.size(), 11), 0.75f); putAll(t); }Copy the code
  • The default size of Hashtable is 11 and the default load factor is 0.75.(The default size of HashMap is 16 and the default load factor is 0.75)
  • The capacity of a Hashtable can be any integer, with a minimum of 1, whereas the capacity of a HashMap is always 2 to the power of n.
  • Like a HashMap, a Hashtable has a static class called Entry inside it, which is essentially a key-value pair object that holds references to keys and values.

3.put(K key, V value)

Public synchronized V put(K key, V value) { If (value == null) {throw new NullPointerException(); } // Makes sure the key is not already in the hashtable. Entry<? ,? > tab[] = table; int hash = key.hashCode(); // Calculate the hash value of the key and mod it to get the hash bucket position. int index = (hash & 0x7FFFFFFF) % tab.length; @SuppressWarnings("unchecked") Entry<K,V> entry = (Entry<K,V>)tab[index]; // walk through the list for(; entry ! = null ; If ((entry-hash == hash) && entry-key.equals (key)) {V old = entry.value; entry.value = value; return old; } } addEntry(hash, key, value, index); return null; } private void addEntry(int hash, K key, V value, int index) {modCount++ modCount++; Entry<? ,? > tab[] = table; // If the actual capacity exceeds the threshold, expand the capacity. If (count >= threshold) {// Rehash the table if the threshold is exceeded Rehash (); tab = table; hash = key.hashCode(); // Recalculate the position of the element index = (hash & 0x7FFFFFFF) % tab.length; } / / Creates the new entry. @ SuppressWarnings (" unchecked ") entry / / remove the current position of the element < K, V > e = (entry > < K, V) TAB [index]; TAB [index] = new Entry<>(hash, key, value, e); count++; } protected void rehash() {oldCapacity = table.length; / Record old bucket array Entry<? ,? >[] oldMap = table; Int newCapacity = (oldCapacity << 1) +1; If (newCapacity -max_array_size > 0) {// The capacity must not exceed the agreed maximum if (oldCapacity == MAX_ARRAY_SIZE) // Keep running with MAX_ARRAY_SIZE buckets return; newCapacity = MAX_ARRAY_SIZE; } // Create an expanded array Entry<? ,? >[] newMap = new Entry<? ,? >[newCapacity]; modCount++; // change the new threshold size to newCapacity * loadFactor threshold = (int) math. min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1); table = newMap; For (int I = oldCapacity; i-- > 0 ;) { for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old ! = null ; ) { Entry<K,V> e = old; old = old.next; Int index = (e.hash & 0x7FFFFFFF) % newCapacity; E.next = (Entry<K,V>)newMap[index]; newMap[index] = e; }}} public synchronized void putAll(map <? extends K, ? extends V> t) { for (Map.Entry<? extends K, ? extends V> e : t.entrySet()) put(e.getKey(), e.getValue()); }Copy the code
  • New nodes are always inserted at the head of the list.
  • I’m going to expand the array by 2 times 1, but the other thing that’s important is that when I expand the array, I insert new elements by head insertion, so they go in reverse order.

4.get(Object key)

public synchronized V get(Object key) { Entry<? ,? > tab[] = table; int hash = key.hashCode(); 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; }Copy the code
  • The get operation is relatively simple. It iterates through the linked list using the hash value of the key and returns immediately if it finds a key. If it does not find a key, it returns NULL.

5. To summarize

In fact, hashTable and hashMap are similar, the structure is relatively simple, not one by one analysis. Here’s the difference between hashMap and hashTable:

  • HashTable is thread-safe and ensures synchronization, whereas hashMap is not thread-safe.
  • A hashTable cannot hold null values and null keys. A hashMap can have one NULL key and multiple NULL values.
  • The default size of hashTable is 11, and the default size of hashMap is 16, and the default size of hashMap is 2 to the NTH power.