Phase to recommend

  • Java Collections Framework
  • (3) Detailed explanation of HashMap
  • (2) Detailed explanation of LinkedList
  • (a) ArrayList details

Summary of Hashtable

Hashtable is a set of two columns that implement the Map interface. The underlying implementation is based on the data structure of array + linked list, which is unordered and cannot store null values for keys and values. Hashtable is thread safe (based on synchronized implementation).

Hashtable underlying data structure

The Hashtable class diagram

The properties of Hashtable

public class Hashtable<K,V> extends Dictionary<K,V> implements Map<K,V>, Cloneable, Java.io.Serializable {// Hash bucket array to store key and value pairs private TRANSIENT Entry<? ,? >[] table; // Hash bucket array table number of key/value pairs private TRANSIENT int count; // Hash bucket array table Capacity expansion threshold //threshold= Capacity (array capacity) * loadFactor(loading factor) private int threshold; // private float loadFactor; Private TRANSIENT int modCount = 0; }Copy the code

Hashtable constructor

  • Construct an empty Hashtable using the default capacity (11) and loading factor (0.75 f)
Public Hashtable() {this(11, 0.75f); }Copy the code
  • Construct an empty Hashtable usingUser-defined initial capacity, the default load factor (0.75 f)
Public Hashtable(int initialCapacity) {this(initialCapacity, 0.75f); }Copy the code
  • Construct an empty Hashtable usingUser-defined initial capacityandCustom load factor
Public Hashtable(int initialCapacity, float loadFactor) {// if the initialCapacity is less than 0, If (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); // If the custom load factor is less than 0 or non-numeric, Is thrown IllegalArgumentException if (loadFactor < = 0 | | Float. The isNaN (loadFactor)) throw new IllegalArgumentException (" Illegal Load: "+loadFactor); If (initialCapacity==0) initialCapacity= 1; this.loadFactor = loadFactor; Table = new Entry<? ,? >[initialCapacity]; // Calculate the capacity expansion threshold = (int) math. min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1); }Copy the code

Static inner class Entry for Hashtable <K,V>

private static class Entry<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    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;
}
Copy the code

Hashtable put(K key, V value) method

  • put(K key, V value)The implementation adds an Entry key-value pair to the Hashtable, which is calledaddEntry()Method to implement specific add operations.
Public synchronized V put(K key, V value) { If (value == null) {throw new NullPointerException(); } // Determine if the key exists in the hash bucket array Entry<? ,? > tab[] = table; Int hash = key.hashcode (); Int index = (hash & 0x7fffff) % tab.length; int index = (hash & 0x7fffff) % tab.length; @suppressWarnings ("unchecked") // Discard the values of the table array index position into data of the Entry type. Entry<K,V> Entry = (Entry<K,V>) TAB [index]; // If the entry pair at index position is not empty, iterate through the list to find the entry pair with the same key for(; entry ! = null ; Entry = entry.next) {// If the hash value of the original key-value pair in the Hashtable is equal to the hash value of the key-value pair to be inserted // and the corresponding keys of the two key-value pairs are equal, then the value of the original key-value pair is overwritten. Without inserting if ((entry-hash == hash) && entry-key.equals (key)) {// Save the old value V old = entry.value; // Override the old value entry.value = value; // return old; AddEntry (hash, key, value, index); // Add a new key-value pair successfully, return null; }Copy the code
  • addEntry(int hash, K key, V value, int index)
Private void addEntry(int hash, K key, V value, int index) {// number of structural changes +1 modCount++; // Get the hash bucket array table Entry<? ,? > tab[] = table; // If the number of Entry key-value pairs in the hash bucket array is greater than threshold // Call rehash() to expand the capacity. If (count >= threshold) {// rehash the table if the threshold is  exceeded rehash(); Table TAB = table; // Retrieve the key hash = key.hashcode (); Index index = (hash & 0x7fffff) % tab.length; } @suppressWarnings ("unchecked") // Casting values of the index position to Entry<K,V> type Entry<K,V> e = (Entry<K,V>) TAB [index]; // Create an Entry key-value pair and store it at index position in the hash table TAB [index] = new Entry<>(hash, key, value, e); // the number of key-value pairs in the hash bucket array +1 count++; }Copy the code

Rehash ()

Expansion formula :(current hash bucket array capacity *2) + 1

protected void rehash() { int oldCapacity = table.length; Entry<? ,? >[] oldMap = table; Int newCapacity = (oldCapacity << 1) + 1; If (newCapacity -max_array_size > 0) {// If (oldCapacity ==) if (newCapacity -max_array_size > 0) {// If (oldCapacity ==) if (oldCapacity ==) MAX_ARRAY_SIZE) // Keep running with MAX_ARRAY_SIZE buckets return; NewCapacity = MAX_ARRAY_SIZE; newCapacity = MAX_ARRAY_SIZE; newCapacity = MAX_ARRAY_SIZE; } // Create an Entry array for newCapacity calculated above. ,? >[] newMap = new Entry<? ,? >[newCapacity]; +1 modCount++; // Recalculate capacity expansion threshold = (int) math. min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1); // Assign the expanded entry array to table. Table = newMap; For (int I = oldCapacity; for (int I = oldCapacity; i-- > 0 ;) {// Iterate over the linked list 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

Differences between Hashtable and HashMap

  • Thread-safe: HashMap is non-thread-safe, Hashtable is thread-safe; The methods inside a Hashtable are mostly synchronized modified. Here’s another article about synchronized:

  • Efficiency: Because of thread-safety issues, HashMap is a little more efficient than Hashtable. Also, Hashtable is largely obsolete, so don’t use it in your code; (Use ConcurrentHashMap if you want to be thread-safe);

  • Support for Null keys and Null values: In a HashMap, only one key can be Null, and one or more keys can be Null. However, no key value put into a Hashtable can be null; otherwise, a NullPointerException will be thrown.

  • The difference between the initial capacity and each capacity expansion:

  • If you do not specify an initial capacity when creating a Hashtable, the default initial size of the Hashtable is 11. After each expansion, the original capacity is 2N +1. The default size of a HashMap is 16, and it doubles in size each time it is expanded.

  • If you create a Hashtable with an initial capacity, the Hashtable will use the size you gave it, and the HashMap will expand it to a power of two. That is, a HashMap always uses a power of 2 as the size of the hash table.

  • Underlying data structure: HashMap since JDK1.8 has a major change in resolving hash collisions, converting lists to red-black trees to reduce search time when the list length is greater than the threshold (8 by default). Hashtable has no such mechanism.

  • Recommended use: As you can see in the class annotation of Hashtable, Hashtable is a reserved class and is not recommended to be used. It is recommended to use HashMap in single-threaded environments, or ConcurrentHashMap in multi-threaded environments.

Above is the introduction of Hashtable, if there is an error, please leave a message to correct…

Phase to recommend

  • Java Collections Framework
  • (3) Detailed explanation of HashMap
  • (2) Detailed explanation of LinkedList
  • (a) ArrayList details