Imagine storing baseball cards in an array slot named by each card’s key. A direct-access table places an element with key k directly at array index k, rather than packing elements in insertion order. Empty positions contain None or another marker, so the table can distinguish unused cells from stored elements. section 12.10 section 12.22
The ideal operation sequence is simple:
- Extract or compute an element’s key, use that key as the array index, and read, insert, or delete the element in constant time once the index is known. section 12.10 section 12.11
- Treat indexing cost separately: converting a string identifier to an integer may take O(k) time, though bounded key lengths can make this effectively constant. section 12.11
- Use direct access only when the key range is constrained; otherwise, most array cells remain empty and memory usage becomes impractical. section 12.12
Joe Di Maggio’s card
Suppose an indexing function assigns Joe Di Maggio’s card the index 3. Store the card in the array’s fourth cell, at position 3, and retrieve it later from that same position. A string identifier may first be converted into an integer by processing its characters, such as with a base-256 calculation. section 12.10 section 12.11
Hash tables address the main limitation by mapping a large key range into a smaller array, accepting collisions that require techniques such as chaining or open addressing. Direct-access tables avoid those collisions but may require an array as large as the entire key space. section 12.22 section 12.13
