I saw that. From the context of the article, do you think he was really talking about a system using perfect hash tables? Be that as it may, "use a perfect hash table" is rarely a good answer to the job interview question, which is the only reason I commented on this.
Re:Coding tricks I learnt at Apple
by aaronblohowiak on Friday June 10, 2011 @02:34PM
(#2641944)
A really perfect hash table is just an array ;)
Re:Coding tricks I learnt at Apple
by bricestacey on Saturday June 11, 2011 @11:22AM
(#2644082)
Since they did load testing to optimize performance, I think his argument stands. If they didn't bother to optimize I would agree with you.
Yes. So?
There are lots of other constraints that come to mind. Do we do frequent insertions/deletions?
What are the memory constraints?
What is the size of the unhashed key?
And many more... No data structure always wins.
Only if you neglect hashing time (significant with perfect hashes) and comparison-time. That makes them O(k), not O(1). It is helpful to me to think of hashing as expensive as copying.
Radix tries on the other hand don't hash. They're always at least O(k), and you can find the next and previous values (lexicographically) in O(k) as well. They're also more compact and you never have to resize your tables.
A perfect hash table does have O(1) look-ups in the worst case.