JDK collection source HashTable parsing

HashTable

HashMap

As can be seen from the figure, both of them are derived from the Map interface, and both of them implement Cloneable and Serializable interfaces. Both of them can be cloned and serialized. But AbstractMap is the parent of HashMap, and Dictionary is the parent of HashTable.

The Dictionary class is a deprecated class (see comments in its source code). The parent class is deprecated, so its subclass Hashtable is used less often.

Put (); put(); put();

public synchronized V put(K key, V value) {
    // Value cannot be null; otherwise, a null pointer exception is thrown
    if (value == null) {
        throw new NullPointerException();
    }
    // Makes sure the key is not already in the hashtable.Entry<? ,? > tab[] = table;// Key cannot be considered null, because a null call to hashCode() raises a null pointer exception when key is null
    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;
}
Copy the code

In a HashMap, NULL can be used as a key, and only one such key can exist. There can be one or more keys with a value of NULL. When the get() method returns a NULL value, the key may not exist in the HashMap, or the value corresponding to the key may be NULL. Therefore, instead of using the get() method to determine the presence of a key in a HashMap, use the containsKey() method.

• The default initial size of a Hashtable is11After each expansion, the capacity becomes the same2n+1.
• The default initialization size of a HashMap is16. And each time you expand it, you get the same capacity2Times.

When created, if given an initial capacity value, the Hashtable will use the size you gave it, and the HashMap will expand it to a power of two. In other words, Hashtable uses prime and odd numbers as much as possible. A HashMap, on the other hand, always uses a power of 2 as its hash table size.

The difference is due to the different priorities that Hashtable and HashMap were designed with. The focus of Hashtable is to make hash results more uniform, resulting in less hash collisions. Simple modular hashing is more uniform when the hash table is prime in size. HashMap, on the other hand, is more concerned with the computational efficiency of hash. In modular calculation, if the modulus is a power of two, then we can directly use bitwise operations to get the result, which is much more efficient than division. A HashMap fixes the size of a hash table to a power of two in order to speed up hash. Of course, this introduces the problem of uneven hash distribution, so HashMap makes some changes to the hash algorithm to solve this problem. This results in different ways of calculating hash values for hashTables and HashMaps.

public Hashtable(int initialCapacity, float loadFactor) {
	 // Verify the initial capacity
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    // Verify the load factor
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal Load: "+loadFactor);

    if (initialCapacity==0)
        initialCapacity = 1;
    this.loadFactor = loadFactor;
    // Initialize the table and get the table array of size initialCapacity
    table = newEntry<? ,? >[initialCapacity];// Calculate the threshold --> threshold = "capacity * load factor"
    threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
}

public Hashtable(int initialCapacity) {
    this(initialCapacity, 0.75 f);
}

// Empty parameter constructor, initial capacity 11
public Hashtable(a) {
    this(11.0.75 f);
}

// Initialize the HashTable directly based on the incoming Map set. The capacity is the size of the incoming Map set *2 compared with 11, whichever is larger
public Hashtable(Map<? extends K, ? extends V> t) {
    this(Math.max(2*t.size(), 11), 0.75 f);
    putAll(t);
}

private int hash(Object k) {
     return hashSeed ^ k.hashCode();
}
Copy the code

// Obtain synchronized locks
public synchronized V put(K key, V value) {
    // Throw an exception if value is null
    if (value == null) {
        throw new NullPointerException();
    }
    // Makes sure the key is not already in the hashtable.Entry<? ,? > tab[] = table;// Calculate key hash and index
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    Entry<K,V> entry = (Entry<K,V>)tab[index];
    // Iterate through the list at the corresponding index position
    for(; entry ! =null ; entry = entry.next) {
        // If the key already exists, update the data
        if ((entry.hash == hash) && entry.key.equals(key)) {
            V old = entry.value;
            entry.value = value;
            returnold; }}// Add a new Entry element
    addEntry(hash, key, value, index);
    return null;
}
Copy the code

