Novice source code hashtable

HashTable ：key,value Neither can it be. null; Thread safety .（ If thread safety is not required , You should use HashMap, If thread safety is needed , have access to ConcurrentHashMap,HashTable It is estimated that we will withdraw from the stage of history ）
As key The object must be implemented hashCode Methods and equals Method .
The default load factor is 0.75, Too small will lead to frequent allocation of space , Too much will increase the search time .
If you know you want to put it in one time HashTable A lot of elements , You can specify a relatively large initialization capacity , This can avoid many times rehashing To increase the capacity of the table .

HashTable Inheritance structure

HashTable Member variables

// Hash table data 
private transient Entry<?,?>[] table;
// The amount of data in the hash 
private transient int count;
//  threshold （capacity * loadFactor）, When the table size Over this threshold , will rehash To increase the capacity of the table 
private int threshold;
// Load factor 
private float loadFactor;
// Number of changes 
private transient int modCount = 0;
// serialize id
private static final long serialVersionUID = 1421746759512286392L;

HashTable The data structure of the node , Single chain list

 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;
        }
   // Omit other methods 
   ...
 }

HashTable Constructor for

public Hashtable() {
    
    this(11, 0.75f);
}

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

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;
    // initialization table
    table = new Entry<?,?>[initialCapacity];
    // to threshold assignment 
    threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
}

In short, initialization function is initialization table object , And give threshold assignment .

HashTable Member method of , Why thread safety , Methods have been prefixed with synchronized.

/** * key,value Neither can it be. null. Method returns null perhaps key The previous one in the position value. */
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;
    //key Not for null
    int hash = key.hashCode();
    // Calculate the storage location 
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    Entry<K,V> entry = (Entry<K,V>)tab[index];
    // Traversing the linked list 
    for(; entry != null ; entry = entry.next) {
    
        // There are the same elements , Update element returns oldValue
        if ((entry.hash == hash) && entry.key.equals(key)) {
    
            V old = entry.value;
            entry.value = value;
            return old;
        }
    }
    // Add a new element 
    addEntry(hash, key, value, index);
    return null;
}

• First look at the position to insert index Element exists on entry, If there is , Just traverse backward entry.
• If meet (entry.hash == hash) && entry.key.equals(key), Replace the old value with the new value , And return the old value .
• If the position index There is no element on entry, Just call addEntry Method to insert the element , return null;

addEntry(hash, key, value, index) Method

private void addEntry(int hash, K key, V value, int index) {
    
    // Structural modification 
    modCount++;

    Entry<?,?> tab[] = table;
    if (count >= threshold) {
    
        //  If the number of elements exceeds the threshold , Just rehash, Increase the capacity of the table 
        rehash();

        tab = table;
        hash = key.hashCode();
        index = (hash & 0x7FFFFFFF) % tab.length;
    }

    //  Create a new one Entry object , Insert index Location , Be careful tab[index] by null
    Entry<K,V> e = (Entry<K,V>) tab[index];
    tab[index] = new Entry<>(hash, key, value, e);
    count++;
}

• Number of changes plus 1.
• If the number of elements exceeds the threshold , Just rehash, Increase the capacity of the table , And recalculate index.
• Create a new one Entry object , Insert index Location , Number of elements plus 1.

HashTable Of putAll(Map<? extends K, ? extends V> t) Method , Internally, it is a traversal call HashTable Of put(K key, V value) Method .

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

HashTable Of get(Object key) 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;
}

• according to key Value calculation hash value , Then find the storage location index, If index There are elements in position entry, Just traverse backward , If the element is satisfied e(e.hash == hash) && e.key.equals(key)), Just go back to e Of value.
• Otherwise return to null.

HashTable Of containsValue(Object value) Method

public boolean containsValue(Object value) {
    
    return contains(value);
}

HashMap Of contains(Object value) Method

public synchronized boolean contains(Object value) {
    
    if (value == null) {
    
        throw new NullPointerException();
    }

    Entry<?,?> tab[] = table;
    for (int i = tab.length ; i-- > 0 ;) {
    
        for (Entry<?,?> e = tab[i] ; e != null ; e = e.next) {
    
            if (e.value.equals(value)) {
    
                return true;
            }
        }
    }
    return false;
}

• Traverse from back to front table, If i Element on location entry, Just traverse backward entry, If there are elements e Satisfy e.value.equals(value), Just go back to true.
• Go back if you can't find it false.
  HashTable Of containsKey(Object key) Method

public synchronized boolean containsKey(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 true;
        }
    }
    return false;
}

• according to key Hash value of , Find the corresponding index, If index There are elements in position e, Just traverse backward e. If there is an element that satisfies (e.hash == hash) && e.key.equals(key) Just go back to true.
• Go back if it doesn't exist false.

HashTable Of clear function , There's nothing to say , Increase the number of changes , Set the element in each position to null, The number of elements is set to 0.

public synchronized void clear() {
    
    Entry<?,?> tab[] = table;
    modCount++;
    for (int index = tab.length; --index >= 0; )
        tab[index] = null;
    count = 0;
}

HashTable Of rehash() Method

protected void rehash() {
    
    int oldCapacity = table.length;
    Entry<?,?>[] oldMap = table;
    // The new capacity is table Twice the capacity +1
    int newCapacity = (oldCapacity << 1) + 1;
    // Ensure that the maximum length is less than or equal to Integer.MAX_VALUE - 8
    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];
    // Number of changes plus 1
    modCount++;
    // Back to the threshold assignment 
    threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    // Give Way table Point to newMap
    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;
        }
    }
}

• Calculate the new capacity newCapacity , original table The length of *2+1. If the maximum new capacity cannot exceed MAX_ARRAY_SIZE（Integer.MAX_VALUE - 8）
• Create a new length of newCapacity Of newMap, Increase the number of changes , Back to the threshold assignment , Give Way table Point to newMap.
• Traverse from back to front old table, If i There are elements in position , find i The last element in position , Recalculate index, And then let i The last element in position points to newMap[index]（newMap[index] At this time null）, And then to newMap[index] The assignment is e.

for instance , As shown in the figure below

In the example above , Only index=0 There is data on the location of

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

 The result of the traversal is 
 When i=1;i-->0 When ,index=0 There are elements in the position of 
 Go to the second level for loop 

(Entry<K,V> old = oldMap[0] = {hello->world->null};old!=null;){
	...
}

1.  The first 1 Time to traverse the ,old = hello->world->null

e=hello->world->null;
old=world->null;

int index = (e.hash & 0x7FFFFFFF) % newCapacity;// Suppose the newly calculated index The value of 5, And this index There's no element in it 

e.next = (Entry<K,V>)newMap[5];//e=hello->null;
newMap[5] = e;//newMap[5] = hello->null;

2.  The first 2 Time to traverse the ,old=world->null

e=world->null;
old=null;

int index=5;
e.next = (Entry<K,V>)newMap[5];//e=world->hello->null;
newMap[5] = e;//newMap[5]=world->hello->null;

3.  The first 3 Secondary cycle  old=null;  end 

The results after traversal are as follows , Will flip the linked list at the corresponding position