.c	Thursday  Dec 1,1983  22:59  LQ+4D.17H.6M.38S.  -*- Bolio -*-

.chapter "Hashing"
.setq hash-table-section-page section-page

lan{nil} supports a lan{common lisp} compatible hash-table
facility.  This will eventually include the ability to have a
hash-table from which associations can be garbage-collected.

.section "Hash Tables"

The following routines are lan{common lisp} compatible:

.defun make-hash-table &key :test :rehash-threshold :rehash-size :size
Creates a hash table.  The 2test* may be one of 3#'eq*,
3#'eql*, or 3#'equal*.  lan{Nil} additionally provides some
others it is able to perform significant optimizations on as primitive
(see below).  Note that for lan{nil} to use some predicate it must
know how to compute a hash code compatible with that predicate's
notion of equality;  thus, not just any predicate is acceptable.
.end_defun

.defun gethash key hash-table &optional default
This returns two values.
If there is an entry for 2key* in 2hash-table*, then this
returns as its values the value associated with 2key*, and
3t*.  Otherwise, it returns 2default*, and 3nil*.

3gethash* may be used with 3setf* to add an entry to (or
replace an entry in) a hash table.
.end_defun

.defun remhash key hash-table
Removes the entry associated with 2key* from 2hash-table*.
.end_defun

.defun clrhash hash-table
Removes all entries from 2hash-table*.
.end_defun

.defun hash-table-count hash-table
Returns the number of entries in 2hash-table*.
.end_defun

.subsection "Additional Hash-Table Predicates"

lan{Nil} additionally offers the following predicates for
hash-tables:
.table 3 250 250
.item string-equal
.item string=
.end_table

associating hashing routines with predicates, making this list extensible?


.section "Hash Functions"

A hash function for equality predicate 3(2p* 2x1*
2x2*)* is a function which returns the same value for all
2x* which are equivalent according to 2p*.  The standard
lan{lisp} hashing function is 3sxhash*, which is defined
according to the 3equal* predicate.  3sxhash* is inherited
from lan{maclisp}, and is defined by lan{common lisp} and
lan{lispm}.

Other hash functions are defined by lan{nil}, for use with other
equality predicates.  Usually they are not needed, because they are
implied in the use of a hash table utilizing a particular equality
predicate.  By convention, all lan{nil} hashing functions return a
non-negative fixnum:  it is a fixnum for ease of computation, and
non-negative to make modulus operations more trivial.

.defun sxhash object
This is the general lan{lisp} hashing function, based on the
predicate 3equal* ((equal-fun)).  It returns a non-negative
integer;  in lan{nil}, this will always be a fixnum.  Two objects
which are 3equal* should always 3sxhash* to the same thing.
If this is not true, then any hash tables which use 3sxhash* and
3equal* will break.  Note that because lan{nil} will have a
relocating garbage collector, the hash of an object should never
be a function of the address of anything.
.end_defun

.defun string-equal-hash string
This function returns a non-negative fixnum such that for all strings
which are 3string-equal*, their hashes computed by this function
will be equal.
.end_defun

.defun string=-hash string
Similar;  defined by the predicate 3string=* ((string=-fun)).
.end_defun

.defmac sys:sxhash-combine {hash}+
This macro might be useful to writers of 3:sxhash* methods or
special hashing functions.  It is
a canonical way to combine a fixed number of hash codes.  For example,
the 3sxhash* of a cons does
.lisp
(sys:sxhash-combine (sxhash (car x)) (sxhash (cdr x)))
.end_lisp
The 2hash*es are rotated some fixed amount determined by the
number of arguments, and crunched together in some canonical fashion.
(There may be a limitation on the number of arguments which are
handled, but this will work for some moderate number of arguments.)
.end_defmac


.section "Symbol Tables"

Although one can use packages to implement symbol tables, and this has
been recommended in the past, it is now better to use a hash table
based on the appropriate predicate, and storing an appropriate object
as the value.  For example, if one had been using a package as a
symbol table and then using the symbol after interning it, a hash
table could be used using 3string-equal* or 3string=* as the
predicate (as appropriate) and putting a symbol in as the value.
Depending on what the symbol is used for, it may be better to use a
3defstruct*-created object instead;  attributes can be accessed
faster off of this than as properties on the plist of a symbol.
Secondarily, there is a moderate space inefficiency to generating
lots of value cells in lan{nil}, so instead of generating symbols
and using their value cells to store things is also better to use a
specialized structure.

When the lan{nil} package system is redone, the internal portion of
that which does simple symbol-table hacking will be made available for
applications where that is truly needed.

