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. -- Carl Eastlund _______________________________________________ r6rs-discuss mailing list [email protected] http://lists.r6rs.org/cgi-bin/mailman/listinfo/r6rs-discuss
