Marcin 'Qrczak' Kowalczyk <firstname.lastname@example.org> wrote:
| Bruno Haible <email@example.com> 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 Warnock <firstname.lastname@example.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607