[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: hash tables
Re: hash tables
Thu, 27 Mar 2008 21:15:24 -0400
MT-NewsWatcher/3.5.3b2 (Intel Mac OS X)
In article <address@hidden>,
David Roderick <address@hidden> wrote:
> 7.3 Defining Hash Comparisons
> You can define new methods of key lookup by means of
> `define-hash-table-test'. In order to use this feature, you need to
> understand how hash tables work, and what a "hash code" means.
> You can think of a hash table conceptually as a large array of many
> slots, each capable of holding one association. To look up a key,
> `gethash' first computes an integer, the hash code, from the key. It
> reduces this integer modulo the length of the array, to produce an
> index in the array. Then it looks in that slot, and if necessary in
> other nearby slots, to see if it has found the key being sought.
> Thus, to define a new method of key lookup, you need to specify both
> a function to compute the hash code from a key, and a function to
> compare two keys directly.
> " It
> reduces this integer modulo the length of the array,"
> So does this mean that the integer must be times greater than the length
> of the array, otherwise the integer is returned?
Yes. Hash codes should generally be very large integers.
> What happens if the hash table increases in size and this happens?
When a hash table changes size, all the elements have to be rehashed and
moved to the new locations.
Barry Margolin, address@hidden
*** PLEASE don't copy me on replies, I'll read them in the group ***
- hash tables, David Roderick, 2008/03/27
- Re: hash tables,
Barry Margolin <=