hash.tex

%Part{Hash, Root = "CLM.MSS"}
%%%Chapter of Common Lisp Manual.  Copyright 1984, 1988, 1989 Guy L. Steele Jr.

\clearpage\def\pagestatus{FINAL PROOF}

\ifx \rulang\Undef

\chapter{Hash Tables}
\label{HASH}

A hash table is a Lisp object that can efficiently map a given
Lisp object to another Lisp object.
Each hash table has a set of \emph{entries}, each of which associates a
particular \emph{key} with a particular \emph{value}.  The basic functions
that deal with hash tables can create entries, delete entries, and find
the value that is associated with a given key.  Finding the value is
very fast, even if there are many entries, because hashing is used; this
is an important advantage of hash tables over property lists.

A given hash table can associate only one \emph{value} with a given
\emph{key}; if you try to add a second \emph{value}, it will replace the
first.  Also, adding a value to a hash table is a destructive operation;
the hash table is modified.  By contrast, association lists can be
augmented non-destructively.

Hash tables come in three kinds, the difference being whether the keys
are compared with \cdf{eq}, \cdf{eql}, or \cdf{equal}.  In other words, there
are hash tables that hash on Lisp \emph{objects} (using \cdf{eq} or \cdf{eql})
and there are hash tables that hash on \emph{tree structure}
(using \cdf{equal}).

