Marcin 'Qrczak' Kowalczyk  <qrczak@knm.org.pl> wrote:
+---------------
| Bruno Haible <bruno@clisp.org> writes:
| > The clisp developers agree. This has been fixed in the clisp CVS a week ago
| > for normal hash tables, and six months ago for package symbol-tables.
| 
| Do you think that letting a hash go up to 0x3FFFFFFF (1e9) on 64-bit
| platforms is enough, or it's better to have a bigger range in this
| case? In the implementation I have in mind object sizes are 64-bit on
| 64-bit platforms, but I'm not sure whether someone will want to make
| a hash table with 1e9 entries (of course it will work anyway but
| collisions will be often).
+---------------

A well-designed hash has (roughly) equal information in each bit,
therefore for smaller hash tables only a subset of bits need be used
for indexing into the table. The remaining bits can be useful as a
secondary hash in resolving collisions. And if one saves the *whole*
original SXHASH value with each object in the hash table, then it
is not necessary to rehash to grow the table -- just start using a
different subset of the hash bits.

Which is a long-winded way of saying that on a 64-bit machine it'd
be really nice if SXHASH values were at least 60 (say) bits...


-Rob

-----
Rob Warnock			<rpw3@rpw3.org>
627 26th Avenue			<URL:http://rpw3.org/>
San Mateo, CA 94403		(650)572-2607