Re: hash tables

[Barry Margolin]

In article <uiqz8w7db.fsf@tiscali.co.uk>,
 David Roderick <angel_ov_north@tiscali.co.uk> 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, barmar@alum.mit.edu
Arlington, MA
*** PLEASE don't copy me on replies, I'll read them in the group ***