hash tables

hash tables

[David Roderick]

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?

What happens if the hash table increases in size and this happens?
-- 
from 
David Roderick

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 ***