Timeline for (When) is hash table lookup O(1)?
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S May 5, 2013 at 22:31 | history | suggested | Alejandro Sazo | CC BY-SA 3.0 |
fixed notation with LaTeX
|
| May 5, 2013 at 21:30 | review | Suggested edits | |||
| S May 5, 2013 at 22:31 | |||||
| Apr 21, 2012 at 22:00 | comment | added | Louis | To make a more useful comment on this answer, as @Suresh points out, cuckoo hashing will work well without the fancy (and big) hash functions used to analyze it theoretically. | |
| Apr 21, 2012 at 21:41 | comment | added | Suresh | I meant "in practice" :) | |
| Apr 21, 2012 at 21:39 | comment | added | Louis | @Suresh: Really? I thought you needed $\log n$-independent functions, which I always associated with needing expanders. I stand corrected. Will delete my comment in a bit. | |
| Apr 21, 2012 at 21:21 | comment | added | Suresh | @Louis: That's not true. you can use relatively simple hash functions in practice. I had my students implement cuckoo hashing for an assignment using regular mod-prime hash functions. | |
| Mar 13, 2012 at 8:38 | comment | added | uli | FKS are the initials of (Fredman, Komlós, Szemerédi) and Cuckoo is the name of a brid species. It is use for this type of hashing, because cuckoo chicks push sibilings eggs out of the nest. This resembles somewhat how this hasing method functions. | |
| Mar 13, 2012 at 0:48 | comment | added | Suresh | Ah yes, dynamic perfect hashing works as well. But it's randomized. For both FKS and cuckoo hashing, these notes are good: courses.csail.mit.edu/6.851/spring07/scribe/lec11.pdf | |
| Mar 13, 2012 at 0:23 | comment | added | Joe | What about dynamic perfect hashing? It has $O(1)$ worst-case lookups and $O(1)$ amortized insertion and deletion. (citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.30.8165) | |
| Mar 12, 2012 at 21:30 | comment | added | Gilles 'SO- stop being evil' | Could you expand on FKS and Cuckoo? Both terms are new to me. | |
| Mar 12, 2012 at 20:26 | history | answered | Suresh | CC BY-SA 3.0 |