Java Hashtable Implementation: Methods and Usage

Posted on Jan 20, 2025 in Computer Engineering

Java Hashtable Implementation Details

toString Method

The toString method returns a string representation of the hashtable’s contents:

public String toString() {
    StringBuffer sb = new StringBuffer();
    Entry1 tab[] = table;
    for (int i = 0; i < tab.length; i++) {
        for (Entry1 e = tab[i]; e != null; e = e.getNext()) {
            sb.append(e + " ");
        }
    }
    return sb.toString();
}

Mayor Method

The Mayor method finds the largest key (assuming keys are integers) in the hashtable:

public Object Mayor() {
    Entry1 tab[] = table;
    int mayor = 0;
    for (int i = 0; i < tab.length; i++) {
        for (Entry1 e = tab[i]; e != null; e = e.getNext()) {
            if (e.getValue() != null) {
                Object n = e.getKey();
                if ((int) n > (int) mayor) {
                    mayor = (int) n;
                }
            }
        }
    }
    return mayor;
}

Handling Null Keys

The maskNull and unmaskNull methods handle null keys by using a special NULL_KEY object:

• maskNull(Object key): Replaces a null key with NULL_KEY.
• unmaskNull(Object key): Replaces NULL_KEY with null.

public static final Object NULL_KEY = new Object();

public static Object maskNull(Object key) {
    return (key == null ? NULL_KEY : key);
}

public static Object unmaskNull(Object key) {
    return (key == NULL_KEY ? null : key);
}

Checking for Null Values

The containsNullValue method checks if the hashtable contains any null values:

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

Hash Code Calculation

The hCode method calculates the hash code for a key:

private int hCode(Object k, int capacity) {
    return maskNull(k).hashCode() & (capacity - 1);
}

Equality Check

The eq method checks if two objects are equal:

private static boolean eq(Object x, Object y) {
    return x == y || x.equals(y);
}

Adding Entries

The addEntry method adds a new entry to the hashtable:

private void addEntry(Object key, Object value, int index) {
    Entry1 newEntry = new Entry1(key, value);
    newEntry.setNext(table[index]);
    table[index] = newEntry;
    if (size++ >= threshold) {
        resize(2 * table.length);
    }
}

Resizing the Hashtable

The resize method increases the capacity of the hashtable:

private void resize(int newCapacity) {
    Entry1[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (size < threshold || oldCapacity > newCapacity) {
        return;
    }
    Entry1[] newTable = new Entry1[newCapacity];
    transfer(newTable);
    table = newTable;
    threshold = (int) (newCapacity * loadFactor);
}

Transferring Entries

The transfer method moves entries from the old table to the new table during resizing:

private void transfer(Entry1[] newTable) {
    Entry1[] src = table;
    int newCapacity = newTable.length;
    for (int j = 0; j < src.length; j++) {
        Entry1 e = src[j];
        if (e != null) {
            src[j] = null;
            do {
                Entry1 next = e.getNext();
                int i = hCode(e.getKey(), newCapacity);
                e.setNext(newTable[i]);
                newTable[i] = e;
                e = next;
            } while (e != null);
        }
    }
}

Removing Entries

The removeEntryForKey method removes an entry with a specific key:

private Entry1 removeEntryForKey(Object key) {
    Object k = maskNull(key);
    int i = hCode(k, table.length);
    Entry1 previous = null;
    for (Entry1 e = table[i]; e != null; e = e.getNext()) {
        if (eq(k, maskNull(e.getKey()))) {
            if (e == table[i]) {
                table[i] = e.getNext();
            } else {
                previous.setNext(e.getNext());
            }
            size--;
            return e;
        }
        previous = e;
    }
    return null;
}