4.2.6.1, 4.2.7.1 - Hash tables and dictionaries (C#)

Key-value structures

Key-based access lets a program find an associated value without treating the key as an ordinary array position.

A library can map an accession number to a book record. A word index can map a word to its frequency. Keys identify entries; they must be unique within a dictionary, but different keys may have equal values. An array index 2 means a position; the dictionary key 203 may represent a learner ID and need not imply 204 array slots.

The ADT and implementation are different: a dictionary could be implemented using a searched collection of pairs or a tree, while a hash table uses a hash function and collision policy. C#'s Dictionary<TKey,TValue> supplies key-based operations; an application must not assume its internal slots match a classroom modulo example.

Dictionary<string, int> stock = new Dictionary<string, int>();
stock["Pencil"] = 12;
stock["Notebook"] = 12;
stock["Pencil"] = 9;

With System.Collections.Generic imported, the final dictionary has two keys: Pencil maps to 9 and Notebook to 12. Assignment through an existing key replaces its value; it does not create a second Pencil entry.

Simple hashing

A hash function converts a key into a position in a bounded table.

For a seven-slot table and nonnegative integer keys, use $h(k)=k\bmod7$. Thus key 10 maps to slot 3, key 12 to slot 5 and key 17 to slot 3. A string key could instead sum stated character codes before applying modulo; the task must supply the actual rule. The hash is not necessarily unique and is not an encryption of the key.

static int Hash(int key, int capacity)
{
    return key % capacity;
}

The method assumes key ≥ 0 and capacity > 0. % is C#'s remainder operator; negative inputs need an explicitly chosen normalisation rule if supported. The stored record must include its key as well as its value, because one slot calculation can correspond to many keys. Comparing only the computed position would mistake key 17 for key 10.

Create a simple table with arrays for keys, values and bool[] occupied, initially false. The occupied flag permits a legitimate key 0 or value 0: neither is an empty-slot marker by itself.

Collisions and rehashing

A collision occurs when distinct keys compute the same hash, so insertion needs another candidate position.

Use linear probing as the stated rehashing rule: try $(h(k)+1)\bmod m$, then $(h(k)+2)\bmod m$, continuing until an empty slot or the matching key is found. Here rehashing means generating another candidate on collision; it is distinct from rebuilding a larger table.