Hashtable source code analysis

hash The data structure of the table ： Array + Linked list

Class inheritance

public class Hashtable<K,V>
    extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable

• Dictionary It's an abstract class ,jdk Inheritance is no longer recommended

Attributes of a class

// Entity object 
private transient Entry<?,?>[] table;
    private static class Entry<K,V> implements Map.Entry<K,V> {
    
        final int hash;
        final K key;
        V value;
        Entry<K,V> next;
}
// Number of objects 
private transient int count;
// again hash Threshold of 
private int threshold;
// Load factor 
private float loadFactor;
// When it comes to re hash When , Let the iterative process fail quickly 
private transient int modCount = 0;

Construction method

    public Hashtable() {
    
        this(11, 0.75f);
    }
    public Hashtable(int initialCapacity) {
    
        this(initialCapacity, 0.75f);
    }
    public Hashtable(Map<? extends K, ? extends V> t) {
    
        this(Math.max(2*t.size(), 11), 0.75f);
        putAll(t);
    }
    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;
        this.loadFactor = loadFactor;
        table = new Entry<?,?>[initialCapacity];
        // Set threshold , If you exceed the threshold, you have to re hash
        threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    }

• If no size is specified default hash The size is 16
• The loading factor is 0.75
• The default threshold is initialCapacity * loadFacto , stay 16 When 12 It will be expanded and then re hash

Some basic methods

rehash Method

    protected void rehash() {
    
         // Original array size 
        int oldCapacity = table.length;
         // Original array 
        Entry<?,?>[] oldMap = table;
        // overflow-conscious code
        // The new size is twice +1
        int newCapacity = (oldCapacity << 1) + 1;
        // It is used to judge whether the maximum value 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;
        }
        Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];

        modCount++;
        // Recalculate the threshold , It's still the length * Load factor 
        threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
        table = newMap;
        // The original hash The objects in the table are moved to the new hash In the table . Start with the tail 
        for (int i = oldCapacity ; i-- > 0 ;) {
    
            // It's head insertion 
            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;
            }
        }
    }

add Method

// The first parameter is to call hashCode Of hash code , The second parameter is key, The third is vaule, The fourth is in hash In the table index Subscript 
private void addEntry(int hash, K key, V value, int index) {
    modCount++;
    Entry<?,?> tab[] = table;
   // If the threshold is exceeded , Is to rehash
    if (count >= threshold) {
        // Rehash the table if the threshold is exceeded
        rehash();
        // again hash after , Some properties also need to be reassigned 
        tab = table;
        hash = key.hashCode();
        index = (hash & 0x7FFFFFFF) % tab.length;
    }

    // Creates the new entry.
    @SuppressWarnings("unchecked")
    // The head insertion method is also used here , see entry You can also see the construction method of 
    Entry<K,V> e = (Entry<K,V>) tab[index];
    tab[index] = new Entry<>(hash, key, value, e);
    count++;
}

*hash The method of adding nodes to a table is header insertion

put Method

     // Use here Synchronized Lock method to ensure put Method in multi-threaded data security 
    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;
        // produce hash
        int hash = key.hashCode();
        // Hash the hash function 
        int index = (hash & 0x7FFFFFFF) % tab.length;
        @SuppressWarnings("unchecked")
       // Get the node of the subscript 
        Entry<K,V> entry = (Entry<K,V>)tab[index];
        for(; entry != null ; entry = entry.next) {
    
             // If you have this value , Set the original value to the new value , And switch back to the original value 
            if ((entry.hash == hash) && entry.key.equals(key)) {
    
                V old = entry.value;
                entry.value = value;
                return old;
            }
        }
        // If this value doesn't exist , Then return to null And add the new value to hashtable in 
        addEntry(hash, key, value, index);
        return null;
    }

• hashtable No null values are allowed

get Method

    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;
    }

• adopt key Of hash Value to find the corresponding subscript , And then compare hash and key Whether they are equal to determine whether they exist .

equals Method

    // Compare the two hashtable Is it like waiting 
    public synchronized boolean equals(Object o) {
    
      
        if (o == this)
            return true;
        // No inheritance map Then return to false
        if (!(o instanceof Map))
            return false;
        Map<?,?> t = (Map<?,?>) o;
        if (t.size() != size())
            return false;

        try {
    
            // Call iterator 
            Iterator<Map.Entry<K,V>> i = entrySet().iterator();
            while (i.hasNext()) {
    
                Map.Entry<K,V> e = i.next();
                K key = e.getKey();
                V value = e.getValue();
                if (value == null) {
    
                    if (!(t.get(key)==null && t.containsKey(key)))
                        return false;
                } else {
    
                    if (!value.equals(t.get(key)))
                        return false;
                }
            }
        } catch (ClassCastException unused)   {
    
            return false;
        } catch (NullPointerException unused) {
    
            return false;
        }

        return true;
    }

remove Method

    // remove key Equal to the given key The elements of 
    public synchronized V remove(Object key) {
    
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        @SuppressWarnings("unchecked")
        Entry<K,V> e = (Entry<K,V>)tab[index];
        // Through the idea of double pointers 
        for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) {
    
            if ((e.hash == hash) && e.key.equals(key)) {
    
                modCount++;
                // If it's not the first element , So let the element in front of it point to the element behind it , And set your own value to null
                if (prev != null) {
    
                    prev.next = e.next;
                } else {
    
                  // If it's the first element , The header element is the next node of the object 
                    tab[index] = e.next;
                }
                count--;
                V oldValue = e.value;
                e.value = null;
                return oldValue;
            }
        }
        return null;
    }
    // remove key and value Are equivalent elements , Compared with the above, I judged once more value
    @Override
    public synchronized boolean remove(Object key, Object value) {
    
        Objects.requireNonNull(value);

        Entry<?,?> tab[] = table;
        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) {
    
            if ((e.hash == hash) && e.key.equals(key) && e.value.equals(value)) {
    
                modCount++;
                if (prev != null) {
    
                    prev.next = e.next;
                } else {
    
                    tab[index] = e.next;
                }
                count--;
                e.value = null;
                return true;
            }
        }
        return false;
    }