5.4 Hashtable

1. What Is It?

A thread-safe hash map.

2. How to Use It

public class HashtableTest
{
    public static void main(String[] args) throws InterruptedException
    {
        Hashtable<Integer, Integer> map = new Hashtable<>();
        Thread thread1 = new Thread(()->{
            for (int i = 0; i < 100000; i++)
            {
                map.put(i, i);
            }
        });

        Thread thread2 = new Thread(()->{
            for (int i = 100000; i < 200000; i++)
            {
                map.put(i, i);
            }
        });

        thread1.start();
        thread2.start();
        thread1.join();
        thread2.join();
        System.out.println(map);
        System.out.println(map.size());
        for (int i = 0; i < 200000; i++)
        {
            if (!map.contains(i))
            {
                throw new RuntimeException("Concurrent put has a problem");//No exception means concurrent put worked here.
            }
            System.out.println(map.remove(i));
        }
    }
}

3. Implementation Analysis

3.1. UML

It is cloneable, serializable, and implements the Map interface.

3.2. Constructor

Hash collisions are resolved with separate chaining using singly linked lists.

The initial capacity is 11 and the default load factor is 0.75.

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

    // Implemented with an Entry array.
    private transient Entry<?,?>[] table;

    // Actual number of elements in the map.
    private transient int count;

    // These two determine when expansion occurs.
    private int threshold;
    private float loadFactor;

    private transient int modCount = 0;

    public Hashtable() {
        // Initial capacity is 11 and load factor is 0.75.
        this(11, 0.75f);
    }

    public Hashtable(int initialCapacity, float loadFactor) {
        // Validate arguments.
        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;
        // Create table array.
        table = new Entry<?,?>[initialCapacity];
        threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    }
}

3.3. put Method

// synchronized
public synchronized V put(K key, V value) {
    // Make sure the value is not null.
    // Unlike HashMap, Hashtable does not allow a null value.
    if (value == null) {
        throw new NullPointerException();
    }

    // Makes sure the key is not already in the hashtable.
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    // Calculate bucket index.
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    Entry<K,V> entry = (Entry<K,V>)tab[index];
    // Traverse the linked list until an equal node is found or the end is reached.
    for(; entry != null ; entry = entry.next) {
        // Found it: replace value.
        if ((entry.hash == hash) && entry.key.equals(key)) {
            V old = entry.value;
            entry.value = value;
            return old;
        }
    }

    // Not found: create a node and add it to the list.
    addEntry(hash, key, value, index);
    return null;
}

3.3.1. synchronized Locking

public synchronized V put(K key, V value) {
//...
}

3.3.2. Calculate Which Bucket / Linked List the key Belongs To

Entry<?,?> tab[] = table;
int hash = key.hashCode();
// Uses modulo by array length rather than a bitwise mask.
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];

3.3.3. Traverse the Linked List Until an Equal Node Is Found or the End Is Reached

for(; entry != null ; entry = entry.next) {
    if ((entry.hash == hash) && entry.key.equals(key)) {
        V old = entry.value;
        entry.value = value;
        return old;
    }
}

3.3.4. If Not Found, Create a Node and Insert It at the Head

• addEntry

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

    Entry<?,?> tab[] = table;
    // Determine whether expansion is needed.
    if (count >= threshold) {
        // Rehash the table if the threshold is exceeded
        rehash();

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

    // Creates the new entry.
    @SuppressWarnings("unchecked")
    Entry<K,V> e = (Entry<K,V>) tab[index];
    // Create a new node and put it directly at the corresponding array position.
    tab[index] = new Entry<>(hash, key, value, e);
    count++;
}

3.3.4.1. Expansion

• rehash

@SuppressWarnings("unchecked")
protected void rehash() {
    int oldCapacity = table.length;
    Entry<?,?>[] oldMap = table;

    // overflow-conscious code
    // New capacity = old capacity * 2 + 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;
    }
    // Create a new array with the new capacity.
    Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];

    modCount++;
    threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    table = newMap;
    // Traverse the Entry array from back to front.
    for (int i = oldCapacity ; i > 0 ;) {
        // Traverse each linked list.
        for (Entry<K,V> old = (Entry<K,V>)oldMap[--i] ; old != null ; ) {
            // e is the node being migrated; old is the next node to migrate.
            Entry<K,V> e = old;
            old = old.next;

            // Calculate e's position in the new Entry array.
            int index = (e.hash & 0x7FFFFFFF) % newCapacity;
            // Point e.next to the current head node at that position.
            e.next = (Entry<K,V>)newMap[index];
            // Make e the new head node.
            newMap[index] = e;
        }
    }
}

3.4. get Method

// synchronized
public synchronized V get(Object key) {
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    // Calculate which linked list to inspect.
    int index = (hash & 0x7FFFFFFF) % tab.length;
    // Traverse the linked list and find an equal node.
    for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            return (V)e.value;
        }
    }
    return null;
}

3.4.1. synchronized Locking

public synchronized V get(Object key) {
}

3.4.2. Calculate Which Bucket / Linked List the key Belongs To

Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;

3.4.3. Traverse Until an Equal Node Is Found or the End Is Reached

for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
    if ((e.hash == hash) && e.key.equals(key)) {
        return (V)e.value;
    }
}

3.5. remove Method

It is declared with synchronized.

Like get, it first finds the node. Deletion is an ordinary linked-list node deletion.

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];
    for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            modCount++;
            if (prev != null) {
                // Not the head node.
                prev.next = e.next;
            } else {
                // Head node.
                tab[index] = e.next;
            }
            count--;
            // help GC
            V oldValue = e.value;
            e.value = null;
            return oldValue;
        }
    }
    return null;
}

3.5.1. synchronized Locking

public synchronized V remove(Object key) {
}

3.5.2. Calculate Which Bucket / Linked List the key Belongs To

Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>)tab[index];

3.5.3. Traverse to the Node and Remove It

@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)) {
        modCount++;
        if (prev != null) {
            // Not the head node.
            prev.next = e.next;
        } else {
            // Head node.
            tab[index] = e.next;
        }
        count--;
        // help GC
        V oldValue = e.value;
        e.value = null;
        return oldValue;
    }
}

3.6. containsKey Method

// synchronized
public synchronized boolean containsKey(Object key) {
    // The following logic is the same as get.
    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;
}

3.6.1. synchronized Locking

public synchronized boolean containsKey(Object key) {
}

3.6.2. Calculate the Bucket

Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;

3.6.3. Traverse Until an Equal Node Is Found or the End Is Reached

for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
    if ((e.hash == hash) && e.key.equals(key)) {
        return true;
    }
}
return false;