Java Hashtable Implementation using Array

A HashTable is a type of data structure used to store key-value pairs.

In this post, we will see how to write code to design our own HashTable using Java. We gonna use an Array to hold the entries. 

Java Hashtable Implementation using Array

To keep it simple we will design put() and get() methods to add and retrieve entry to/from the hash table:
public class HashTable<K, V> {
 
    private static final int SIZE = 10;

    private static class HashEntry<K, V> {

        K key;
        V value;

        HashEntry<K, V> next;

        HashEntry(K k, V v) {
            this.key = k;
            this.value = v;
            this.next = null;
        }

        @Override
        public String toString() {
            return "HashEntry{" + "key=" + key + ", value=" + value + ", next=" + next + '}';
        }

    }

    private final HashEntry[] entries = new HashEntry[SIZE];

    public void put(K key, V value) {

        int hash = getHash(key);
        
        final HashEntry hashEntry = new HashEntry(key, value);

        if (entries[hash] == null) {
            entries[hash] = hashEntry;
        } else { // collision => chaining
            HashEntry currentEntry = entries[hash];
            while (currentEntry.next != null) {
                currentEntry = currentEntry.next;
            }

            currentEntry.next = hashEntry;
        }
    }

    public V get(K key) {

        int hash = getHash(key);
        
        if (entries[hash] != null) {
            HashEntry currentEntry = entries[hash];

            // Check the entry linked list for matching the given 'key'
            while (currentEntry != null) {                

                if (currentEntry.key.equals(key)) {
                    return (V) currentEntry.value;
                }
                
                currentEntry = currentEntry.next;
            }
        }

        return null;
    }

    private int getHash(K key) {        
        return Math.abs(key.hashCode() % SIZE);
    }    
}
Let's test above hash table implementation using main() method:
public class Main {

    public static void main(String[] args) {

        HashTable hashTable = new HashTable();

        // Put some key-value
        hashTable.put("ana", "ana".toUpperCase());
        hashTable.put("carina", "carina".toUpperCase());
        hashTable.put("barbu", "barbu".toUpperCase());
        hashTable.put("leo", "leo".toUpperCase());
        hashTable.put("marius", "marius".toUpperCase());
        hashTable.put(5, "FIVE");
        hashTable.put(10, "TEN");

        // The following keys should exists
        System.out.println("Get(ana): " + hashTable.get("ana"));        
        System.out.println("Get(carina): " + hashTable.get("carina"));
        System.out.println("Get(barbu): " + hashTable.get("barbu"));
        System.out.println("Get(leo): " + hashTable.get("leo"));
        System.out.println("Get(marius): " + hashTable.get("marius"));
        System.out.println("Get(5): " + hashTable.get(5));
        System.out.println("Get(10): " + hashTable.get(10));
        
        // The following two keys should not exists
        System.out.println("Get(anna): " + hashTable.get("anna"));
        System.out.println("Get(15): " + hashTable.get(15));               
    }
}
Output:
Get(ana): ANA
Get(carina): CARINA
Get(barbu): BARBU
Get(leo): LEO
Get(marius): MARIUS
Get(5): FIVE
Get(10): TEN
Get(anna): null
Get(15): null
Note that we have used an array to store entries:
 private final HashEntry[] entries = new HashEntry[SIZE];
We have designed put() method to add an entry to a hash table:
public void put(K key, V value) {

        int hash = getHash(key);
        
        final HashEntry hashEntry = new HashEntry(key, value);

        if (entries[hash] == null) {
            entries[hash] = hashEntry;
        } else { // collision => chaining
            HashEntry currentEntry = entries[hash];
            while (currentEntry.next != null) {
                currentEntry = currentEntry.next;
            }

            currentEntry.next = hashEntry;
        }
    }
We have designed the get() method to get an entry from the hash table:
public V get(K key) {

        int hash = getHash(key);
        
        if (entries[hash] != null) {
            HashEntry currentEntry = entries[hash];

            // Check the entry linked list for matching the given 'key'
            while (currentEntry != null) {                

                if (currentEntry.key.equals(key)) {
                    return (V) currentEntry.value;
                }
                
                currentEntry = currentEntry.next;
            }
        }

        return null;
    }

Comments