Satish Balay <[email protected]> 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? > 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') > > 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).
signature.asc
Description: PGP signature
