Separate Chaining HashTable Implementation in JAVA

This is my Java implementation of the HashTable data structure with Separate Chaining as collision correction. Collision is minimized when the table size (threshold) is initialized as a prime number, so I chose 11. I am using the Java standard library ArrayList dynamic array as a buffer to hold the different HashNode chains. The indices of the buffer are the hash keys to each chain, which can be calculated by modulating the hash code of a HashNode's key by the threshold. The hash code in this implementation is generated by the standard hashCode method of the Java standard library. The methods the HashTable class supports are get, add, remove, and resize.

HashNode Definition

public static class HashNode<K, V> {
    K key;
    V data;
    HashNode<K, V> next;

    public HashNode(K k, V d) {
        key = k;
        data = d;
        next = null;
    }
}

HashTable Implementation

public static class HashTable<K, V> {
    private static final double LIMIT = 0.7;

    int usage;
    int threshold;
    ArrayList<HashNode<K, V>> table;

    public HashTable() {
        usage = 0;
        threshold = 11;
        table = new ArrayList<HashNode<K, V>>(threshold);

        for (int i = 0; i < threshold; i++) {
            table.add(null);
        }
    }

    public V get(K key) {
        if (key == null) return null;
        int i = key.hashCode() % threshold;
        i = Math.abs(i);
        HashNode<K, V> head = table.get(i);
        HashNode<K, V> cur = head;

        while (cur != null) {
            if (cur.key == key)
                return cur.data;

            cur = cur.next;
        }

        return null;
    }

    private void resize() {
        ArrayList<HashNode<K, V>> temp = table;
        usage = 0;
        threshold = threshold << 1;
        table = new ArrayList<HashNode<K, V>>(threshold);

        for (int i = 0; i < threshold; i++) {
            table.add(null);
        }

        for (HashNode<K, V> cur : temp) {
            while (cur != null) {
                put(cur.key, cur.data);
                cur = cur.next;
            }
        }
    }

    public void put(K key, V data) {
        if (key == null) return;
        int i = key.hashCode() % threshold;
        i = Math.abs(i);
        HashNode<K, V> head = table.get(i);
        HashNode<K, V> cur = head;

        while (cur != null) {
            if (cur.key == key) {
                cur.data = data;
                return;
            }

            cur = cur.next;
        }

        HashNode<K, V> entry = new HashNode<K, V>(key, data);
        entry.next = head;

        table.set(i, entry);

        if (head == null) usage++;

        if ((1.0 * usage)/threshold >= LIMIT) resize();
    }

    public V remove(K key) {
        if (key == null) return null;
        int i = key.hashCode() % threshold;
        i = Math.abs(i);
        HashNode<K, V> head = table.get(i);
        HashNode<K, V> cur = head;
        HashNode<K, V> prev = null;

        while (cur != null) {
            V data = cur.data;

            if (prev == null && cur.key.equals(key)) {
                if (cur.next == null) {
                    table.set(i, null);
                    usage--;
                }
                else {
                    table.set(i, cur.next);
                }

                return data;
            }

            if (cur.key.equals(key)) {
                prev.next = cur.next;
                return data;
            }

            prev = cur;
            cur = cur.next;
        }

        return null;
    }
}

This article is my 10th oldest. It is 342 words long, and it’s got 0 comments for now.