>
by a flat array for small n (hundreds, low thousands)Some of us are working in, say, Python. A flat array can outperform at small n, yes, but people overestimate where the tradeoff point is. It's at <5 items:
# A list of [0, 1, 2, 3, 4]
In [10]: linear = list(range(5))
# A hash set, same thing.
In [11]: hashing = set(range(5))
# 44ns / linear search
In [12]: %timeit 3 in linear
44.2 ns ± 0.412 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
# 25ns / hash search!
In [13]: %timeit 3 in hashing
25 ns ± 0.6 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
The hash set outperforms the linear search by nearly 2x, on a list of size 5! (The performance is similar for other common types that end up in hashes, like strings.)
"It's Python!", you say. "Too much chasing of pointers to PyObjects destroy the cache!" And yes, they do; but many people are working in high-level languages like Python or Ruby.
But, for those that aren't, if we repeat the above exercise in Rust, yes the tradeoff will move up, but only to ~60 items, not hundreds or low thousands:
test tests::bench_hash_int ... bench: 14 ns/iter (+/- 1)
test tests::bench_linear_int ... bench: 19 ns/iter (+/- 3)
If you're thinking that somehow accessing the middle item each time bestows an unfair advantage to the hash table, randomizing the desired item doesn't help, either:
test tests::bench_rng_hash_int ... bench: 19 ns/iter (+/- 2)
test tests::bench_rng_linear_int ... bench: 24 ns/iter (+/- 2)
And looking for an item
not in the list is definitely not favorable to the linear search. (It's the worst case.)
In my experience, it's almost always easiest to pay mild attention to big O concerns, and just use the appropriate data structure for the problem at hand. Cache effects mattering is either rare (you're writing a RESTful microserving to push cat pictures, a cache isn't going to matter once we hit this mobile devices 20 second network latency!) or highly context dependent (your line of work is always low-level, and these crop up more often, and you're consequently on the lookout for it; I don't think this applies to most of us, however).
The code used, in case you wish to find fault with it: https://github.com/thanatos/hash-vs-linear