HashTable is pass

JAVA COLLECTIONS source

1. What is HashTable

• The underlying hash table is used to store key-value pairs that are not null
• Use synchronized to ensure thread safety

2. Data structure of HashTable

• The class definition

      

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

• Important global variable

      

       
//The hash table data.
       
// The bottom layer maintains an Entry array
       
private transient Entry<K.V> [] table;
       
//The total number of entries in the hash table.
       
// Total number of elements, equivalent to the size of the HashMap
       
private transient int count;
       
//The load factor for the hashtable.
       
// Load factor
       
private float loadFactor;
       
/ * *
       
 * The table is rehashed when its size exceeds this threshold.
       
 * (The value of this field is (int)(capacity * loadFactor).)
       
* Rehash when the threshold is exceeded
       
* /
       
private int threshold;
       
/ * *
       
  * The number of times this Hashtable has been structurally modified
       
  * Structural modifications are those that change the number of entries in
       
  * the Hashtable or otherwise modify its internal structure (e.g.,
       
* rehash). This field is used to make iterators on Collection-views of
       
* the Hashtable fail-fast. (See ConcurrentModificationException).
       
* The fail-fast mechanism for traversal takes effect when modCount counts +1 for structural changes
       
* /
       
private transient int modCount = 0;
      

• The constructor

      

       
/ * *
       
* initialCapacity Default 11
       
* loadFactor defaults to 0.75
       
* /
       
public Hashtable(a) {
       
    this(11. 0.75 f);
       
}
       
/ * *
       
* Basically consistent with JDK1.7's HashMap
       
* @param initialCapacity The default capacity is 11
       
* @param loadFactor the loadFactor defaults to 0.75
       
* /
       
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);
       
        // The difference is that cap is not forced to power 2. When initCap=0, it defaults to 1
       
        if (initialCapacity= =0)
       
            initialCapacity = 1;
       
        this.loadFactor = loadFactor;
       
        table = new Entry[initialCapacity];
       
        threshold = (int)Math.min(initialCapacity * loadFactor. MAX_ARRAY_SIZE + 1);
       
        UseAltHashing: Boolean; if true, execute another hashed string key to reduce hash collisions due to weak hash calculations
       
        useAltHashing = sun.misc.VM.isBooted(a) &&
       
                (initialCapacity > = Holder.ALTERNATIVE_HASHING_THRESHOLD);
       
}
      

3. The HashTable of storage

• Put method parsing

      

       
public synchronized V put(K key. V value) {
       
    // Make sure the value is not null
       
    if (value = = null) {
       
        throw new NullPointerException(a);
       
    }
       
    // Makes sure the key is not already in the hashtable.
       
    // Make sure the key is not in the hashtable
       
    // First, hash the key and index to determine its position in table[]
       
    // Next, iterate over the list at the index position. If the list at that position has the same key, replace value and return the old value
       
    Entry tab[] = table;
       
    int hash = hash(key);
       
    // Calculate the subscript, using the % method, which is nowhere near as good as the bitwise operations of HashMap (one of the reasons HashTable is not recommended)
       
    int index = (hash & 0x7FFFFFFF) % tab.length;
       
    for (Entry<K.V> e = tab[index] ; e ! = null ; e = e.next) {
       
        / / use equals more directly, and much HashMap layer address is ` ((k = e.k ey) = = key | | key. Equals (k)) `
       
        if ((e.hash = = hash) && e.key.equals(key)) {
       
            V old = e.value;
       
            e.value = value;
       
            return old;
       
        }
       
    }
       
    // Structural change operation modCount counts +1
       
    modCount+ +;
       
    // select addEntry to encapsulate the logic
       
    if (count > = threshold) {
       
        // Rehash the table if the threshold is exceeded
       
        // If the threshold is exceeded, rehash is performed
       
        rehash(a);
       
        tab = table;
       
        hash = hash(key);
       
        index = (hash & 0x7FFFFFFF) % tab.length;
       
    }
       
    // Creates the new entry.
       
    // Insert the value, return null
       
    Entry<K.V> e = tab[index];
       
    // Create a new Entry node, insert the new Entry into the index position of the Hashtable, and set e to the next element of the new Entry
       
    tab[index] = new Entry< > (hash. key. value. e);
       
    //size++
       
    count+ +;
       
    return null;
       
}
      

