MAKE-HASH-TABLEMAKE-HASH-TABLE accepts two additional keyword arguments
:INITIAL-CONTENTS and :WEAK:
(MAKE-HASH-TABLE&KEY:TEST :INITIAL-CONTENTS :SIZE :REHASH-SIZE :REHASH-THRESHOLD :WARN-IF-NEEDS-REHASH-AFTER-GC :WEAK)
The :TEST argument can be, other than one of the symbols EQ,
EQL, EQUAL, EQUALP, one of the symbols EXT:FASTHASH-EQ and
EXT:STABLEHASH-EQ. Both of these tests use EQ as the comparison
function; they differ in their performance characteristics.
EXT:FASTHASH-EQEXT:STABLEHASH-EQSYMBOL,
EXT:STANDARD-STABLEHASH (subclass of STANDARD-OBJECT) and
EXT:STRUCTURE-STABLEHASH (subclass of STRUCTURE-OBJECT) are
stable across GCs.
This test can thus avoid the scalability problems if all keys,
other than immediate objects, are SYMBOL, EXT:STANDARD-STABLEHASH or
EXT:STRUCTURE-STABLEHASH instances.
One can recommend to use EXT:FASTHASH-EQ for short-lived hash tables.
For tables with a longer lifespan which can be big or accessed
frequently, it is recommended to use EXT:STABLEHASH-EQ, and to modify the
objects that are used as its keys to become instances of
EXT:STANDARD-STABLEHASH or EXT:STRUCTURE-STABLEHASH.
When the symbol EQ or the function #'eq is
used as a :TEST argument, the value of the variable
CUSTOM:*EQ-HASHFUNCTION* is used instead.
This value must be one of EXT:FASTHASH-EQ, EXT:STABLEHASH-EQ.
Similarly, the :TEST argument can also be one
of the symbols EXT:FASTHASH-EQL,
EXT:STABLEHASH-EQL,
EXT:FASTHASH-EQUAL,
EXT:STABLEHASH-EQUAL.
The same remarks apply as for EXT:FASTHASH-EQ and EXT:STABLEHASH-EQ.
When the symbol EQL or the function #'eql is used
as a :TEST argument, the value of the variable
CUSTOM:*EQL-HASHFUNCTION* is used instead;
this value must be one of EXT:FASTHASH-EQL,
EXT:STABLEHASH-EQL.
Similarly, when the symbol EQUAL or the function #'equal
is used as a :TEST argument, the value of the variable
CUSTOM:*EQUAL-HASHFUNCTION* is used instead;
this value must be one of EXT:FASTHASH-EQUAL,
EXT:STABLEHASH-EQUAL.
The :WARN-IF-NEEDS-REHASH-AFTER-GC argument,
if true, causes a WARNING to be SIGNALed when an object is stored
into the table which will force table reorganizations at the first
access of the table after each garbage-collection.
This keyword argument can be used to check whether EXT:STABLEHASH-EQ
should be preferred over EXT:FASTHASH-EQ for a particular table.
Use HASH-TABLE-WARN-IF-NEEDS-REHASH-AFTER-GC
to check and SETF this parameter after the table has been created.
The :INITIAL-CONTENTS argument is an
association list that is used to initialize the new hash table.
The :REHASH-THRESHOLD argument is ignored.
The :WEAK argument can take the following values:
NIL (default) |
:KEY |
:VALUE |
:KEY-AND-VALUE |
:KEY-OR-VALUE |
and specifies whether the HASH-TABLE is weak:
if the key, value, either or both are not accessible for the garbage-collection
purposes, i.e., if they are only accessible via weak HASH-TABLEs
and EXT:WEAK-POINTERs, it is garbage-collected and removed from the weak
HASH-TABLE.
The SETFable predicate EXT:HASH-TABLE-WEAK-P
checks whether the HASH-TABLE is weak.
Note that the only test that makes sense for weak hash tables are
EQ and its variants EXT:FASTHASH-EQ and EXT:STABLEHASH-EQ.
Just like all other weak objects, weak
HASH-TABLEs cannot be printed readably.
See also Section 31.7.9, “Weak Hash Tables”.
HASH-TABLEs and garbage-collectionWhen a hash table contains keys to be compared by identity - such
as NUMBERs in HASH-TABLEs with the HASH-TABLE-TEST EQ;
or CONSes in tables which test with EQ or EQL;
or VECTORs in tables which test with EQ, EQL or EQUAL;
or STANDARD-OBJECT or STRUCTURE-OBJECT instances in tables which
test with EQ, EQL, EQUAL or EQUALP;
- the hash code will in general depend on the object's address in
memory. Therefore it will in general be invalidated after a garbage-collection,
and the hash table's internal structure must be recomputed at the next
table access.
While :WARN-IF-NEEDS-REHASH-AFTER-GC can help
checking the efficiency of a particular HASH-TABLE, the variable
CUSTOM:*WARN-ON-HASHTABLE-NEEDING-REHASH-AFTER-GC*
achieves the same effect for all HASH-TABLEs in the system at once:
when CUSTOM:*WARN-ON-HASHTABLE-NEEDING-REHASH-AFTER-GC* is true and a
HASH-TABLE needs to be rehashed after a garbage-collection, a warning is
issued that shows the inefficient HASH-TABLE.
What can be done to avoid the inefficiencies detected by these warnings?
STABLEHASH variant of the hash
test.STANDARD-OBJECT or
STRUCTURE-OBJECT instances, you can solve the problem by making
the key object classes inherit from EXT:STANDARD-STABLEHASH or
EXT:STRUCTURE-STABLEHASH, respectively.EXT:DEFINE-HASH-TABLE-TESTYou can define a new hash table test using the macro
EXT:DEFINE-HASH-TABLE-TEST: (, after
which EXT:DEFINE-HASH-TABLE-TEST test-name test-function hash-function)test-name can be passed as the
:TEST argument to MAKE-HASH-TABLE.
E.g.:
(EXT:DEFINE-HASH-TABLE-TESTstringSTRING=SXHASH) (MAKE-HASH-TABLE:test 'string)
(which is not too useful because it is equivalent to an EQUAL
HASH-TABLE but less efficient).
The fundamental requirement is that the test-function and hash-function are
consistent:
(FUNCALLtest-functionxy) ⇒ (=(FUNCALLhash-functionx) (FUNCALLhash-functiony))
This means that the following definition:
(EXT:DEFINE-HASH-TABLE-TESTnumber=SXHASH) ; broken!
is not correct because ( is
= 1 1d0)T but (
is = (SXHASH 1) (SXHASH 1d0))NIL. The correct way is, e.g.:
(EXT:DEFINE-HASH-TABLE-TESTnumber=(LAMBDA(x) (SXHASH(COERCEx 'SHORT-FLOAT))))
(note that ( does not
cons up fresh objects while COERCE x SHORT-FLOAT)( does).COERCE x
DOUBLE-FLOAT)
HASH-TABLE-TESTFunction HASH-TABLE-TEST returns either one of EXT:FASTHASH-EQ,
EXT:STABLEHASH-EQ, EXT:FASTHASH-EQL,
EXT:STABLEHASH-EQL,
EXT:FASTHASH-EQUAL,
EXT:STABLEHASH-EQUAL, EQUALP (but not EQ, EQL
nor EQUAL anymore), or, for HASH-TABLEs
created with a user-defined HASH-TABLE-TEST (see macro EXT:DEFINE-HASH-TABLE-TEST),
a CONS cell (.
test-function . hash-function)
EXT:DOHASHFor iteration through a HASH-TABLE, a macro EXT:DOHASH,
similar to DOLIST, can be used instead of MAPHASH:
(EXT:DOHASH(key-varvalue-varhash-table-form[resultform]) {declaration}* {tag|form}*)
EXT:DOHASH forms are iteration forms.
| These notes document CLISP version 2.45 | Last modified: 2008-04-15 |