[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: Per Bothner <per@xxxxxxxxxxx>*Subject*: Re: should hash function upper bound be exclusive?*From*: bear <bear@xxxxxxxxx>*Date*: Tue, 9 Aug 2005 17:13:47 -0700 (PDT)*Cc*: srfi-69@xxxxxxxxxxxxxxxxx*Delivered-to*: srfi-69@xxxxxxxxxxxxxxxxx*In-reply-to*: <42F8E871.5070903@xxxxxxxxxxx>*References*: <42F8E871.5070903@xxxxxxxxxxx>

On Tue, 9 Aug 2005, Per Bothner wrote: > Current the 'bound' for hash functions is exclusive: the returned > hash h is such that (and (>= 0 h) (< h bound)). One might want the > default bound to be such that hashes range over the positive > fixnums. But in that case the bound would not be a fixnum: it would > have to be one larger than the largest fixnum. On the other hand, the largest fixnum is likely to be either a power of two, or one less than a power of two; as hashes are conventionally implemented (via modulus operations) these are poor choices for a hash range boundary. Numerical theory indicates that a much better choice is the highest prime fixnum representable, or at least a fixnum with no small factors. Otherwise you run into rehash problems where the system may be able to find no valid rehash value even though the table is not full. > A hash-table implementation might want to cache hash values, and > might also want to be able to resize the table. Definitely; when you have the capability of resizing the table, you must be able to rehash everything in the table. Usually you can make that much faster by caching the hashes. Caching the hashes also makes it much faster (in the average case) to check and make sure that you are looking at an actual *match* rather than something else that hashed into the same bucket. bear

**Follow-Ups**:**Re: should hash function upper bound be exclusive?***From:*Per Bothner

**References**:**should hash function upper bound be exclusive?***From:*Per Bothner

- Prev by Date:
**should hash function upper bound be exclusive?** - Next by Date:
**Re: should hash function upper bound be exclusive?** - Previous by thread:
**should hash function upper bound be exclusive?** - Next by thread:
**Re: should hash function upper bound be exclusive?** - Index(es):