Figure 18--1 lists some defined names that are applicable to hash tables. The following rules apply to hash tables.
(setq a (make-hash-table)) => #<HASH-TABLE EQL 0/120 32536573> (setf (gethash 'color a) 'brown) => BROWN (setf (gethash 'name a) 'fred) => FRED (gethash 'color a) => BROWN, true (gethash 'name a) => FRED, true (gethash 'pointy a) => NIL, falseIn this example, the symbols color and name are being used as keys, and the symbols brown and fred are being used as the associated values. The hash table has two items in it, one of which associates from color to brown, and the other of which associates from name to fred.
clrhash hash-table-p remhash gethash make-hash-table sxhash hash-table-count maphash
Figure 18--1: Hash-table defined names
The function supplied as the :test argument to make-hash-table specifies the `equivalence test' for the hash table it creates.
An object is `visibly modified' with regard to an equivalence test if there exists some set of objects (or potential objects) which are equivalent to the object before the modification but are no longer equivalent afterwards.
If an object O_1 is used as a key in a hash table H and is then visibly modified with regard to the equivalence test of H, then the consequences are unspecified if O_1, or any object O_2 equivalent to O_1 under the equivalence test (either before or after the modification), is used as a key in further operations on H. The consequences of using O_1 as a key are unspecified even if O_1 is visibly modified and then later modified again in such a way as to undo the visible modification.
Following are specifications of the modifications which are visible to the equivalence tests which must be supported by hash tables. The modifications are described in terms of modification of components, and are defined recursively. Visible modifications of components of the object are visible modifications of the object.
No standardized function is provided that is capable of visibly modifying an object with regard to eq or eql.
As a consequence of the behavior for equal, the rules for visible modification of objects not explicitly mentioned in this section are inherited from those in section Visible Modification of Objects with respect to EQ and EQL.
Any visible change to the car or the cdr of a cons is considered a visible modification with regard to equal.
For a vector of type bit-vector or of type string, any visible change to an active element of the vector, or to the length of the vector (if it is actually adjustable or has a fill pointer) is considered a visible modification with regard to equal.
As a consequence of the behavior for equalp, the rules for visible modification of objects not explicitly mentioned in this section are inherited from those in section Visible Modification of Objects with respect to EQUAL.
Any visible change to a slot of a structure is considered a visible modification with regard to equalp.
In an array, any visible change to an active element, to the fill pointer (if the array can and does have one), or to the dimensions (if the array is actually adjustable) is considered a visible modification with regard to equalp.
In a hash table, any visible change to the count of entries in the hash table, to the keys, or to the values associated with the keys is considered a visible modification with regard to equalp.
Note that the visibility of modifications to the keys depends on the equivalence test of the hash table, not on the specification of equalp.
Implementations that extend the language by providing additional mutator functions (or additional behavior for existing mutator functions) must document how the use of these extensions interacts with equivalence tests and hash table searches.
Implementations that extend the language by defining additional acceptable equivalence tests for hash tables (allowing additional values for the :test argument to make-hash-table) must document the visible components of these tests.
hash-table, t
Hash tables provide a way of mapping any object (a key) to an associated object (a value).
section Hash Table Concepts, section Printing Other Objects
The intent is that this mapping be implemented by a hashing mechanism, such as that described in Section 6.4 "Hashing" of {The Art of Computer Programming, Volume 3} (pp506-549). In spite of this intent, no conforming implementation is required to use any particular technique to implement the mapping.
make-hash-table {&key test size rehash-size rehash-threshold} => hash-table
test---a designator for one of the functions eq, eql, equal, or
equalp.
The default is eql.
size---a non-negative integer.
The default is implementation-dependent.
rehash-size---a real of type (or (integer 1 *) (float (1.0) *)). The default is implementation-dependent.
rehash-threshold---a real of type (real 0 1). The default is implementation-dependent.
hash-table---a hash table.
Creates and returns a new hash table.
test determines how keys are compared. An object is said to be present in the hash-table if that object is the same under the test as the key for some entry in the hash-table.
size is a hint to the implementation about how much initial space to allocate in the hash-table.
This information, taken together with the rehash-threshold, controls the approximate number of entries which it should be possible to insert before the table has to grow.
The actual size might be rounded up from size to the next `good' size; for example, some implementations might round to the next prime number.
rehash-size specifies a minimum amount to increase the size of the hash-table when it becomes full enough to require rehashing; see rehash-theshold below.
If rehash-size is an integer, the expected growth rate for the table is additive and the integer is the number of entries to add; if it is a float, the expected growth rate for the table is multiplicative and the float is the ratio of the new size to the old size.
As with size, the actual size of the increase might be rounded up.
rehash-threshold specifies how full the hash-table can get before it must grow.
It specifies the maximum desired hash-table occupancy level.
The values of rehash-size and rehash-threshold do not constrain the implementation to use any particular method for computing when and by how much the size of hash-table should be enlarged. Such decisions are implementation-dependent, and these values only hints from the programmer to the implementation, and the implementation is permitted to ignore them.
(setq table (make-hash-table)) => #<HASH-TABLE EQL 0/120 46142754> (setf (gethash "one" table) 1) => 1 (gethash "one" table) => NIL, false (setq table (make-hash-table :test 'equal)) => #<HASH-TABLE EQUAL 0/139 46145547> (setf (gethash "one" table) 1) => 1 (gethash "one" table) => 1, T (make-hash-table :rehash-size 1.5 :rehash-threshold 0.7) => #<HASH-TABLE EQL 0/120 46156620>
section gethash [Accessor] , hash-table
hash-table-p object => generalized-boolean
object---an object.
generalized-boolean---a generalized boolean.
Returns true if object is of type hash-table; otherwise, returns false.
(setq table (make-hash-table)) => #<HASH-TABLE EQL 0/120 32511220> (hash-table-p table) => true (hash-table-p 37) => false (hash-table-p '((a . 1) (b . 2))) => false
(hash-table-p object) == (typep object ' match, then the one occurring earlier in sequence is discarded, unless from-end is true, in which case the one later in sequence is discarded.remove-duplicates and delete-duplicates return a sequence of the same type as sequence with enough elements removed so that no two of the remaining elements match. The order of the elements remaining in the result is the same as the order in which they appear in sequence.
remove-duplicates returns a sequence that may share with sequence or may be identical to sequence if no elements need to be removed.
delete-duplicates, when sequence is a list, is permitted to setf any part, car or cdr, of the top-level list structure in that sequence. When sequence is a vector, delete-duplicates is permitted to change the dimensions of the vector and to slide its elements into new positions without permuting them to produce the resulting vector.
Examples::
(remove-duplicates "aBcDAbCd" :test #'char-equal :from-end t) => "aBcD" (remove-duplicates '(a b c b d d e)) => (A C B D E) (remove-duplicates '(a b c b d d e) :from-end t) => (A B C D E) (remove-duplicates '((foo #\a) (bar #\%) (baz #\A)) :test #'char-equal :key #'cadr) => ((BAR #\%) (BAZ #\A)) (remove-duplicates '((foo #\a) (bar #\%) (baz #\A)) :test #'char-equal :key #'cadr :from-end t) => ((FOO #\a) (BAR #\%)) (setq tester (list 0 1 2 3 4 5 6)) (delete-duplicates tester :key #'oddp :start 1 :end 6) => (0 4 5 6)Side Effects::
delete-duplicates might destructively modify sequence.
Exceptional Situations::
Should signal an error of type type-error if sequence is not a proper sequence.
See Also::
section Compiler Terminology,
section Traversal Rules and Side Effects
Notes::
The :test-not argument is deprecated.
These functions are useful for converting sequence into a canonical form suitable for representing a set.
Go to the first, previous, next, last section, table of contents.