3 ms·
He does say: "Perfect hash tables always win, hands down." A perfect hash table does have O(1) look-ups in the worst case.
by quacker 15y ago
He does say: "Perfect hash tables always win, hands down."
A perfect hash table does have O(1) look-ups in the worst case.
- tptacek 15y agoI 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.
- bricestacey 15y agoSince they did load testing to optimize performance, I think his argument stands. If they didn't bother to optimize I would agree with you.
- aaronblohowiak 15y agoA really perfect hash table is just an array ;)
- groby_b 15y agoYes. 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.
- geocar 15y agoOnly 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.