News for hackers. Stuff that matters.
Re:Coding tricks I learnt at Apple by quacker on Friday June 10, 2011 @12:52PM (#2641524)
He does say: "Perfect hash tables always win, hands down."

A perfect hash table does have O(1) look-ups in the worst case.

Re:Coding tricks I learnt at Apple by tptacek on Friday June 10, 2011 @01:29PM (#2641668)
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.
Re:Coding tricks I learnt at Apple by groby_b on Friday June 10, 2011 @02:02PM (#2641803)
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.

Re:Coding tricks I learnt at Apple by geocar on Saturday June 11, 2011 @02:31PM (#2644484)
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.