Subject: Re: sxhash redux
From: (Rob Warnock)
Date: Sun, 05 Jun 2005 19:03:02 -0500
Newsgroups: comp.lang.lisp
Message-ID: <>
Marcin 'Qrczak' Kowalczyk  <> wrote:
| Bruno Haible <> 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			<>
627 26th Avenue			<URL:>
San Mateo, CA 94403		(650)572-2607