HashTable.java

package com.anthonynsimon.datastructures;

import com.anthonynsimon.datastructures.util.HashTableNode;

import java.util.ArrayList;

public class HashTable<K, V> {

    protected final double maxLoadFactor = 0.75d;
    protected final int capacityGrowth = 2;
    protected final int initialCapacity;
    protected int size;
    protected int currentCapacity;
    protected ArrayList<HashTableNode<K, V>> buckets;

    public HashTable() {
        this(16);
    }

    // Initialize with desired initial number of buckets
    public HashTable(int initialCapacity) {
        this.initialCapacity = nearestPowerOfTwo(initialCapacity);
        resetHashTable();
    }

    protected static int nearestPowerOfTwo(int value) {
        int pow = 0;
        while (value >> 1 > 0) {
            value >>= 1;
            pow++;
        }
        return 1 << pow;
    }

    protected void resetHashTable() {
        this.size = 0;
        this.currentCapacity = this.initialCapacity;
        this.buckets = new ArrayList<>(this.initialCapacity);
        // Initialize all buckets to null
        for (int i = 0; i < this.currentCapacity; i++) {
            this.buckets.add(null);
        }
    }

    // Returns the value stored under the given key, if found
    public V get(K key) {
        HashTableNode<K, V> result = getNodeWithKey(key);
        return result != null ? result.getValue() : null;
    }

    protected void ensureCapacity(int intendedCapacity) {
        double loadFactor = (double) intendedCapacity / (double) currentCapacity;
        // If we're within the load limit, return early, it's all good.
        if (loadFactor < maxLoadFactor) {
            return;
        }

        // Otherwise, ensure we will be within limits
        int newCapacity = currentCapacity * capacityGrowth;
        buckets.ensureCapacity(newCapacity);

        // Initialize buckets
        for (int i = this.currentCapacity; i < newCapacity; i++) {
            this.buckets.add(null);
        }

        currentCapacity = newCapacity;
    }

    // Inserts a Key, Value pair into the table
    public void put(K key, V value) throws IllegalArgumentException {
        // No support for null as key
        if (key == null) {
            throw new IllegalArgumentException("key cannot be null");
        }

        ensureCapacity(size() + 1);

        // Hash the key and get the bucket index
        int bucketIndex = getBucketIndex(key);

        HashTableNode<K, V> newNode = new HashTableNode<>(key, value);
        HashTableNode<K, V> current = buckets.get(bucketIndex);

        // If bucket is empty, set as first node and we're done
        if (current == null) {
            buckets.set(bucketIndex, newNode);
            this.size++;
            return;
        }

        // Traverse the list within the bucket until match or end found
        while (current != null) {
            // When a key match is found, replace the value it stores and break
            if (current.getKey().equals(key)) {
                current.setValue(value);
                break;
            }
            // When the last node of the list is reached, append new node here and break
            else if (current.getNext() == null) {
                current.setNext(newNode);
                this.size++;
                break;
            }
            current = current.getNext();
        }
    }

    // Removes the Key, Value pair based on the provided Key
    public void remove(K key) {
        if (size() == 0 || key == null) {
            return;
        }

        int bucketIndex = getBucketIndex(key);

        HashTableNode<K, V> current = buckets.get(bucketIndex);
        HashTableNode<K, V> previous = null;

        // Traverse the list inside the bucket until match is found or end of list reached
        while (current != null) {
            if (current.getKey().equals(key)) {
                // Handle case when node is first in bucket
                if (previous == null) {
                    // If there is a next node, set next node as first in bucket
                    if (current.getNext() != null) {
                        buckets.set(bucketIndex, current.getNext());
                    }
                    // If there is no other node in list, simply set bucket to null
                    else {
                        buckets.set(bucketIndex, null);
                    }
                }
                // Handle case when node is not in first position
                else {
                    // If it's the last node in the list, set previous's next as null
                    if (current.getNext() == null) {
                        previous.setNext(null);
                    }
                    // If it's anywhere else in the list, connect previous and next
                    else {
                        previous.setNext(current.getNext());
                    }
                }

                // We're done removing the node, diminish size and return
                this.size--;
                return;
            }

            previous = current;
            current = current.getNext();
        }
    }

    // Returns array of all values in table
    // Traverse each bucket and add value to results
    public V[] values() {
        // It is safe to suppress unchecked exception because the array we're creating
        // is of the same type as the one passed.
        @SuppressWarnings("unchecked")
        V[] values = (V[]) new Object[size()];

        if (size() > 0) {
            int index = 0;
            for (int i = 0; i < buckets.size(); i++) {
                HashTableNode<K, V> current = buckets.get(i);

                while (current != null) {
                    values[index] = current.getValue();
                    index++;
                    current = current.getNext();
                }
            }
        }

        return values;
    }

    // Returns array of all keys in table
    // Traverse each bucket and add key to results
    public K[] keys() {
        // It is safe to suppress unchecked exception because the array we're creating
        // is of the same type as the one passed.
        @SuppressWarnings("unchecked")
        K[] keys = (K[]) new Object[size()];

        if (size() > 0) {
            int index = 0;
            for (int i = 0; i < buckets.size(); i++) {
                HashTableNode<K, V> current = buckets.get(i);

                while (current != null) {
                    keys[index] = current.getKey();
                    index++;
                    current = current.getNext();
                }
            }
        }

        return keys;
    }

    // Returns if some node in table contains provided key
    public boolean containsKey(K key) {
        HashTableNode<K, V> result = getNodeWithKey(key);
        return result != null;
    }

    // Returns if some node in table contains provided value
    public boolean containsValue(V value) {
        HashTableNode<K, V> result = getNodeWithValue(value);
        return result != null;
    }

    // Returns the total number of Key, Value pairs in the table
    public int size() {
        return this.size;
    }

    // Empty out the table
    public void clear() {
        resetHashTable();
    }

    // Hash the key and find the appropriate bucket index
    protected int getBucketIndex(K key) {
        // Rehash to protect against poor hash functions
        int rehashed = hash(key.hashCode());
        // Capacity is always a power of two, use fast modulo operation
        return rehashed & (this.currentCapacity - 1);
    }

    protected int hash(int h) {
        h ^= (h >> 20) ^ (h >> 12);
        return h ^ (h >> 7) ^ (h >> 4);
    }

    // Returns the node with the matching key, if any
    // Searches only inside the appropriate bucket
    private HashTableNode<K, V> getNodeWithKey(K key) {
        if (size() == 0 || key == null) {
            return null;
        }

        int bucketIndex = getBucketIndex(key);
        HashTableNode<K, V> current = buckets.get(bucketIndex);

        while (current != null) {
            if (current.getKey().equals(key)) {
                return current;
            }
            current = current.getNext();
        }

        return null;
    }

    // Returns the node with the matching value, if any
    // Must search the entire table since the value doesn't give us
    // a clue about a possible bucket
    private HashTableNode<K, V> getNodeWithValue(V value) {
        if (size() == 0) {
            return null;
        }

        for (int i = 0; i < buckets.size(); i++) {
            HashTableNode<K, V> current = buckets.get(i);

            while (current != null) {
                if (current.getValue().equals(value)) {
                    return current;
                }
                current = current.getNext();
            }
        }

        return null;
    }
}