The underlying implementation is opaque, and you should always expect it to be.

Not really. "Hash", short for "hash table", is a specific algorithm. "Associative array" is the implementation-independent term.

Loss of speed in memory-access can only come from one source: page faults.

I think you mean cache misses. p5p is indeed aware that cache misses can mess up theoretical performance analysis, but it's hardly the only source of loss of speed. I'm not well versed in this area, but I suspect that it's quite the opposite, that it takes second seat to other macro factors (like quantum physics to newtonian physics).

http://queue.acm.org/detail.cfm?id=1814327 is a story where changing the algorithm to reduce cache misses made a big difference. If what you said was true, a linear search would be as fast as the algorithm to which he changed since they're both cache-oblivious.