HashTable

What is hash-table ? It is key-value data structure , it is really good for lookup data in the HashTable.

• Is super fast lookup – O(1)
• Know what hashing is
• Collisions are handled via chaining
• Index (not hashing) used for lookup

Example code

public class HashTable {
    private static int INITIAL_SIZE = 16;

    private HashEntry[] data;

    public HashTable() {
        this.data = new HashEntry[INITIAL_SIZE];
    }

    public void put(String key, String value) {
        // Get index
        int index = getIndex(key);

        HashEntry entry = new HashEntry(key, value);

        if(data[index] == null) {
            data[index] = entry;
        } else { // Handle collision by adding to end of linked list
            HashEntry entries = data[index];
            while (entries.next !=null) {
                entries = entries.next;
            }
            // Add our new entry
            entries.next = entry;
        }
    }

    public String get(String key) {
        int index = getIndex(key);

        // Get the current list of entries
        HashEntry entries = data[index];

        if(entries!=null) {
            while (!entries.key.equals(key) && entries.next !=null) {
                entries = entries.next;
            }
            return entries.value;
        }
        return null;
    }

    private int getIndex(String key) {
        int hashCode = key.hashCode();
        int index = (hashCode & 0x7fffffff) % INITIAL_SIZE;

        // Hack Collision keys
        if(key.equals("Kevin") || key.equals("John")) {
            index = 4;
        }
        return index;
    }

    private static class HashEntry {
        String key;
        String value;
        HashEntry next;

        public HashEntry(String key, String value) {
            this.key = key;
            this.value = value;
            this.next = null;
        }
    }
}

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

public class HashTableTest {
    private HashTable objectUnderTest;

    @BeforeEach
    void setUp() {
        objectUnderTest = new HashTable();
    }

    @Test
    void testPutAndGet() {
        objectUnderTest.put("John", "421-1111");
        objectUnderTest.put("Kevin", "421-2131");
        objectUnderTest.put("Joe", "421-453");
        objectUnderTest.put("Robert", "421-123123");
        objectUnderTest.put("Vincent", "421-2132");

        Assertions.assertEquals("421-1111", objectUnderTest.get("John"));
        Assertions.assertEquals("421-2131", objectUnderTest.get("Kevin"));
        Assertions.assertEquals("421-453", objectUnderTest.get("Joe"));
        Assertions.assertEquals("421-123123", objectUnderTest.get("Robert"));
        Assertions.assertEquals("421-2132", objectUnderTest.get("Vincent"));
    }

    @Test
    void testCollision() {
        // these keys will collide
        objectUnderTest.put("John", "421-1111");
        objectUnderTest.put("Kevin", "421-2131");

        Assertions.assertEquals("421-1111", objectUnderTest.get("John"));
        Assertions.assertEquals("421-2131", objectUnderTest.get("Kevin"));
    }
}