I think you are right that the asymptotic claims are wrong, but it also seems plausible that hashing a k-byte string (in some way that gives you k prefix hashes

I think you are right that the asymptotic claims are wrong, but it also seems plausible that hashing a k-byte string (in some way that gives you k prefix hashes) may sometimes be drastically cheaper than k cache misses in a large data structure. My charitable guess is that the author is implicitly using a cost model where only access to unbounded memory has a cost.