On 2/1/2012 3:59 AM, Daniel James wrote:
On 1 February 2012 00:44, Topher Cooper<topher@topherc.net> wrote:
values that differ by the table size end up in the same bin
Is that likely though? And any more likely than other causes of collisions?
It is immensely more likely than any of the causes of /systematic/ collisions in a reasonable implementations that avoids destroying expected performance (O(1)) and replacing it with worst case performance (O(N)) for simple regularities in the input data. The expected performance takes into account the occurrence of non-systematic collisions. No algorithm can guarantee that there cannot be systematic collisions (since it must be deterministic) but it is easy to make sure that regularities in the input data would have to be incredibly arbitrary to cause them. Topher Cooper