CODEWITHSUNDEEP
data-structureshashhashtable
CuriousMind
CuriousMind

Reputation: 8903

Hashtable underlying place holder?

I am trying to understand the HashTable data structure. I understand that in HashTable we first use HashFunction to coverts a key to hash Code and then using modulo operator to convert Hash code to integer index and which is used to get the location in HashTable where data is placed.

At a high level, the flow is like this?

Key -> Hash Function -> Hash code -> Modulo operator -> integer index -> Store in HashTable

Since the key is stored based on the index as emitted by the modulo operator, my doubt is, what is the underlying data structure which is used to hold the actual data? Is it an array, for array can be accessed using Index.

Can anyone help me understand this?

Upvotes: 0

Views: 67

Answers (1)

miradham
miradham

Reputation: 2345

Though it completely depends on implementation, I would agree that underlying data structure would be array with linked list, since array is convinient to access elements at low cost, while linked list is necessary to handle hash collisions.

Here is example of details how it is implemented in java openjdk Hashtable
Initially it creates array with initial capacity:

table = new Entry<?,?>[initialCapacity];

It checks for capacity threshold everytime when new element is added. When threshold limit is reached it performs rehashing and creates a new array which is double size of old array

    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<?,?>[] newMap = new Entry<?,?>[newCapacity];

    modCount++;
    threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    table = newMap;

Hashtable Entry forms a linked list. It is used in case of hash collisions, since index for 2 different values would become same and required value is checked through linked list.

private static class Entry<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Entry<K,V> next;

You may want to check other more simple implementations of Hashtables for better understanding.

Upvotes: 1

Related Questions