Direct Address Table

Concept (short)

A Direct Address Table (DAT) is the simplest hashing technique: keys are integers taken from a small universe (U = {0,1,\dots,m-1}). Instead of computing a complicated hash, the key itself directly indexes an array.
So table[key] holds the value associated with key (or a sentinel if empty).

When to use

• Good when universe size m is small and memory O(m) is affordable.
• Examples: flags for ASCII codes (0–127), small ID ranges, bitmap/bitset usage, presence arrays, frequency counters for small ranges.

Properties & Complexity

• Insert / Delete / Search — O(1) time (direct array access).
• Space — O(m) (must allocate array of size = universe).
• No collisions — because each key maps to a unique slot (identity mapping).
• Limitations — impractical if universe is very large or sparse (wastes memory). For large sparse domains, use hashing (chaining/open addressing) or dictionaries.

Behavior details

• DAT stores either None or a sentinel for empty slot, or the stored value.
• Keys must be integers in valid range; attempting to use out-of-range key should raise error or be handled.
• It can be made memory-efficient by storing booleans or bits (bitset) when only membership is needed.

---

Python implementation (clean, ready-to-run)

from typing import Generic, TypeVar, Optional, List

T = TypeVar("T")

class DirectAddressTable(Generic[T]):
    """
    Direct Address Table for keys in range [0, m-1].
    Stores values of type T (or None if empty).
    Operations: insert(key, value), delete(key), search(key), contains(key).
    """
    def __init__(self, universe_size: int):
        if universe_size <= 0:
            raise ValueError("universe_size must be a positive integer")
        self.m = universe_size
        self.table: List[Optional[T]] = [None] * self.m

    def _check_key(self, key: int):
        if not isinstance(key, int):
            raise TypeError("key must be integer")
        if key < 0 or key >= self.m:
            raise IndexError(f"key {key} out of universe range [0, {self.m - 1}]")

    def insert(self, key: int, value: T) -> None:
        """Insert value at position 'key'. Overwrites any existing value."""
        self._check_key(key)
        self.table[key] = value

    def delete(self, key: int) -> None:
        """Delete value at 'key' (set to None). If already empty, no-op."""
        self._check_key(key)
        self.table[key] = None

    def search(self, key: int) -> Optional[T]:
        """Return value at 'key' or None if empty."""
        self._check_key(key)
        return self.table[key]

    def contains(self, key: int) -> bool:
        """Return True if there is a value stored at 'key'."""
        self._check_key(key)
        return self.table[key] is not None

    def keys(self):
        """Yield all keys that currently store a value."""
        for i, v in enumerate(self.table):
            if v is not None:
                yield i

    def items(self):
        """Yield (key, value) pairs for non-empty slots."""
        for i, v in enumerate(self.table):
            if v is not None:
                yield (i, v)

    def __repr__(self):
        used = sum(1 for x in self.table if x is not None)
        return f"<DirectAddressTable m={self.m} used={used}>"

# Example usage
if __name__ == "__main__":
    dat = DirectAddressTable   # universe 0..19
    dat.insert(5, "alice")
    dat.insert(0, "root")
    dat.insert(12, "bob")
    print("Search key 5:", dat.search(5))       # alice
    print("Contains 3?", dat.contains(3))       # False
    print("All items:", list(dat.items()))      # [(0,'root'), (5,'alice'), (12,'bob')]
    dat.delete(5)
    print("After delete key 5, contains 5?", dat.contains(5))  # False

---

Variants & Practical tips

• Bitset: if only membership matters (no values), use a boolean list or Python bitarray / int bitmask to save memory.
• Sparse alternative: if universe large and few keys used, use Python dict (hash table) to avoid O(m) space.
• External memory: for on-disk direct addressing (large m), consider compression or block-mapping schemes.

---