3 ms·
> But we’ve shown that these types of subgraphs don’t appear with high probability! Hence the greedy routine works for hash tables with an occupancy of less tha
by yread 15y ago
> But we’ve shown that these types of subgraphs don’t appear with high probability! Hence the greedy routine works for hash tables with an occupancy of less than 0.5.
I haven't completely understood the probability estimation, but doesn't the insertion algorithm have an infinite worst case running time (albeit not with "high probability")?
- jaekwon 15y agoi guess, without loop detection.
- ErikCorry 15y agoYes, from the original paper: "As it may happen that this process loops, the number of iterations is bounded by a value, MaxLoop, to be speci ed below. If this number of iterations is reached, everything is rehashed with new hash functions, and we try once again to accommodate the nestless key"