Re: sxhash redux

Bruno Haible <bruno@xxxxxxxxx> writes:

>> If CLISP limits its 64-bit version of SXHASH to the range of its 32-bit
>> non-negative fixnums then it is worthless using the hash code as a index
>> to any vector greater than 16777215 in size.
>>
>> This is a serious limitation upon the performance of any hash table with
>> many millions of elements and a practically unacceptable limitation upon
>> 64-bit platforms.
>
> 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).

--
__("< Marcin Kowalczyk
\__/ qrczak@xxxxxxxxxx
^^ http://qrnik.knm.org.pl/~qrczak/
.

Relevant Pages

  • Re: Maximum String size in Java?
    ... > portions he was replying to CBF, two birds, one stone. ... platforms where int is not 32 bits are pretty marginal. ... I'll help you out -- its not an incremental hash. ... I've seen stupid things like hungarian programming ...
    (comp.programming)
  • Re: Suggestions for double-hashing scheme
    ... >> a hash table with a prime number of slots. ... > you don't care about such portability, then by all means use the pointer ... platforms that most people will encounter. ... > I agree with you that using prime table sizes has it's advantages. ...
    (comp.programming)
  • Re: MAC problems
    ... yes i was referring to bytes per second, take for example a 200 byte string, ... isn't a well implemented hash supposed to be independant of the ... relatively the same across hardware platforms with an exception or two if ... In terms of cycles per ...
    (sci.crypt)
  • Re: MAC problems
    ... probably a wrong understanding as usual, that a hash becomes a HMAC by the ... IMO it would be more accurate to say that HMAC is a construction ... relatively the same across hardware platforms with an exception or two if i ...
    (sci.crypt)
  • Re: sxhash redux
    ... |> The clisp developers agree. ... |> for normal hash tables, and six months ago for package symbol-tables. ... In the implementation I have in mind object sizes are 64-bit on ... secondary hash in resolving collisions. ...
    (comp.lang.lisp)