On Mon, 9 Jan 2017, Jed Brown wrote: > 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?
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
