Cuckoo hashing has O(1) worst-case *access* time, and O(1) "average" (amortized,... | Hacker News

Hacker Newsnew | past | comments | ask | show | jobs | submit

		ot on Feb 20, 2011 \| parent \| context \| favorite \| on: Hash tables with O(1) worst-case lookup and space ... Cuckoo hashing has O(1) worst-case access time, and O(1) "average" (amortized, to be correct) insert time.

16s on Feb 20, 2011 [–]

OK. That makes sense. If O(1) is worst case, what could be better :)

rudiger on Feb 20, 2011 | [–]

Well, smaller constant factors could be better :)

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact