4.2.6.1, 4.2.7.1 - Hash tables and dictionaries (Java)

Key-value structures

A key identifies which associated value should be retrieved without making the user know its storage position.

A student identifier can retrieve a score, and a word can retrieve its occurrence count. Keys are unique within a dictionary; values need not be unique. Updating the value for an existing key does not add a second independent pair with that same key. A hash table is one way to implement this mapping; dictionary describes access behaviour, while hashing describes how a storage location is chosen.

Java uses the Map<K,V> interface for dictionary operations. For example Map<String,Integer> associates strings with integer counts. Integer is the reference wrapper type required by Java generics; an int value is boxed when stored and unboxed when used numerically. A map is not an array whose string key is a numeric subscript.

Simple hashing

A hash function computes a candidate storage location from a key.

For a table with seven slots, numbered 0 through 6, use $h(k)=k\bmod7$ for nonnegative integer keys. Keys 10, 23 and 17 map to slots 3, 2 and 3 respectively. A good distribution reduces clashes but cannot generally guarantee a unique slot for every possible key in a smaller finite table.

static int hash(int key, int capacity) {
    return Math.floorMod(key, capacity);
}

Here capacity is positive. Math.floorMod keeps the index nonnegative even for a negative key; Java's % can return a negative remainder. The modulo method is a simple teaching hash, not a universal replacement for a library's hashing and capacity rules. Hashing a string could combine character codes, but the exact rule must be supplied before a trace.

Use hash tables for frequent key lookups such as identifier-to-record tables. A lookup still compares the stored key with the requested key: matching hash locations alone does not establish equal keys.

Collisions and rehashing

A collision occurs when different keys compute the same hash location.

Use the explicit rehashing rule $h_i(k)=(h(k)+i)\bmod7$, for attempts $i=0,1,\ldots,6$. This is linear probing: try the next slot, wrapping at the end. Inserting 10, 23, 17, 24 into an empty seven-slot table gives:

Maintain both key and value in each occupied slot. To retrieve 17, repeat its probe sequence, rejecting key 10 at slot 3 before matching 17 at slot 4. Stop at a never-used empty slot or after at most the capacity probes. Insertion must update an existing matching key or use an empty slot; a full table must report failure instead of looping forever.

For an insertion-only integer-key table, an Integer[] with null meaning empty supports this bounded location search:

static int locate(Integer[] keys, int key) {
    int start = Math.floorMod(key, keys.length);
    for (int offset = 0; offset < keys.length; offset++) {
        int slot = (start + offset) % keys.length;
        if (keys[slot] == null || keys[slot].intValue() == key) {
            return slot;
        }
    }
    return -1;
}