I think this is very different from a splay tree, though. Open-address tables take advantage of the cache
Well, duh! That's why I said it's analogous. Of course something built on an array is likely going to have better cache behavior! My point is that you're using amortized work to shorten the average amount of work it takes to retrieve your data. My point was to talk about the generalized meta-strategy. Lose a point for poor reading comprehension because you so-badly-wanted-to-correct-someone.
Nope! Didn't go there.
I think this is very different from a splay tree, though. Open-address tables take advantage of the cache
Well, duh! That's why I said it's analogous. Of course something built on an array is likely going to have better cache behavior! My point is that you're using amortized work to shorten the average amount of work it takes to retrieve your data. My point was to talk about the generalized meta-strategy. Lose a point for poor reading comprehension because you so-badly-wanted-to-correct-someone.