1. An overview of theLast time we discussed the structure, principles, and implementation of HashMap. HashSet and HashMapBlog.csdn.net/qq_27574367…This article introduces HashTable, another commonly used collection of the Map family. HashTable and HashMap collections are very similar and are often asked by various interviewers about the differences between the two. The main differences between the two are as follows: HashMap is asynchronous and does not lock read and write operations, so it is thread unsafe. Data inconsistency may occur in multi-threaded scenarios. However, HashTable is synchronized, and all read and write operations are protected by synchronized, so there is no security problem in multi-threaded environment. However, lock protection comes at a cost, affecting read and write efficiency. In the HashMap structure, null is allowed. Entry. Key and Entry. However, null is not allowed in a HashTable. HashMap iterators are fail-fast iterators, but Hashtable iterators are not Fail-fast iterators. If there are other threads to add/remove elements, HashMap will throw ConcurrentModificationException, but the remove method remove elements of iterator itself will not throw an exception. This is also the difference between Enumeration and Iterator.Principle 2.In the HashTable class, the actual data is still stored in the Entry object. The data structure is the same as a HashMap.The HashTable class inherits from the Dictionary class and implements three interfaces, Map, Cloneable, and Java.io.Serializable, as shown in the figure below.The main methods in HashTable, such as PUT, GET, remove, and Rehash, are the same as those in HashMap and will not be described here3. Source code analysisThe source code implementation logic for the main methods of HashTable is very similar to that of HashMap, with one major difference being that all operations are protected by synchronized locks. Follow-up operations, such as read and write operations, can be performed only after the corresponding lock is obtained.1. Put methodThe main logic of the PUT method is as follows: Obtains a synchronized lock. The PUT method does not allow null values, and if null is found, an exception is thrown. If the same hash and key already exist, the value is updated and the old value is returned. If there is no Entry node with the same key, the addEntry method is called to add the node. In the addEntry method, expand if necessary and then add a new node to the head of the list.

public synchronized V put(K key, V value) { // Make sure the value is not null if (value == null) { throw new NullPointerException(); } // Makes sure the key is not already in the hashtable. Entry<? ,? > tab[] = table; int hash = key.hashCode(); int index = (hash & 0x7FFFFFFF) % tab.length; @SuppressWarnings("unchecked") Entry<K,V> entry = (Entry<K,V>)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; } } addEntry(hash, key, value, index); return null; } private void addEntry(int hash, K key, V value, int index) { modCount++; Entry<? ,? > tab[] = table; if (count >= threshold) { // Rehash the table if the threshold is exceeded rehash(); tab = table; hash = key.hashCode(); index = (hash & 0x7FFFFFFF) % tab.length; } // Creates the new entry. @SuppressWarnings("unchecked") Entry<K,V> e = (Entry<K,V>) tab[index]; tab[index] = new Entry<>(hash, key, value, e); count++; }Copy the code

The main logic of the GET method is as follows: Obtain a synchronized lock first. Compute the hash of key and index. Search for nodes with the same hash and key in the linked list at the corresponding position and return the value of the node. If no node is found at the end of the traversal, null is returned.

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

3. Rehash Expansion method The logic of rehash expansion method is as follows: The array length is doubled (if the array length exceeds the upper limit, the array length is set to the upper limit). Update the capacity expansion threshold of the hash table. Iterate over the nodes in the old table, calculate the index in the new table, and insert it into the head of the list at the corresponding position.

protected void rehash() { int oldCapacity = table.length; Entry<? ,? >[] oldMap = table; // overflow-conscious code int newCapacity = (oldCapacity << 1) + 1; if (newCapacity - MAX_ARRAY_SIZE > 0) { if (oldCapacity == MAX_ARRAY_SIZE) // Keep running with MAX_ARRAY_SIZE buckets return; newCapacity = MAX_ARRAY_SIZE; } Entry<? ,? >[] newMap = new Entry<? ,? >[newCapacity]; modCount++; 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; }}}Copy the code

4. Remove Method The logic of the remove method is as follows: Obtain a synchronized lock. Compute the hash of key and index. Traverse the linked list of the corresponding position to find the node to be deleted. If there is one, use E to represent the node to be deleted, and pre to represent the precursor node. If it does not exist, return NULL. Update next of the precursor node to point to next of E. Returns the value of the node to be deleted.

To sum up, the biggest feature of HashTable compared with HashMap is thread-safety. All operations are protected by synchronized locks