--- a/man/lispref/hash-tables.texi	Mon Aug 13 11:06:08 2007 +0200
+++ b/man/lispref/hash-tables.texi	Mon Aug 13 11:07:10 2007 +0200
@@ -7,8 +7,8 @@
 @chapter Hash Tables
 @cindex hash table
 
-@defun hashtablep object
-This function returns non-@code{nil} if @var{object} is a hash table.
+@defun hash-table-p object
+This function returns @code{t} if @var{object} is a hash table, else @code{nil}.
 @end defun
 
 @menu
@@ -23,77 +23,162 @@
 @node Introduction to Hash Tables
 @section Introduction to Hash Tables
 
-A hash table is a data structure that provides mappings from
-arbitrary Lisp objects (called @dfn{keys}) to other arbitrary Lisp
-objects (called @dfn{values}).  There are many ways other than
-hash tables of implementing the same sort of mapping, e.g.
-association lists (@pxref{Association Lists}) and property lists
-(@pxref{Property Lists}), but hash tables provide much faster lookup.
+A @dfn{hash table} is a data structure that provides mappings from
+arbitrary Lisp objects called @dfn{keys} to other arbitrary Lisp objects
+called @dfn{values}.  A key/value pair is sometimes called an
+@dfn{entry} in the hash table.  There are many ways other than hash
+tables of implementing the same sort of mapping, e.g.  association lists
+(@pxref{Association Lists}) and property lists (@pxref{Property Lists}),
+but hash tables provide much faster lookup when there are many entries
+in the mapping.  Hash tables are an implementation of the abstract data
+type @dfn{dictionary}, also known as @dfn{associative array}.
 
-When you create a hash table, you specify a size, which indicates the
-expected number of elements that the table will hold.  You are not
-bound by this size, however; hash tables automatically resize themselves
-if the number of elements becomes too large.
+Internally, hash tables are hashed using the @dfn{linear probing} hash
+table implementation method.  This method hashes each key to a
+particular spot in the hash table, and then scans forward sequentially
+until a blank entry is found.  To look up a key, hash to the appropriate
+spot, then search forward for the key until either a key is found or a
+blank entry stops the search.  This method is used in preference to
+double hashing because of changes in recent hardware.  The penalty for
+non-sequential access to memory has been increasing, and this
+compensates for the problem of clustering that linear probing entails.
+
+When hash tables are created, the user may (but is not required to)
+specify initial properties that influence performance.
+
+Use the @code{:size} parameter to specify the number of entries that are
+likely to be stored in the hash table, to avoid the overhead of resizing
+the table.  But if the pre-allocated space for the entries is never
+used, it is simply wasted and makes XEmacs slower.  Excess unused hash
+table entries exact a small continuous performance penalty, since they
+must be scanned at every garbage collection.  If the number of entries
+in the hash table is unknown, simply avoid using the @code{:size}
+keyword.
+
+Use the @code{:rehash-size} and @code{:rehash-threshold} keywords to
+adjust the algorithm for deciding when to rehash the hash table.  For
+temporary hash tables that are going to be very heavily used, use a
+small rehash threshold, for example, 0.4 and a large rehash size, for
+example 2.0.  For permanent hash tables that will be infrequently used,
+specify a large rehash threshold, for example 0.8.
 
-(Internally, hash tables are hashed using a modification of the
-@dfn{linear probing} hash table method.  This method hashes each
-key to a particular spot in the hash table, and then scans forward
-sequentially until a blank entry is found.  To look up a key, hash
-to the appropriate spot, then search forward for the key until either
-a key is found or a blank entry stops the search.  The modification
-actually used is called @dfn{double hashing} and involves moving forward
-by a fixed increment, whose value is computed from the original hash
-value, rather than always moving forward by one.  This eliminates
-problems with clustering that can arise from the simple linear probing
-method.  For more information, see @cite{Algorithms} (second edition)
-by Robert Sedgewick, pp. 236-241.)
+Hash tables can also be created by the lisp reader using structure
+syntax, for example:
+@example
+#s(hash-table size 20 data (foo 1 bar 2))
+@end example
+
+The structure syntax accepts the same keywords as @code{make-hash-table}
+(without the @code{:} character), as well as the additional keyword
+@code{data}, which specifies the initial hash table contents.
+
+@defun make-hash-table &key @code{:size} @code{:test} @code{:type} @code{:rehash-size} @code{:rehash-threshold}
+This function returns a new empty hash table object.
+
+Keyword @code{:size} specifies the number of keys likely to be inserted.
+This number of entries can be inserted without enlarging the hash table.
+
+Keyword @code{:test} can be @code{eq}, @code{eql} (default) or @code{equal}.
+Comparison between keys is done using this function.
+If speed is important, consider using @code{eq}.
+When storing strings in the hash table, you will likely need to use @code{equal}.
+
+Keyword @code{:type} can be @code{non-weak} (default), @code{weak},
+@code{key-weak} or @code{value-weak}.
 
-@defun make-hashtable size &optional test-fun
-This function makes a hash table of initial size @var{size}.  Comparison
-between keys is normally done with @code{eql}; i.e. two keys must be the
-same object to be considered equivalent.  However, you can explicitly
-specify the comparison function using @var{test-fun}, which must be
-one of @code{eq}, @code{eql}, or @code{equal}.
+A weak hash table is one whose pointers do not count as GC referents:
+for any key-value pair in the hash table, if the only remaining pointer
+to either the key or the value is in a weak hash table, then the pair
+will be removed from the hash table, and the key and value collected.
+A non-weak hash table (or any other pointer) would prevent the object
+from being collected.
 
