[petsc-users] PetscTableCreateHashSize

[Satish Balay]

On Mon, 9 Jan 2017, Jed Brown wrote:

> Satish Balay <balay at mcs.anl.gov> writes:
> 
> >> Why is it not sufficient to be coprime?
> >
> > Well whatever was implemented previsously with PETSC_HASH_FACT [a
> > prime number] didn't work well. [there were a couple of reports on it].
> 
> That was linear probing, right?

yes - but not sure if it implemented a good hash function. [had issues with collisions]

> 
> > Checking double hashing [Intro to algorithms, Coremen et all.]:
> >
> > For a hashtable size 'm' - and using hash functions h1(k), h2(k) - it
> > says: h2(k) must be relatively prime to 'm'. [for all possilbe 'k'
> > values? its not clear. Also any constraints on h1(k)?]
> 
> relatively prime = coprime
> 
> > And it suggested the following as one way to imlement:
> > choose a prime 'm'
> > h1(k) = k mod m
> > h2(k) = 1 +  (k mod m')

Forgot to mention: choose m' = (m-1) or (m-2)

> >
> > This was simple enough for me - so I updated ctable to use it. I've
> > added entries up to INT_MAX.
> 
> Thanks.
> 
> > If its still lacking (I could potentially add more entries - perhaps
> > for 64bitincides? or) - feel free to change the algorithm for arbirary
> > sizes...
> 
> I would use khash (hash.h) because it is a portable and well-optimized
> hash implementation.  The version in PETSc uses primes and double
> hashing, though upstream now uses quadratic probing (better cache
> locality).

I tried looking at it - but it was easier for me to fixup current ctable code.

Satish