a direct-mapped cache

Imagine a coat-check where your ticket number is your locker number, computed by a fixed rule: the last two digits of your number ARE your locker. Finding your coat is trivially fast — you go straight to that one locker, no searching. But there is a catch: everyone whose number ends in the same two digits must share that single locker, so two such people cannot both leave a coat at once. A direct-mapped cache is exactly this: each memory block has exactly ONE place it is allowed to live in the cache.

The rule is arithmetic on the address. An address is split into offset (which byte within the line), index (which cache slot to use, computed as the block number modulo the number of slots), and tag (the rest, to confirm identity). To look up an address you go directly to the slot named by its index — no choices, no parallel search — and compare the one stored tag there with the address's tag. Match plus valid means hit; mismatch means miss, and the incoming block simply overwrites whatever was in that one slot. This makes direct-mapped caches the simplest, fastest, and cheapest to build: a single tag comparison, no replacement decision at all.

The price is conflict misses. Because each block has only one home, two (or more) hot blocks that happen to map to the same slot keep evicting each other, thrashing, even while the rest of the cache sits empty. A loop alternating between two arrays whose addresses collide can have a near-zero hit rate in a direct-mapped cache that a set-associative cache would handle easily. So direct-mapped trades a higher conflict-miss rate for a lower hit time and simpler hardware — sometimes a good deal (especially for large lower-level caches), sometimes not. It is best understood as one-way set-associative: the simplest point on the associativity spectrum.