Changes between Version 65 and Version 66 of HashTablesCowan
 Timestamp:
 06/15/13 14:57:40 (4 years ago)
Legend:
 Unmodified
 Added
 Removed
 Modified

HashTablesCowan
v65 v66 17 17 == Issues == 18 18 19 1. Should we support [wiki:ComparatorsCowan comparators] as alternatives to equality procedures? That packages up the equality predicate with the hash function; if no hash function is available, but an order predicate is, the hash table can fall back to an O(log n) tree.20 21 2. Alternatively, what if we did not support arbitrary equality predicates, but only allowed `eq?`, `eqv?`, `equal?`, and `string=?` (hash tables that support `equal?` will also support `string=?`). We could further allow `stringci=?` as an optional ("should") equality predicate. This would allow us to support more Scheme implementations and eliminate any need to deal with userspecified hash functions, though it is a considerable restriction on generality.19 1. (resolved) 20 21 2. (resolved) 22 22 23 23 == Rationale == … … 27 27 There is no mandated support for thread safety, immutability, or weakness, though there is a semiportable hook for specifying these features. 28 28 29 This specification accepts separate equality predicates and hash functions for backward compatibility, but strongly encourages the use of [http://srfi.schemers.org/srfi114/srfi114.html SRFI 114] comparators, which package a type test, an equality predicate, and a hash function into a single bundle. 30 29 31 30 32 === SRFI 69 compatibility === … … 128 130 === Constructors === 129 131 130 `(makehashtable `'' equality'' [ ''hash'' ] [ ''arg'' ... ]`)`131 132 Returns a newly allocated hash table whose equality predicate is ''equality'' andhash function is ''hash''. The equality predicate accepts two arguments and returns a truth value. The hash function accepts one argument in the domain of the equality predicate and returns a nonnegative exact integer. It is the programmer's responsibility to ensure that two objects passed to the hash function return the same value if the same objects passed to the equality predicate return true; however, the converse is not required.133 134 The ability to omit the ''hash'' argument is severely limited. If ''equality'' is `eq?`, `eqv?`, `equal?`, `string=?`, or `stringci=?`, then if ''hash'' is not provided, a suitable implementationprovided procedure will be used; the implementation may use its own procedure in any case. The implementation may extend this list. But if any other equality predicate is provided without a hash function, an error should be signaled.132 `(makehashtable `''comparator'' [ ''hash'' ] [ ''arg'' ... ]`)` 133 134 Returns a newly allocated hash table whose equality predicate and hash function are extracted from ''comparator''. If the argument is a procedure instead, it is assumed to be the equality predicate, and the hash function is ''hash''. The equality predicate accepts two arguments and returns a truth value. The hash function accepts one argument in the domain of the equality predicate and returns a nonnegative exact integer. It is the programmer's responsibility to ensure that two objects passed to the hash function return the same value if the same objects passed to the equality predicate return true; however, the converse is not required. 135 136 If a bare equality predicate rather than a comparator is provided, the ability to omit the ''hash'' argument is severely limited. If ''equality'' is `eq?`, `eqv?`, `equal?`, `string=?`, or `stringci=?`, then the implementation must provide a hash function, which it may use in any case. The implementation may extend this list. But if any other equality predicate is provided without a hash function, an error should be signaled. 135 137 136 138 The meaning of the remaining arguments is implementationdependent. However, implementations which support the ability to specify the initial capacity of a hash table should interpret a nonnegative exact integer as the specification of that capacity. In addition, if the symbols `immutable`, `threadsafe`, `weakkeys` or `weakvalues` are present, implementations should create immutable hash tables, mutable threadsafe hash tables, hash tables with weak keys, and hash tables with weak values respectively. In an implementation which does not support these features, an error should be signaled if they are requested. To avoid collision with the ''hash'' argument, none of these arguments can be procedures. … … 138 140 (SRFI 69 `makehashtable`; R6RS `makeeqhashtable`, `makeeqvhashtable`, and `makehashtable`; Common Lisp `makehashtable`) 139 141 140 `(hashtable `'' equality hash'' ( ''key value'' ) ...`)`141 142 Returns a newly allocated hash table, created as if by `makehashtable` , whose equality procedure is `equality` and hash function is `hash`. For each pair of arguments, an association is added to the new hash table with ''key'' as its key and ''value'' as its value.143 144 `(hashtableunfold `''continue? mapper successor seed equality'' [ ''hash'' ]`)`142 `(hashtable `''comparator'' ( ''key value'' ) ...`)` 143 144 Returns a newly allocated hash table, created as if by `makehashtable`. For each pair of arguments, an association is added to the new hash table with ''key'' as its key and ''value'' as its value. 145 146 `(hashtableunfold `''continue? mapper successor seed comparator'' [ ''hash'' ]`)` 145 147 146 148 Create a new hash table as if by `makehashtable`. If the result of applying the predicate ''continue?'' to ''seed'' is `#f`, return the hash table. Otherwise, apply the procedure ''mapper'' to ''seed''. ''Mapper'' returns two values, which are inserted into the hash table as the key and the value respectively. Then get a new seed by applying the procedure ''successor'' to ''seed'', and repeat this algorithm. … … 158 160 `(hashtable=? `''value= hashtable,,1,, hashtable,,2,,''`)` 159 161 160 Returns `#t` if ''hashtable,,1,,'' and ''hashtable,,2,,'' have the same size, the same keys (in the sense of their common equality predicate) and the same values (in the sense of the ''value='' predicate) for each key, and `#f` otherwise. It is an error to compare two hash tables that have distinct equality predicates.162 Returns `#t` if ''hashtable,,1,,'' and ''hashtable,,2,,'' have the same size, the same keys (in the sense of their common equality predicate) and the same values (in the sense of the ''value='' predicate) for each key, and `#f` otherwise. It is an error to compare two hash tables that have distinct comparators or distinct equality predicates. 161 163 162 164 === Accessors === … … 181 183 `(hashtableset! `''hashtable key value''`)` 182 184 183 Creates a new association in ''hashtable'' that associates ''key'' with ''value''. If there is a previous association for ''key'', it is deleted. It is an error if ''key'' is not a valid argument to the equality predicate of ''hashtable''. Returns an unspecified value. Must execute in expected amortized constant time. (SRFI 69 `hashtableset!`; R6RS `hashtableset!`)185 Creates a new association in ''hashtable'' that associates ''key'' with ''value''. If there is a previous association for ''key'', it is deleted. It is an error if the type check procedure of the comparator of ''hashtable'', when invoked on ''key'', does not return `#t`. Likewise, it is an error if ''key'' is not a valid argument to the equality predicate of ''hashtable''. Returns an unspecified value. Must execute in expected amortized constant time. (SRFI 69 `hashtableset!`; R6RS `hashtableset!`) 184 186 185 187 `(hashtablesetall! `''hashtable'' ( ''key value'' ) ...`)` … … 290 292 These procedures process the associations of the hash table in arbitrary order. 291 293 292 `(hashtablemap `'' equality hashproc merger hashtable''`)`294 `(hashtablemap `''comparator proc merger hashtable''`)` 293 295 294 296 Returns a newly allocated hash table as if by `makehashtable`. Calls ''proc'' for every association in ''hashtable'' with two arguments: the key of the association and the value of the association. The two values returned by ''proc'' are inserted into the new hash table as a key and value. … … 322 324 Returns an alist with the same associations as ''hashtable'' in an unspecified order. 323 325 324 `(alist>hashtable `''alist equalityhash''`)`326 `(alist>hashtable `''alist comparator hash''`)` 325 327 326 328 Returns a newly allocated hashtable as if by `makehashtable`, initializing it from the associations of ''alist''. (SRFI 69 `alist>hashtable`)