Re: question on hash for objects such as tables and functions

[Francisco Olarte <folarte@...>]

On Tue, May 26, 2020 at 3:46 AM Philippe Verdy <verdyp@gmail.com> wrote:
> A table size for 16 elements: 2^4-1=15 is Mersenne, but is a multiple of 3 and 5, so collisions occur for objects whose differences of addresses is frequently a multiple of 3 or 5 (e.g. allocating many objects with size 10, or 12 or 20).
> A table size for 32 elements: 2^5-1=31 is Mersenne, but is prime (no problem here).
> A table size for 64 elements: 2^6-1=63 is Mersenne, but is a multiple of 3, so collisions occur for objects whose differences of addresses is frequently a multiple of 3 (e.g. allocating many objects with size 12)
> A table size for 128 elements: 2^7-1=127 is Mersenne, but is prime (no problem here).
> A table size for 512 elements: 2^9-1=511 is Mersenne, but is a multiple of 3.
> A table size with 256 elements: 2^8-1=255 is Mersennen but is a multiple of 5

4,6,9,8 are not primes and are even, their mersennes must all be divisible by 3.

4 is 2*2, so 2^4-1 must be multiple of 2^2-1 = 3, same for 8 ( the 5
factor is easy to spot in decimal, but 255 = 3*5*17.

In fact any 2^p-1 where p is even is trivially proven to be equal to
(2^(p/2)-1)*(2^(p/2)+1)  as (x-1)*(x+1)=x^2-1 ), as can be seen in
3*5=15, 7*9=63, 15*17=255

The interesting odd  9 must be a multiple of 7 ( 2^3-1), in fact, it
is NOT A MULTIPLE OF 3 (5+1+1=7!). It is in fact seven times seventy
three ( try factor 511 )

This message and the previous one makes me suspicious on the soundness
of all your hash table collisions/primes/sizes dissertation. Do you
have ay measurements/simulations of your various assertions?

Francisco Olarte.