Implementing a Custom HashTable in Java

Custom HashTable Implementation in Java

This document provides a robust implementation of a HashTable in Java, demonstrating core concepts like load factors, capacity management, and collision handling.

Class Definition

public class HashTable1 implements IHashTable {
    private Entry1 table[];
    private int size;
    private final float loadFactor;
    private int threshold;
    private final int DEFAULT_INITIAL_CAPACITY = 12;
    private final float DEFAULT_LOAD_FACTOR = 0.75f;

    public HashTable1() {
        loadFactor = DEFAULT_LOAD_FACTOR;
        threshold = DEFAULT_INITIAL_CAPACITY;
        table = new Entry1[DEFAULT_INITIAL_CAPACITY];
    }

    public HashTable1(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0) {
            throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
        }
        if (loadFactor <= 0 || loadFactor > 1) {
            throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
        }
        // Find a power of 2 >= initialCapacity
        int capacity = 1;
        while (capacity < initialCapacity) {
            capacity <<= 1;
        }
        this.loadFactor = loadFactor;
        threshold = (int)(capacity * loadFactor);
        table = new Entry1[capacity];
    }

    public HashTable1(int initialCapacity) {
        this(initialCapacity, 0.75f);
    }
}

Core Methods

Clearing the Table

The clear() method resets the table and size:

public void clear() {
    Entry1 tab[] = table;
    for (int i = 0; i < tab.length; i++) {
        tab[i] = null;
    }
    size = 0;
}

Checking for Keys and Values

• containsKey(Object key): Uses a hash function to locate the bucket and traverses the linked list to find the key.
• containsValue(Object value): Iterates through all buckets to find a matching value.

public boolean containsKey(Object key) {
    Object k = maskNull(key);
    int i = hCode(k, table.length); // Hash function
    Entry1 e = table[i];
    while (e != null) {
        if (eq(k, maskNull(e.getKey()))) {
            return true;
        }
        e = e.getNext();
    }
    return false;
}

public boolean containsValue(Object value) {
    if (value == null) {
        return containsNullValue();
    }
    Entry1 tab[] = table;
    for (int i = 0; i < tab.length; i++) {
        for (Entry1 e = tab[i]; e != null; e = e.getNext()) {
            if (value.equals(e.getValue())) {
                return true;
            }
        }
    }
    return false;
}