i think the confusion here is whether we're talking about worst case or average times. cuckoo hashing addresses worst case times, while the traditional O(1) fo

i think the confusion here is whether we're talking about worst case or average times. cuckoo hashing addresses worst case times, while the traditional O(1) for access to a probed table is an average time (worst case is going to be O(n) i guess). that's not as bad as it sounds because provided the load factor is low enough the probability of the worst case goes down "fast enough" for the average to be bounded. i think :o)