On Fri, Apr 3, 2009 at 9:00 PM, Carl Eastlund <[email protected]>wrote:
> On Fri, Apr 3, 2009 at 8:43 PM, Lynn Winebarger <[email protected]> > wrote: > > On Fri, Apr 3, 2009 at 5:16 PM, leppie <[email protected]> wrote: > >> > >> ----- Original Message ----- > >> From: "Brian Harvey" <[email protected]> > >> > >> > Okay, I'm confused, A hash value is an index into an array. If the > >> > hash value doesn't fit in a fixnum, then the array doesn't fit in > >> > memory, > >> > or even in the virtual address space (by a factor of 4 on a 32-bit > >> > machine). > >> > What am I missing here? > >> > >> > >> Something other than the most extreme naive implementation of a > hashtable, > >> ever. :) > > > > I'm with Brian - I haven't been following the "hash table" literature, > but > > to the best of my knowledge its normal usage refers specifically to > > associations recorded in an array. Maybe the term has acquired a wider > > meaning - certainly R6RS does not retain this standard meaning - but I > think > > it's hard to claim the standard definition of X is "the most extreme > naive > > implementation of " X. > > The problem with "the standard definition" is that it doesn't account > for any kind of abstraction. It describes hash functions from the > perspective of a definition that "knows" about the array the hash > table is stored in. In a real library, that doesn't happen -- that > array may get resized by the hash table implementation; you as a user > do not know its capacity. So any API that exposes the ability to > write a "hash function" cannot ask you to produce an index into that > array. Instead, you must write the "first half" of the hash function: > a function from elements to integers, or fixnums, or something of that > sort. The hash table library can then apply modulo or whatever other > operation to go "the rest of the way" and narrow down the number to an > index into a specific array size. > > The problem is that the situation is actually reversed. The user may be writing the hash table implementation, but wants to use the Scheme implementation's hash functions to get hashes on arbitrary Scheme objects for efficiency. Obviously the tables the implementation provides can do whatever they want under the hood, but the hash functions provided by the implementation to the public should conform to the user's expectations. If the implementation's make-hashtable accepts hash functions that yield arbitrary fixnums, but it should work even if the hash function produces positive bignums. This question actually conforms to the "should" - it's ridiculous to require that the implementation detect whether the user-provided hash function always return a non-negative exact integer, so the text says "should". Lynn
_______________________________________________ r6rs-discuss mailing list [email protected] http://lists.r6rs.org/cgi-bin/mailman/listinfo/r6rs-discuss
