Originally Posted by sundialsvcs

Let's say that, within this "key space" of 1 billion possible keys, on any particular run you actually top-out at, say, five million. Let's say, furthermore, that the key distribution is "all over the place." Very random, very unpredictable.

Your "very large array" would flop over and die, horribly. The odds are nearly 100% that a page-fault would occur on every reference, because I said that "the key distribution is random." The virtual memory subsystem would quickly succumb to thrashing.

But what would a hash table do? Each of the key-values is translated (by some means) into a "bucket number," and only that "bucket" of the hash-table is searched (by some means) for the desired value. Although the key-distribution is random, the size of the hash-table is both reasonable and fixed. Storage is only being consumed for the actual values used, plus some amount of overhead, but the storage-management strategy is designed to minimize the number of page-faults.

Certainly, the CPU is being obliged to execute more instructions. But it does that at a rate of several hundred million instructions per second... so "who cares?" What we are avoiding is a page-fault, which takes many milliseconds per fault. You do the math.