-Note that currently, @code{eq} and @code{eql} are the same.  This will
-change when bignums are implemented.
+A key-weak hash table is similar to a fully-weak hash table except that
+a key-value pair will be removed only if the key remains unmarked
+outside of weak hash tables.  The pair will remain in the hash table if
+the key is pointed to by something other than a weak hash table, even
+if the value is not.
+
+A value-weak hash table is similar to a fully-weak hash table except
+that a key-value pair will be removed only if the value remains
+unmarked outside of weak hash tables.  The pair will remain in the
+hash table if the value is pointed to by something other than a weak
+hash table, even if the key is not.
+
+Keyword @code{:rehash-size} must be a float greater than 1.0, and specifies
+the factor by which to increase the size of the hash table when enlarging.
+
+Keyword @code{:rehash-threshold} must be a float between 0.0 and 1.0,
+and specifies the load factor of the hash table which triggers enlarging.
 @end defun
 
-@defun copy-hashtable old-table
-This function makes a new hash table which contains the same keys and
-values as the given table.  The keys and values will not themselves be
+@defun copy-hash-table hash-table
+This function returns a new hash table which contains the same keys and
+values as @var{hash-table}.  The keys and values will not themselves be
 copied.
 @end defun
 
-@defun hashtable-fullness table
-This function returns number of entries in @var{table}.
+@defun hash-table-count hash-table
+This function returns the number of entries in @var{hash-table}.
+@end defun
+
+@defun hash-table-size hash-table
+This function returns the current number of slots in @var{hash-table},
+whether occupied or not.
+@end defun
+
+@defun hash-table-type hash-table
+This function returns the type of @var{hash-table}.
+This can be one of @code{non-weak}, @code{weak}, @code{key-weak} or
+@code{value-weak}.
+@end defun
+
+@defun hash-table-test hash-table
+This function returns the test function of @var{hash-table}.
+This can be one of @code{eq}, @code{eql} or @code{equal}.
+@end defun
+
+@defun hash-table-rehash-size hash-table
+This function returns the current rehash size of @var{hash-table}.
+This is a float greater than 1.0; the factor by which @var{hash-table}
+is enlarged when the rehash threshold is exceeded.
+@end defun
+
+@defun hash-table-rehash-threshold hash-table
+This function returns the current rehash threshold of @var{hash-table}.
+This is a float between 0.0 and 1.0; the maximum @dfn{load factor} of
+@var{hash-table}, beyond which the @var{hash-table} is enlarged by rehashing.
 @end defun
 
 @node Working With Hash Tables
 @section Working With Hash Tables
 
-@defun puthash key val table
-This function hashes @var{key} to @var{val} in @var{table}.
+@defun puthash key value hash-table
+This function hashes @var{key} to @var{value} in @var{hash-table}.
 @end defun
 
-@defun gethash key table &optional default
-This function finds the hash value for @var{key} in @var{table}.  If
-there is no corresponding value, @var{default} is returned (defaults to
-@code{nil}).
+@defun gethash key hash-table &optional default
+This function finds the hash value for @var{key} in @var{hash-table}.
+If there is no entry for @var{key} in @var{hash-table}, @var{default} is
+returned (which in turn defaults to @code{nil}).
 @end defun
 
-@defun remhash key table
-This function removes the hash value for @var{key} in @var{table}.
+@defun remhash key hash-table
+This function removes the entry for @var{key} from @var{hash-table}.
+Does nothing if there is no entry for @var{key} in @var{hash-table}.
 @end defun
 
-@defun clrhash table
-This function flushes @var{table}.  Afterwards, the hash table will
-contain no entries.
+@defun clrhash hash-table
+This function removes all entries from @var{hash-table}, leaving it empty.
 @end defun
 
-@defun maphash function table
-This function maps @var{function} over entries in @var{table}, calling
-it with two args, each key and value in the table.
+@defun maphash function hash-table
+This function maps @var{function} over entries in @var{hash-table},
+calling it with two args, each key and value in the hash table.
+
+@var{function} may not modify @var{hash-table}, with the one exception
+that @var{function} may remhash or puthash the entry currently being
+processed by @var{function}.
 @end defun
 
 @node Weak Hash Tables
@@ -135,17 +220,5 @@
 
 Also see @ref{Weak Lists}.
 
-@defun make-weak-hashtable size &optional test-fun
-This function makes a fully weak hash table of initial size @var{size}.
-@var{test-fun} is as in @code{make-hashtable}.
-@end defun
-
-@defun make-key-weak-hashtable size &optional test-fun
-This function makes a key-weak hash table of initial size @var{size}.
-@var{test-fun} is as in @code{make-hashtable}.
-@end defun
-
-@defun make-value-weak-hashtable size &optional test-fun
-This function makes a value-weak hash table of initial size @var{size}.
-@var{test-fun} is as in @code{make-hashtable}.
-@end defun
+Weak hash tables are created by specifying the @code{:type} keyword to
+@code{make-hash-table}.