Hacker News Reader

If the size of the data is small, a linear search through a contiguous array is going to be far faster than anything more complex.

View on HN

Yep; though we'd have to test a few cases to figure out what the cutoffs are here, and if there's any middle ground left for a divide-and-conquer strategy.

It's also definitely going to depend on the cost of the hash function and comparison function - for something like strings, where those can be quite expensive, binary search probably has a better chance of applicability than for guid's say.

For things with non-trivial comparison functions you're all but certainly better off with those in something else like a hashmap. After all, the more expensive the compare, the more expensive the sort & reordering that a binary search requires. And then for trivial comparison objects, binary searching is still slower even at "huge" sizes like 10,000. It's really hard to find a good use of binary searching an array on modern CPUs.

Well, it depends on how expensive your comparison is compared to a cache miss.

Reply on news.ycombinator.com