3 ms·
If they say average case O(1), worst case O(n), hit them with them with O(log n / loglog n) with high probability from a simple balls-into-bins type argument.
by adrianN 11y ago
If they say average case O(1), worst case O(n), hit them with them with O(log n / loglog n) with high probability from a simple balls-into-bins type argument.
- nialo 11y agoCould you expand on the balls-into-bins argument here? It's not quite obvious to me, but I'd really like to understand.
- adrianN 11y agoItems are balls, slots in your table are bins. Hash functions are assumed to distribute them randomly (uniformly). See also the Wikipedia article on Balls-into-Bins. https://en.wikipedia.org/wiki/Balls_into_bins https://en.wikipedia.org/wiki/Balls_into_bins This reference from the wiki is good http://www14.in.tum.de/personen/raab/publ/balls.pdf http://www14.in.tum.de/personen/raab/publ/balls.pdf