• Rehash method resolution

      

       
protected void rehash(a) {
       
    int oldCapacity = table.length;
       
    Entry<K.V> [] oldMap = table;// Use temporary copies to keep current data timely (see JAVA's 'observer' mode implementation)
       
    // overflow-conscious code
       
    // Double the original capacity +1
       
    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<K.V> [] newMap = new Entry[newCapacity];
       
    // Rehash is also a structural change, modCount counts +1
       
    modCount+ +;
       
    threshold = (int)Math.min(newCapacity * loadFactor. MAX_ARRAY_SIZE + 1);
       
    boolean currentAltHashing = useAltHashing;
       
    useAltHashing = sun.misc.VM.isBooted(a) && (newCapacity > = Holder.ALTERNATIVE_HASHING_THRESHOLD);
       
    boolean rehash = currentAltHashing ^ useAltHashing;
       
    table = newMap;
       
    // iterate over the old array and reassign to the new array
       
    for (int i = oldCapacity ; i-- > 0 ;) {
       
        for (Entry<K.V> old = oldMap[i] ; old ! = null ; ) {
       
            Entry<K.V> e = old;
       
            old = old.next;
       
            if (rehash) {
       
                e.hash = hash(e.key);// rehash
       
            }
       
            // It's still the % operation
       
            int index = (e.hash & 0x7FFFFFFF) % newCapacity;
       
            e.next = newMap[index];
       
            newMap[index] = e;
       
        }
       
    }
       
}
      

• Get method parsing

      

       
public synchronized V get(Object key) {
       
    Entry tab[] = table;// Use temporary copies to keep current data timely (see JAVA's 'observer' mode implementation)
       
    int hash = hash(key);
       
    int index = (hash & 0x7FFFFFFF) % tab.length;
       
    for (Entry<K.V> e = tab[index] ; e ! = null ; e = e.next) {
       
        if ((e.hash = = hash) && e.key.equals(key)) {
       
            return e.value;
       
        }
       
    }
       
    return null;
       
}
      

4. The HashTable iteration

• A Hashtable can be traversed in several ways:

      

       
//1, use keys()
       
Enumeration<String> en1 = table.keys(a);
       
    while(en1.hasMoreElements()) {
       
    en1.nextElement(a);
       
}
       
//2.
       
Enumeration<String> en2 = table.elements(a);
       
    while(en2.hasMoreElements()) {
       
    en2.nextElement(a);
       
}
       
// select * from keySet();
       
Iterator<String> it1 = table.keySet().iterator(a);
       
    while(it1.hasNext()) {
       
    it1.next(a);
       
}
       
// use entrySet()
       
Iterator<Entry<String. String>> it2 = table.entrySet().iterator(a);
       
    while(it2.hasNext()) {
       
    it2.next(a);
       
}
      

5. Comparison of HashTable and HashMap

• HashTable is based on the Dictionary class, while HashMap is based on AbstractMap. Dictionary is the abstract parent of any class that maps keys to corresponding values, and AbstractMap is an implementation based on the Map interface to minimize the effort required to implement this interface.
• The key and value of a HashMap can be null, while the key and value of a Hashtable cannot be null. When a HashMap encounters a null key, putForNullKey is called (put it into table[0]), but value is not processed. When Hashtable encounters null, NullPointerException is returned.
• The Hashtable method is synchronous, while the HashMap method is not. Nearly all public methods in a Hashtable are synchronized, and some methods are implemented internally with synchronized code blocks.
• HashTable, due to its use of sync and % operations (and associated algorithmic implementations), has a lower performance than HashMap, and is therefore highly discouraged from continuing to use HashTable. HashMap is recommended in non-competitive environments. ConcurrentHashMap is recommended in multi-threaded environments

notice