[s243a]

I haven't studied hash-tables but I've been thinking a bit about the mathematics. In the java class HashMap, the hashkey is trimmed down by removing the highest order bits:

See line 578 (function putImpl)

int index = hash & (elementData.length - 1);

http://www.docjar.co...shMap.java.html

I realized this is equivalent two the following operation hash mod elementData.length.
also written
hash%2^n
where n is the log base 2 of the field ellementData.length (Java HashMap only uses array sizes which are a power of two)

So if you have a number which is relatively prime to 2^n, Then:

p=p^m%2^n when m is equal to 2^m

Now consider two primes p1 and p2.

When is p1^m1 mod 2^n = p2^m2 mod 2^n?

This would be a collision condition.

[Nikitin]

s243a, on 05 September 2010 - 11:38 AM, said:

p=p^m%2^n when m is equal to 2^m2^n

Fixed.

This would be true, only if 2^n were prime.

Quick check: let p = 3, n = 2.

This post has been edited by Nikitin: 05 September 2010 - 01:05 PM