Hash functions

[Piotr Wyderski]

On Thu, 6 May 2004, Kevin Ryde wrote:

> A difficulty would be what algorithm to pick,


FNV is reported to work well when the size of a hash
table is a power of 2. In fact it doesn't matter which
algorithm is used, if it distributes uniformly the keys from
the most frequently used key domains. If a real, complex
enough program shows that the above property holds, it's
a sufficient empirical proof that the algorithm is OK.

> Would also need to think whether results should be
> the same on all systems (limb size independent)

No, it is not necessary. Just make a remark in the
documentation that the return value is not guaranteed
to be the same on all machines and the users will not
save these values into persistent storages.

> and whether to remain
> fixed across gmp versions.

Again, don't guarantee it. :-)

> I guess you might want to work the exponent into it too.

Yes, you're absolutely right. It's exactly the thing
I wrote about: as an "external" user of the library
I should not know it's internal structure, e.g. where
the exponent is kept or how it is represented internally.
To a library developer, however, it's easy to write such a function,
because he is allowed to know every detail of its internal
representation and to make use of this knowledge. So, would
you add a portable support for hashing to the GMP library? :-)

> Don't forget a limb can be a long long.

Yes, it's another evidence that hashing should be
supported by the library, not by the user.

	Best regards
	Piotr Wyderski