Hash tables are created with the function
\cdf{make-hash-table}, which takes various options, including
which kind of hash table to make (the default being the \cdf{eql} kind).
To look up a key and find
the associated value, use \cdf{gethash}.
New entries are added
to hash tables using \cdf{setf} with \cdf{gethash}.
To remove an entry, use \cdf{remhash}.  Here is a simple example.
\begin{lisp}
(setq a (make-hash-table)) \\
(setf (gethash 'color a) 'brown) \\
(setf (gethash 'name a) 'fred) \\
(gethash 'color a) \EV\ brown \\
(gethash 'name a) \EV\ fred \\
(gethash 'pointy a) \EV\ {\false}
\end{lisp}

In this example, the symbols \cdf{color} and \cdf{name} are being used as
keys, and the symbols \cdf{brown} and \cdf{fred} are being used as the
associated values.  The hash table has two items in it, one of which
associates from \cdf{color} to \cdf{brown}, and the other of which
associates from \cdf{name} to \cdf{fred}.

Keys do not have to be symbols; they can be any Lisp object.  Similarly,
values can be any Lisp object.

\begin{newer}
There is a discrepancy between the preceding description of the
size of a hash table and the description of the \cd{:size} argument
in the specification below
of \cdf{make-hash-table}.

X3J13 voted in June 1989 \issue{HASH-TABLE-SIZE} to regard the
latter description as definitive: the \cd{:size} argument
is approximately the number of entries that can be inserted
without having to enlarge the hash table.  This definition is certainly
more convenient for the user.
\end{newer}

\section{Hash Table Functions}

This section documents the functions for hash tables, which
use \emph{objects} as keys and associate other objects with them.

\begin{defun}[Function]
make-hash-table &key :test :size :rehash-size :rehash-threshold

This function creates and returns a new hash table.
The \cd{:test} argument determines how keys are compared;
it must be one of the three values \cd{\#'eq}, \cd{\#'eql}, or \cd{\#'equal},
or one of the three symbols \cdf{eq}, \cdf{eql}, or \cdf{equal}.
If no test is specified, \cdf{eql} is assumed.

\begin{new}
X3J13 voted in January 1989
\issue{HASH-TABLE-TESTS}
to add a fourth type of hash table:
the value of \cd{\#'equalp} and the symbol \cdf{equalp} are to be additional
valid possibilities for the \cd{:test} argument.

Note that one consequence of
the vote to change the rules of
floating-point contagion
\issue{CONTAGION-ON-NUMERICAL-COMPARISONS}
(described in section~\ref{PRECISION-CONTAGION-COERCION-SECTION})
is to require \cdf{=}, and therefore also \cdf{equalp},
to compare the values of numbers exactly and not approximately, making
\cdf{equalp} a true equivalence relation on numbers.

Another valuable use of \cdf{equalp} hash tables is case-insensitive
comparison of keys that are strings.
\end{new}

The \cd{:size} argument
sets the initial size of the hash table, in entries.
(The actual size may be rounded up from the size
you specify to the next ``good'' size, for example to make it a prime number.)
You won't necessarily be able to store precisely
this many entries into the table
before it overflows and becomes bigger, but this argument does serve
as a hint to the implementation of approximately
how many entries you intend to store.

\begin{new}
X3J13 voted in January 1989
\issue{ARGUMENTS-UNDERSPECIFIED}
to clarify that the \cd{:size} argument
must be a non-negative integer.
\end{new}

\begin{newer}
X3J13 voted in June 1989 \issue{HASH-TABLE-SIZE} to regard the
preceding description of the \cd{:size} argument as definitive: it
is approximately the number of entries that can be inserted
without having to enlarge the hash table.
\end{newer}

The \cd{:rehash-size} argument
specifies how much to increase the size of the hash table when it becomes
full.  This can be an integer greater than zero,
which is the number of entries to add, or
it can be a floating-point number greater than 1,
which is the ratio of the new size to the old size.
The default value for this argument is implementation-dependent.

The \cd{:rehash-threshold} argument
specifies how full the hash table can get before it must grow.
It may be any \cdf{real} number between \cd{0} and \cd{1}, inclusive.
It indicates the maximum desired level of hash table occupancy.
An implementation is permitted to ignore this argument.
The default value for this argument is implementation-dependent.

An example of the use of \cdf{make-hash-table}:
\begin{lisp}
(make-hash-table :rehash-size 1.5 \\*
~~~~~~~~~~~~~~~~~:size (* number-of-widgets 43))
\end{lisp}
\end{defun}

\begin{defun}[Function]
hash-table-p object

\cdf{hash-table-p} is true if its argument is a hash table,
and otherwise is false.
\begin{lisp}
(hash-table-p x) \EQ\ (typep x 'hash-table)
\end{lisp}
\end{defun}

\begin{defun}[Function]
gethash key hash-table &optional default

\cdf{gethash} finds the entry in \emph{hash-table} whose key is \emph{key}
and returns the
associated value.  If there is no such entry, \cdf{gethash} returns \emph{default},
which is {\false} if not specified.

\cdf{gethash} actually returns two values, the second being a predicate
value that is true if an entry was found, and false if no entry was found.

\cdf{setf} may be used with \cdf{gethash} to make new entries in a hash
table.  If an entry with the specified \emph{key} already exists, it is
removed before the new entry is added.  The \emph{default} argument may be
specified to \cdf{gethash} in this context; it is ignored by \cdf{setf}
but may be useful in such macros as \cdf{incf} that are related to \cdf{setf}:
\begin{lisp}
(incf (gethash a-key table 0))
\end{lisp}
means approximately the same as
\begin{lisp}
(setf (gethash a-key table 0) \\*
~~~~~~(+ (gethash a-key table 0) 1))
\end{lisp}
which in turn would be treated as simply
\begin{lisp}
(setf (gethash a-key table) \\*
~~~~~~(+ (gethash a-key table 0) 1))
\end{lisp}
\end{defun}

\begin{defun}[Function]
remhash key hash-table

\cdf{remhash} removes
any entry for \emph{key} in \emph{hash-table}.  This is a predicate
that is true if there was an
entry or false if there was not.
\end{defun}

\begin{defun}[Function]
maphash function hash-table

For each entry in \emph{hash-table}, \cdf{maphash} calls
\emph{function} on two arguments:
the key of the entry and the value of the entry; \cdf{maphash} then returns \cdf{nil}.
If entries are added to or deleted from the hash table while a \cdf{maphash}
is in progress, the results are unpredictable, with one exception:
if the \emph{function} calls \cdf{remhash} to remove the entry currently
being processed by the \emph{function}, or performs a \cdf{setf} of
\cdf{gethash} on that entry to change the associated value, then those
operations will have the intended effect.
For example:
\begin{lisp}
;;; Alter every entry in MY-HASH-TABLE, replacing the value with \\
;;; its square root.  Entries with negative values are removed. \\
(maphash \#'(lambda (key val) \\
~~~~~~~~~~~~~(if (minusp val) \\
~~~~~~~~~~~~~~~~~(remhash key my-hash-table) \\
~~~~~~~~~~~~~~~~~(setf (gethash key my-hash-table) (sqrt val)))) \\
~~~~~~~~~my-hash-table)
\end{lisp}

\begin{new}
X3J13 voted in January 1989
\issue{MAPPING-DESTRUCTIVE-INTERACTION}
to restrict user side effects; see section~\ref{STRUCTURE-TRAVERSAL-SECTION}.
\end{new}
\end{defun}

\begin{defun}[Function]
clrhash hash-table

This removes all the entries from \emph{hash-table}
and returns the hash table itself.
\end{defun}

\begin{defun}[Function]
hash-table-count hash-table

This returns the number of entries in the \emph{hash-table}.
When a hash table is first created or has been cleared,
the number of entries is zero.
\end{defun}

\begin{defmac}
with-hash-table-iterator (mname hash-table) {form}*

X3J13 voted in January 1989
\issue{HASH-TABLE-PACKAGE-GENERATORS}
to add the macro \cdf{with-hash-table-iterator}.

The name \emph{mname} is bound and defined as if by \cdf{macrolet},
with the body \emph{form\/}s as its lexical scope, to be a ``generator macro''
such that successive invocations \cd{(\emph{mname})} will
return entries, one by one, from the hash table that is the value of the
expression \emph{hash-table} (which is evaluated exactly once).

At each invocation of the generator macro, there are two possibilities.
If there is yet another unprocessed entry in the hash table, then
three values are returned: \cdf{t},
the key of the hash table entry, and
the associated value of the hash table entry.
On the other hand, if there are no more unprocessed entries in the
hash table, then one value is returned: \cdf{nil}.

The implicit interior state of the iteration over the hash table
entries has dynamic extent.  While the name \emph{mname} has
lexical scope, it is an error to invoke the generator macro
once the \cdf{with-hash-table-iterator} form has been exited.

Invocations of \cdf{with-hash-table-iterator}
and related macros may be nested, and the generator macro of an
outer invocation may be called from within an inner invocation
(assuming that its name is visible or otherwise made available).

\begin{new}
X3J13 voted in January 1989
\issue{MAPPING-DESTRUCTIVE-INTERACTION}
to restrict user side effects; see section~\ref{STRUCTURE-TRAVERSAL-SECTION}.
\end{new}

\beforenoterule
\begin{rationale}
This facility is a bit more flexible than \cdf{maphash}.
It makes possible a portable and efficient implementation of \cdf{loop}
clauses for iterating over hash tables (see chapter~\ref{LOOP}).
\end{rationale}
\afternoterule
\end{defmac}

\begin{lisp}
(setq turtles (make-hash-table :size 9 :test 'eq)) \\*
(setf (gethash 'howard-kaylan turtles) '(musician lead-singer)) \\*
(setf (gethash 'john-barbata turtles) '(musician drummer)) \\*
(setf (gethash 'leonardo turtles) '(ninja leader blue)) \\*
(setf (gethash 'donatello turtles) '(ninja machines purple)) \\*
(setf (gethash 'al-nichol turtles) '(musician guitarist)) \\*
(setf (gethash 'mark-volman turtles) '(musician great-hair)) \\*
(setf (gethash 'raphael turtles) '(ninja cool rude red)) \\*
(setf (gethash 'michaelangelo turtles) '(ninja party-dude orange)) \\*
(setf (gethash 'jim-pons turtles) '(musician bassist)) \\
\\
(with-hash-table-iterator (get-turtle turtles) \\*
~~(labels ((try (got-one \&optional key value) \\*
~~~~~~~~~~~~~(when got-one\`;\textrm{Remember, keys may show up in any order} \\*
~~~~~~~~~~~~~~~(when (eq (first value) 'ninja) \\*
~~~~~~~~~~~~~~~~~(format t "{\Xtilde}\%{\Xtilde}:({\Xtilde}A{\Xtilde}): {\Xtilde}{\Xlbrace}{\Xtilde}A{\Xtilde}{\Xcircumflex}, {\Xtilde}{\Xrbrace}" \\*
~~~~~~~~~~~~~~~~~~~~~~~~~key (rest value))) \\*
~~~~~~~~~~~~~~~(multiple-value-call \#'try (get-turtle))))) \\*
~~~~(multiple-value-call \#'try (get-turtle))))~~~~~;\textrm{Prints 4 lines} \\*
Michaelangelo: PARTY-DUDE, ORANGE \\*
Leonardo: LEADER, BLUE \\*
Raphael: COOL, RUDE, RED \\*
Donatello: MACHINES, PURPLE \\*
~~\EV\ nil
\end{lisp}

\begin{defun}[Function]
hash-table-rehash-size hash-table \\
hash-table-rehash-threshold hash-table \\
hash-table-size hash-table \\
hash-table-test hash-table

X3J13 voted in March 1989 \issue{HASH-TABLE-ACCESS}
to add four accessor functions that return values suitable for use in a call to
\cdf{make-hash-table} in order to produce a new hash table with state
corresponding to the current state of the argument hash table.
 
\cdf{hash-table-rehash-size} returns the current rehash size of a hash table.

\cdf{hash-table-rehash-threshold} returns the current rehash threshold.

\cdf{hash-table-size} returns the current size of a hash table.

\cdf{hash-table-test} returns the test used for comparing keys.
If the test is one of the standard test functions, then the result
will always be a symbol, even if the function itself was specified
when the \emph{hash-table} was created.  For example:
\begin{lisp}
(hash-table-test (make-hash-table :test \#'equal)) \EV\ equal
\end{lisp}
Implementations that extend \cdf{make-hash-table} by providing additional
possibilities for the \cd{:test} argument may determine how the
value returned by \cdf{hash-table-test} is related to such additional tests.
\end{defun} 

\section{Primitive Hash Function}

The function \cdf{sxhash} is a convenient tool for the user who needs
to create more complicated hashed data structures than are provided by
\cdf{hash-table} objects.

\begin{defun}[Function]
sxhash object

\cdf{sxhash} computes a hash code for an object and returns the hash code as
a non-negative fixnum.  A property of \cdf{sxhash}
is that \cd{(equal \emph{x} \emph{y})} implies \cd{(= (sxhash \emph{x}) (sxhash \emph{y}))}.

The manner in which the hash code is computed is implementation-dependent
but independent of the particular ``incarnation'' or ``core image.''
Hash values produced
by \cdf{sxhash} may be written out to files, for example, and meaningfully
read in again into an instance of the same implementation.
\end{defun}

%RUSSIAN
\else

\chapter{Хеш-таблицы}
\label{HASH}

Хеш-таблица является Lisp'овыми объектом, который может быстро отображать
заданный Lisp'овый объект в другой Lisp'овый объект. 
\emph{Wikipedia более понятно излагает: это структура данных, реализующая интерфейс
ассоциативного массива, а именно, она позволяет хранить пары (ключ, значение) и
выполнять три операции: операцию добавления новой пары, операцию поиска и
операцию удаления пары по ключу.}
Каждая хеш-таблица содержит множество \emph{элементов}, каждый из которых
содержит \emph{значение} ассоциированное с \emph{ключом}. Базовые функции
взаимодействия с хеш-таблицей могут создавать элементы (пары ключ-значение),
удалять элементы и искать значения по заданному ключу. Поиск значения очень
быстрый, даже при наличии большого количества элементов, потому что используется
хеширование. Это самое важное преимущество хеш-таблиц перед списками свойств.

Хеш-таблица может связывать только одно \emph{значение} с заданным
\emph{ключом}. Если вы попробуете добавить второе \emph{значение}, оно заменит
предыдущее. К тому же, добавление значения в хеш-таблицу является деструктивной
операцией, в этом случае хеш-таблица модифицируется. Ассоциативные списки же,
наоборот, могут расширяться недеструктивно.

Хеш-таблицы существуют в трёх видах, различие между ними в том, как сравниваются
ключи, с помощью \cdf{eq}, \cdf{eql} или \cdf{equal}. Другими словами,
существуют хеш таблицы с ключами, которые используют Lisp'овые \emph{объекты}
(\cdf{eq} или \cdf{eql}) и которые используют \emph{древовидные структуры}
(\cdf{equal}). FIXME

Хеш-таблицы создаются функцией \cdf{make-hash-table}, которая принимает
различные параметры, включая тип хеш-таблицы (по-умолчанию тип \cdf{eql}).
Для поиска значения по ключу используйте \cdf{gethash}.
Новые элементы могут быть добавлены с помощью \cdf{gethash} внутри \cdf{setf}.
Для удаления элементов используйте \cdf{remhash}. Вот простой пример.
\begin{lisp}
(setq a (make-hash-table)) \\
(setf (gethash 'color a) 'brown) \\
(setf (gethash 'name a) 'fred) \\
(gethash 'color a) \EV\ brown \\
(gethash 'name a) \EV\ fred \\
(gethash 'pointy a) \EV\ {\false}
\end{lisp}

В этом примере, символы \cd{color} и \cd{name} используются в качестве ключей, а
символы \cd{brown} и \cd{fred} в качестве ассоциированных значений. Хеш-таблица
содержит две пары, в одной ключ \cd{color} связан с \cd{brown}, а в другой
\cd{name} с \cd{fred}.

Ключи необязательно должны быть символами. Они могут быть любыми Lisp'овыми
объектами. Значения также могут быть любыми Lisp'овыми объектами.

\begin{newer}
There is a discrepancy between the preceding description of the
size of a hash table and the description of the \cd{:size} argument
in the specification below
of \cdf{make-hash-table}.

X3J13 voted in June 1989 \issue{HASH-TABLE-SIZE} to regard the
latter description as definitive: the \cd{:size} argument
is approximately the number of entries that can be inserted
without having to enlarge the hash table.  This definition is certainly
more convenient for the user.
\end{newer}

\section{Функции для хеш-таблиц}

Данный раздел описывает функции для хеш-таблиц, которые используют
\emph{объекты} для ключей и ассоциируют другие объекты с этими.

\begin{defun}[Функция]
make-hash-table &key :test :size :rehash-size :rehash-threshold

Эта функция создаёт и возвращает новую хеш-таблицу.
Аргумент \cd{:test} определяет как будут сравниваться ключи.
Он может быть одним из трёх значений \cd{\#'eq}, \cd{\#'eql} или \cd{\#'equal},
или одним из трёх символов \cdf{eq}, \cdf{eql} или \cdf{equal}.
По-умолчанию используется \cdf{eql}.

\begin{new}
X3J13 voted in January 1989
\issue{HASH-TABLE-TESTS}
to add a fourth type of hash table:
the value of \cd{\#'equalp} and the symbol \cdf{equalp} are to be additional
valid possibilities for the \cd{:test} argument.

Note that one consequence of
the vote to change the rules of
floating-point contagion
\issue{CONTAGION-ON-NUMERICAL-COMPARISONS}
(described in section~\ref{PRECISION-CONTAGION-COERCION-SECTION})
is to require \cdf{=}, and therefore also \cdf{equalp},
to compare the values of numbers exactly and not approximately, making
\cdf{equalp} a true equivalence relation on numbers.

Another valuable use of \cdf{equalp} hash tables is case-insensitive
comparison of keys that are strings.
\end{new}

Аргумент \cd{:size} устанавливает первоначальный размер хеш-таблицы в парах.
(Указанный размер может быть округлён до <<хорошего>> размера, например, до
первого следующего простого числа.)
Вы можете не сохранять в таблице столько пар, сколько указали. Этот аргумент
служит подсказкой для реализации о том, какое примерно число элементов вы будете
хранить в хеш-таблице.

\begin{new}
X3J13 voted in January 1989
\issue{ARGUMENTS-UNDERSPECIFIED}
to clarify that the \cd{:size} argument
must be a non-negative integer.
\end{new}

\begin{newer}
X3J13 voted in June 1989 \issue{HASH-TABLE-SIZE} to regard the
preceding description of the \cd{:size} argument as definitive: it
is approximately the number of entries that can be inserted
without having to enlarge the hash table.
\end{newer}

Аргумент \cd{:rehash-size} указывает, на сколько увеличить размер хеш-таблицы,
когда она по размерам достигнет пределов.
Если это целое число, оно должно быть больше нуля, и будет означать абсолютное
приращение. Если это число с плавающей точкой, оно должно быть больше 1, и будет
означать относительное приращение к предыдущему размеру.
Значение по-умолчанию зависит от реализации.

Аргумент \cd{:rehash-threshold} указывает, насколько должна наполниться
хеш-таблица, прежде чем она будет увеличена. Он должен быть числом типа
\cdf{real} между \cd{0} и \cd{1}, включительно.
Он показывает максимальный уровень заполнения хеш-таблицы.
Значение по-умолчанию зависит от реализации.

Пример использования \cdf{make-hash-table}:
\begin{lisp}
(make-hash-table :rehash-size 1.5 \\*
~~~~~~~~~~~~~~~~~:size (* number-of-widgets 43))
\end{lisp}
\end{defun}

\begin{defun}[Функция]
hash-table-p object

\cdf{hash-table-p} возвращает истину, если аргумент является хеш-таблицей. Иначе
возвращает ложь.
\begin{lisp}
(hash-table-p x) \EQ\ (typep x 'hash-table)
\end{lisp}
\end{defun}

\begin{defun}[Функция]
gethash key hash-table &optional default

\cdf{gethash} ищет элемент в хеш-\emph{hash-table}, чей ключ равен \emph{key} и
возвращает связанное значение. Если элемент не был найден, то возвращается
значение аргумента \emph{default}, который по-умолчанию равен {\false}.

\cdf{gethash} возвращает два значение. Второе значение является предикатом, и
истинно, если значение было найдено, и ложно если нет.

\cdf{setf} может использоваться вместе с \cdf{gethash} для создания в
хеш-таблице новых элементов. Если элемент с заданным ключом \emph{key} уже
существует, он будет удалён перед добавлением. В этом контексте может
использоваться аргумент \emph{default}, он игнорируется \cdf{setf}, но может
быть полезным в таких макросах как \cdf{incf}, которые связаны с \cdf{setf}:
\begin{lisp}
(incf (gethash a-key table 0))
\end{lisp}
обозначает то же, что и 
\begin{lisp}
(setf (gethash a-key table 0) \\*
~~~~~~(+ (gethash a-key table 0) 1))
\end{lisp}
что можно преобразовать в
\begin{lisp}
(setf (gethash a-key table) \\*
~~~~~~(+ (gethash a-key table 0) 1))
\end{lisp}
\end{defun}

\begin{defun}[Функция]
remhash key hash-table

\cdf{remhash} удаляет любой элемент в хеш-таблице \emph{hash-table} ключ,
которого равен параметру \emph{key}. Возвращает истину, если элемент был
удалён, и ложь, если элемента уже не существовало.
\end{defun}

\begin{defun}[Функция]
maphash function hash-table

Для каждого элемента в хеш-таблице \emph{hash-table}, \cdf{maphash} вызывает
функцию \emph{function} с двумя аргументами:
ключ элемента и
значение элемента.
\cdf{maphash} возвращает \cdf{nil}.
Если во время выполнения \cdf{maphash} в хеш-таблице добавлялись или удалялись
ключи, то результат непредсказуем, но есть исключение:
если функция \emph{function} вызывает \cdf{remhash} для удаления элемента,
который в эту функцию и был передан, или устанавливает новое значение с помощью
\cdf{setf} этому элементу, то эти операции будут выполнены правильно.
Например:
\begin{lisp}
;;; Изменение каждого элемента в MY-HASH-TABLE, с заменой на \\
;;; квадратный корень. Элементы с отрицательными значения удаляются. \\
(maphash \#'(lambda (key val) \\
~~~~~~~~~~~~~(if (minusp val) \\
~~~~~~~~~~~~~~~~~(remhash key my-hash-table) \\
~~~~~~~~~~~~~~~~~(setf (gethash key my-hash-table) (sqrt val)))) \\
~~~~~~~~~my-hash-table)
\end{lisp}

\begin{new}
X3J13 voted in January 1989
\issue{MAPPING-DESTRUCTIVE-INTERACTION}
to restrict user side effects; see section~\ref{STRUCTURE-TRAVERSAL-SECTION}.
\end{new}

Пользователь ограничен в создании побочных действий так, как это описано в
разделе~\ref{STRUCTURE-TRAVERSAL-SECTION}
\end{defun}

\begin{defun}[Функция]
clrhash hash-table

Функция удаляет все элемент из хеш-таблицы \emph{hash-table} и возвращает эту
хеш-таблицу.
\end{defun}

\begin{defun}[Функция]
hash-table-count hash-table

Функция возвращает количество элементов в хеш-таблице \emph{hash-table}.
Когда хеш-таблица только были сделана, или только что очищена, то количество
элементов равно нулю.
\end{defun}

\begin{defmac}
with-hash-table-iterator (mname hash-table) {form}*

X3J13 voted in January 1989
\issue{HASH-TABLE-PACKAGE-GENERATORS}
to add the macro \cdf{with-hash-table-iterator}.

The name \emph{mname} is bound and defined as if by \cdf{macrolet},
with the body \emph{form\/}s as its lexical scope, to be a ``generator macro''
such that successive invocations \cd{(\emph{mname})} will
return entries, one by one, from the hash table that is the value of the
expression \emph{hash-table} (which is evaluated exactly once).

At each invocation of the generator macro, there are two possibilities.
If there is yet another unprocessed entry in the hash table, then
three values are returned: \cdf{t},
the key of the hash table entry, and
the associated value of the hash table entry.
On the other hand, if there are no more unprocessed entries in the
hash table, then one value is returned: \cdf{nil}.

The implicit interior state of the iteration over the hash table
entries has dynamic extent.  While the name \emph{mname} has
lexical scope, it is an error to invoke the generator macro
once the \cdf{with-hash-table-iterator} form has been exited.

Invocations of \cdf{with-hash-table-iterator}
and related macros may be nested, and the generator macro of an
outer invocation may be called from within an inner invocation
(assuming that its name is visible or otherwise made available).

\begin{new}
X3J13 voted in January 1989
\issue{MAPPING-DESTRUCTIVE-INTERACTION}
to restrict user side effects; see section~\ref{STRUCTURE-TRAVERSAL-SECTION}.
\end{new}

\beforenoterule
\begin{rationale}
This facility is a bit more flexible than \cdf{maphash}.
It makes possible a portable and efficient implementation of \cdf{loop}
clauses for iterating over hash tables (see chapter~\ref{LOOP}).
\end{rationale}
\afternoterule
\end{defmac}

\begin{lisp}
(setq turtles (make-hash-table :size 9 :test 'eq)) \\*
(setf (gethash 'howard-kaylan turtles) '(musician lead-singer)) \\*
(setf (gethash 'john-barbata turtles) '(musician drummer)) \\*
(setf (gethash 'leonardo turtles) '(ninja leader blue)) \\*
(setf (gethash 'donatello turtles) '(ninja machines purple)) \\*
(setf (gethash 'al-nichol turtles) '(musician guitarist)) \\*
(setf (gethash 'mark-volman turtles) '(musician great-hair)) \\*
(setf (gethash 'raphael turtles) '(ninja cool rude red)) \\*
(setf (gethash 'michaelangelo turtles) '(ninja party-dude orange)) \\*
(setf (gethash 'jim-pons turtles) '(musician bassist)) \\
\\
(with-hash-table-iterator (get-turtle turtles) \\*
~~(labels ((try (got-one \&optional key value) \\*
~~~~~~~~~~~~~(when got-one\`;\textrm{Remember, keys may show up in any order} \\*
~~~~~~~~~~~~~~~(when (eq (first value) 'ninja) \\*
~~~~~~~~~~~~~~~~~(format t "{\Xtilde}\%{\Xtilde}:({\Xtilde}A{\Xtilde}): {\Xtilde}{\Xlbrace}{\Xtilde}A{\Xtilde}{\Xcircumflex}, {\Xtilde}{\Xrbrace}" \\*
~~~~~~~~~~~~~~~~~~~~~~~~~key (rest value))) \\*
~~~~~~~~~~~~~~~(multiple-value-call \#'try (get-turtle))))) \\*
~~~~(multiple-value-call \#'try (get-turtle))))~~~~~;\textrm{Prints 4 lines} \\*
Michaelangelo: PARTY-DUDE, ORANGE \\*
Leonardo: LEADER, BLUE \\*
Raphael: COOL, RUDE, RED \\*
Donatello: MACHINES, PURPLE \\*
~~\EV\ nil
\end{lisp}

\begin{defun}[Функция]
hash-table-rehash-size hash-table \\
hash-table-rehash-threshold hash-table \\
hash-table-size hash-table \\
hash-table-test hash-table

Добавлены функции, которые возвращают значения используемые при вызове
\cdf{make-hash-table}.

\cdf{hash-table-rehash-size} возвращает размер приращения хеш-таблицы.

\cdf{hash-table-rehash-threshold} возвращает текущий уровень заполнения.

\cdf{hash-table-size} возвращает рекомендуемый размер хеш-таблицы.

\cdf{hash-table-test} возвращает функцию сравнения используемую для ключей.
Если данная функция одна из стандартных, то результат всегда является символом,
даже если при создании хеш-таблицы было указано иное. Например:
\begin{lisp}
(hash-table-test (make-hash-table :test \#'equal)) \EV\ equal
\end{lisp}
Реализации, которые расширяют \cdf{make-hash-table} дополнительными функциями
сравнения для аргумента \cd{:test}, могут определять, как будет возвращено
значение из \cdf{hash-table-test} для этих дополнительных функций.
\end{defun} 

\section{Функция хеширования}

Функция \cdf{sxhash} является удобным инструментом для пользователя,
нуждающегося в создании более сложных хешированных структур данных, чем
предоставляются объектами \cdf{hash-table}.

\begin{defun}[Функция]
sxhash object

\cdf{sxhash} вычисляет хеш для объекта и возвращает этот хеш, как
неотрицательное число fixnum. Свойство \cdf{sxhash} заключается в том, что
\cd{(equal \emph{x} \emph{y})} подразумевает \cd{(= (sxhash \emph{x}) (sxhash
  \emph{y}))}.

Механизм вычисления хеша зависит от реализации, но независим от запущенного
экземпляра.
Например, вычисленные \cdf{sxhash} хеши могут быть записаны в файлы, и без
потери информации прочитаны из них в рамках одной реализации.
\end{defun}

\fi