private void addEntry(int hash, K key, V value, int index) {
    // Number of changes ++modCount++; Entry<? ,? > tab[] = table;// The current capacity exceeds the threshold and needs to be expanded
    if (count >= threshold) {
        // Rehash the table if the threshold is exceeded
        // Rebuild the bucket array (equivalent to expansion method) and rehash all the key/value pairs in the array, time
        rehash();

        tab = table;
        // Get the hash value based on the key
        hash = key.hashCode();
        // Fetch operation (equivalent to HashMap locating bucket slot)
        // int index = (hash & 0x7FFFFFFF) % tab.length; ?????
        // The first 31 1 bits represent a numeric value. In computers, the highest 32 bits of an integer are the symbol bits 0 for a positive number and 1 for a negative number.
        // 0x7FFFFFFF: hexadecimal integer, which is the largest integer
        // 0x7FFFFFFF: 0111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111: all 1s except the sign bit
        // (hash & 0x7FFFFFFF) will produce a positive integer
        // (hash & 0x7FFFFFFF) % tab.length will be within the tag length range
        // If all hashtables are odd, there will be fewer hash collisions. If all hashtables are even, there will be more hash collisions
        // h & (length-1); A Hashmap takes the same approach, so taking a power of two length causes less conflict
        index = (hash & 0x7FFFFFFF) % tab.length;
    }

    // Creates the new entry.
    @SuppressWarnings("unchecked")
    // Get the list of entries in the bucket in slot INDEX. The head node is e
    Entry<K,V> e = (Entry<K,V>) tab[index];
    // Create a new node and insert the new node at the head of the list. The next node is e
    tab[index] = new Entry<>(hash, key, value, e);
    // Number of valid elements ++
    count++;
}
Copy the code

Equivalent to the resize() method in hashMap

protected void rehash(a) {
    // Get the size of the current table array.
    int oldCapacity = table.length;
    // oldMap: current table arrayEntry<? ,? >[] oldMap = table;// Expand the capacity to double the original +1 --> that is, expand the capacity to 2n +1 to ensure that the capacity is odd
    // Odd numbers help index = (hash & 0x7FFFFFFF) % tab.length to reduce hash collisions when seeking buckets
    // This is similar to HashMap: hash & (tab.length-1), which ensures a power of 2 to reduce hash collisions
    int newCapacity = (oldCapacity << 1) + 1;
    // Determine whether the maximum capacity is exceeded
    if (newCapacity - MAX_ARRAY_SIZE > 0) {
        if (oldCapacity == MAX_ARRAY_SIZE)
            // Keep running with MAX_ARRAY_SIZE buckets
            return;
        newCapacity = MAX_ARRAY_SIZE;
    }
    // newMap: new table arrayEntry<? ,? >[] newMap =newEntry<? ,? >[newCapacity];// Number of changes to the HashTable structure ++
    modCount++;
    // Calculate the threshold for the next rehash
    threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    table = newMap;

    // Rehash the old hash pair into the new hash table.
    // This method is similar to HashMap, which assigns data from the old array to the new array.
    // In the HashMap, each bucket bit of the old array is further 'smashed' and placed on the corresponding bucket bit of the new array (there is a recalculation of the bucket bit)
    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;// Recalculate the bucket size based on newCapacity
            int index = (e.hash & 0x7FFFFFFF) % newCapacity;
            e.next = (Entry<K,V>)newMap[index];
            // Add the list to the bucketnewMap[index] = e; }}}Copy the code

public synchronized V get(Object key) {// Select index by key
      Entry tab[] = table;  
      int hash = hash(key);// Compute the hash value based on the key
      int index = (hash & 0x7FFFFFFF) % tab.length;// Find index based on hash value
      for(Entry<K,V> e = tab[index] ; e ! =null ; e = e.next) {// Iterate through the entry chain
          if ((e.hash == hash) && e.key.equals(key)) {// If the key is found
              return e.value;// Return the corresponding value}}return null;// Otherwise null is returned
  }  
Copy the code

public synchronized V remove(Object key) { Entry<? ,? > tab[] = table;// Calculate key hash and index
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    Entry<K,V> e = (Entry<K,V>)tab[index];
    for(Entry<K,V> prev = null; e ! =null ; prev = e, e = e.next) {
        // Traverses the list of corresponding positions to find the node to be deleted
        if ((e.hash == hash) && e.key.equals(key)) {
            modCount++;
			  // Update next of the precursor node to point to next of e
           if(prev ! =null) {
                prev.next = e.next;
            } else {
                tab[index] = e.next;
            }
            count--;
            V oldValue = e.value;
            e.value = null;
            // Returns the value of the node to be deleted
            returnoldValue; }}// If it does not exist, return null
    return null;
}
Copy the code