On Jun 26, 1996 23:22:02 in article <Re: Allegro Hash Table Problem>,
····@math.ufl.edu (Kelly Murray)' wrote:
>In article <··········@news2.h1.usa.pipeline.com>,
······@usa.pipeline.com(Pete
>Grant) writes:
>>> The problem appears to be Franz's implementation of sxhash, as
>>> well as of the hash table itself. The values returned by sxhash are
>>> limited to the range 0 to 64K; ie., the size of a a 16-bit unsigned
>>>
>>> Before I embark on a project of implementing my own hash table,
>>> does anyone know of a PD code that already provides for larger
>>> tables than those supplied by Franz?
>
>I think this limitation may be fixed or have a patch,
>(I could ask duane in the office next door but he's on the phone..)
>
>But if you can use your own, why not?
>
>A very simple thing to do is use multiple hashtables
>if you can use some fast simple way to partition the keys
>into a smaller set that will reduce the size for
>the real hashtable to do the lookup.
>It doesn't takes up that much extra space since hashtable are
>dynamically sized. It will be somewhat slower, highly dependant
>on how expensive your primary-hash function is.
>
>-Kelly Murray ···@franz.com
>
>(defconstant bighash-buckets 16) ;; increase hash capacity by 16 times.
>
>;; Must distribute well to be truly increase capacity by N times.
>;; Must be consistent for the same key.
>(defun primary-hash (key)
>(logand key #xF)) ;; trivial example for integer keys..
>
>(defun make-bighash ()
>(let ((table (make-array bighash-buckets)))
>(dotimes (x bighash-buckets)
>(setf (aref table x) (make-hash-table))))
>
>(defmacro getbighash (key table)
>`(gethash ,key (aref ,table (primary-hash ,key)))
>
Hmm, this sounds like a good idea. But, since the problem
may be fixed, I'll wait until my sysadmin installs 4.3
before doing anything major. According to the docs, the
situation is the same; i.e., hash functions can return
values only in the range 0-64K, but it's worth a few days'
wait to verify.
Thanks.
--
Pete Grant
Kalevi, Inc.
Software Engineering & development