Hashtable

Hashtable stores the key-value pairs using a hash table. Hashtable is one of the collection implementation classes which is a child class of the Map interface. Hashtable provides all the capabilities as HashMap but Hashtable is synchronized that makes Hashtable a thread-safe implementation. If there is a need to use a synchronized Map then it is recommended to use ConcurrentHashMap instead of Hashtable.

Internal Implementation details of Hashtable:

Hashtable stores the key-value pairs using a hash table. In the hash table each key-value pair is mapped corresponding to the hashcode derived from the key. Using the hashing techniques a hashcode is derived from the key and using the hashcode we identify the index in the bucket list of the hashtable. This bucket list is an array of the lists of key-value pairs corresponding to the hash codes.

Following diagram depicts the clear picture how internally key-value pairs are stored. First hash code is calculated for the keys. Using the hashcode, index is identified in the bucket array. Corresponding to the hashed index, key-value pair entry is stored in the list corresponding to that particular bucket.

So in Hashtable, at the first level we have an array. In the array, each array index is mapped to the hashcode derived from the key. Each array index ( or we can say each bucket ) contains a reference to a linked list in which we store the key-value pair entry.

For a key-value pair, first identify the hash code for the key using the hashcode() method. Once we have the hash code, index is calculated to identify the bucket in which the key-value pair will be stored. Once we have the bucket index, check for the entry list.

If we do not have the already existing list corresponding to that bucket index then we create a list and add the key-value pair entry to the list. And if already there is a list of the key-value entries then we go through the list check for key object if the key already exist and if key already exist then we override the value. If key is not there then a new entry is created for the key-value pair. New entry is then added to the list

Important HashMap Parameters :

Hashtable’s internal hash table.

            private transient Entry[] table;

The two parameters that affect the performance of HashMap are – initial capacity and load factor. Initial capacity is the initial size of the hash table and load factor is is a measure of how full the hash table is allowed to get before its capacity is automatically increased. Using the below Hashtable constructor, initialCapacity and loadFactor can be passed by a programmer.

	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];
        threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    }

Using the initial capacity and load factor, threshold is calculated. Threshold is the size limit after which table is resized/rehashed. The value of the threshold is (int)(capacity * loadFactor).

Threshold and loadFactor fields :

        private int threshold;
    	private float loadFactor;
    

Deafult value for initial capacity is 11 and default load factor is 0.75.
If Hashtable is created with the detault constructor, See below, default constructor internally passes the default vaoue to the above constructor.

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

Growing the Hashtable bucket :

Using the initial capacity and load factor, threshold is calculated.
Threshold is the size limit after which table is resized/rehashed. The value of the threshold is (int)(capacity * loadFactor).

Hashtable Entry class :

Hashtable internally maintains a hash table which is actually an array with the buckets. At each index position, each bucket contains a linkedlist for the key-value mappings.
This linked list is a bucket collision list. Since multiple keys can be mapped to the same hash code which results into the same index position which causes a conflict for the key-value entry object. Then there comes the linked list to the rescue.
Entry class defines a node which can be used to create a LinkedList as each Entry object contains a reference variable which can point to another Entry object.
A Hashtable Node is the child class of the Entry interface.
A Hashtable Node(Entry) stores hash, key, value and the next node reference. Hash is the hashcode of the key.
The reference points to the next node in the linkedlist of a particular bucket.

Node definition:

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

        @SuppressWarnings("unchecked")
        protected Object clone() {
            return new Entry<>(hash, key, value,
                                  (next==null ? null : (Entry<K,V>) next.clone()));
        }

        // Map.Entry Ops

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }

        public V setValue(V value) {
            if (value == null)
                throw new NullPointerException();

            V oldValue = this.value;
            this.value = value;
            return oldValue;
        }

        public boolean equals(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry e = (Map.Entry)o;

            return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&
               (value==null ? e.getValue()==null : value.equals(e.getValue()));
        }

        public int hashCode() {
            return hash ^ Objects.hashCode(value);
        }

        public String toString() {
            return key.toString()+"="+value.toString();
        }
    }

Insertion into Hashtable: : Adding key-value pair to the map using put method

put() method is used to add a key-value mapping to the Hashtable. Key and value are passed as parameters to the put() method.
For each key-value mapping, an Entry object is created and added to the hash table.
Entry object contains the four fields – key, value, hash and next
Key – passed key object to put method Value – passed value object to put method Hash – hash code of the key Next – pointer to next entry
Hashtable does not allow any null key or value to be inserted in table.
Maps the specified key to the valuein this hashtable.

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

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];
        threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    }

Getting the value from the Hashtable :
We can get the value for a specific key then using get method which accepts a key as parameter. Inside get method, hash code is calculated for the key Then indfex is determined using the hash code using the below statement inside get method:
int index = (hash & 0x7FFFFFFF) % tab.length; checks for the index in the table and checks for the node with the same hash and key. Iterates through the linked list of the nodes and if key is found at that particular index then return the value.
If key-value mapping does not exist then null is returned.
get() method is synchronized so if a thread executing inside get method, during that time no other thread can execute in get or any other method. No other read or update operations can be made to the hash table.

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