1. srfi-69
    1. Hash Table Procedures
      1. make-hash-table
      2. alist->hash-table
      3. hash-table?
      4. hash-table-size
      5. hash-table-equivalence-function
      6. hash-table-hash-function
      7. hash-table-min-load
      8. hash-table-max-load
      9. hash-table-weak-keys
      10. hash-table-weak-values
      11. hash-table-has-initial?
      12. hash-table-initial
      13. hash-table-keys
      14. hash-table-values
      15. hash-table->alist
      16. hash-table-ref
      17. hash-table-ref/default
      18. hash-table-exists?
      19. hash-table-set!
      20. hash-table-update!
      21. hash-table-update!/default
      22. hash-table-copy
      23. hash-table-delete!
      24. hash-table-remove!
      25. hash-table-clear!
      26. hash-table-merge
      27. hash-table-merge!
      28. hash-table-map
      29. hash-table-fold
      30. hash-table-for-each
      31. hash-table-walk
    2. Hashing Functions
      1. number-hash
      2. object-uid-hash
      3. symbol-hash
      4. keyword-hash
      5. string-hash
      6. string-ci-hash
      7. eq?-hash
      8. eqv?-hash
      9. equal?-hash
      10. hash
      11. hash-by-identity
      12. recursive-hash-max-depth
      13. recursive-hash-max-length
    3. Author
    4. License
    5. Version History

srfi-69

An implementation of SRFI 69 with SRFI 90 extensions. For more information, see SRFI-69 and SRFI-90. A straightforward implementation of binary search.

Hash Table Procedures

make-hash-table

[procedure] (make-hash-table [TEST HASH SIZE] [#:test TEST] [#:hash HASH] [#:size SIZE] [#:initial INITIAL] [#:min-load MIN-LOAD] [#:max-load MAX-LOAD] [#:weak-keys WEAK-KEYS] [#:weak-values WEAK-VALUES])

Returns a new HASH-TABLE with the supplied configuration.

TEST
The equivalence function.
HASH
The hash function.
SIZE
The expected number of table elements.
INITIAL
The default initial value.
MIN-LOAD
The minimum load factor. A flonum in (0.0 1.0).
MAX-LOAD
The maximum load factor. A flonum in (0.0 1.0).
WEAK-KEYS
Use weak references for keys. (Ignored)
WEAK-VALUES
Use weak references for values. (Ignored)

Please note that hash tables are not guaranteed to compare equal? to each other, even if they contain exactly the same key/value pairs.

alist->hash-table

[procedure] (alist->hash-table A-LIST [#:test TEST] [#:hash HASH] [#:size SIZE] [#:initial INITIAL] [#:min-load MIN-LOAD] [#:max-load MAX-LOAD] [#:weak-keys WEAK-KEYS] [#:weak-values WEAK-VALUES])

Returns a new HASH-TABLE. The HASH-TABLE is populated from the A-LIST. The keyword arguments are per make-hash-table.

If a key occurs multiple times in A-LIST, the first occurrence will be used in the hash table.

hash-table?

[procedure] (hash-table? OBJECT)

Is the OBJECT a hash-table?

hash-table-size

[procedure] (hash-table-size HASH-TABLE)

The HASH-TABLE size.

hash-table-equivalence-function

[procedure] (hash-table-equivalence-function HASH-TABLE)

The HASH-TABLE equivalence-function.

hash-table-hash-function

[procedure] (hash-table-hash-function HASH-TABLE)

The HASH-TABLE hash-function.

hash-table-min-load

[procedure] (hash-table-min-load HASH-TABLE)

The HASH-TABLE minimum load factor.

hash-table-max-load

[procedure] (hash-table-max-load HASH-TABLE)

The HASH-TABLE maximum load factor.

hash-table-weak-keys

[procedure] (hash-table-weak-keys HASH-TABLE)

Does the HASH-TABLE use weak references for keys?

hash-table-weak-values

[procedure] (hash-table-weak-values HASH-TABLE)

Does the HASH-TABLE use weak references for values?

hash-table-has-initial?

[procedure] (hash-table-has-initial? HASH-TABLE)

Does the HASH-TABLE have a default initial value?

hash-table-initial

[procedure] (hash-table-initial HASH-TABLE)

The HASH-TABLE default initial value.

hash-table-keys

[procedure] (hash-table-keys HASH-TABLE)

Returns a list of the keys in the HASH-TABLE population.

hash-table-values

[procedure] (hash-table-values HASH-TABLE)

Returns a list of the values in the HASH-TABLE population.

hash-table->alist

[procedure] (hash-table->alist HASH-TABLE)

Returns the population of the HASH-TABLE as an a-list.

hash-table-ref

[procedure] (hash-table-ref HASH-TABLE KEY)

Returns the VALUE for the KEY in the HASH-TABLE.

Aborts with an exception when the KEY is missing.

hash-table-ref/default

[procedure] (hash-table-ref/default HASH-TABLE KEY DEFAULT)

Returns the VALUE for the KEY in the HASH-TABLE, or the DEFAULT when the KEY is missing.

hash-table-exists?

[procedure] (hash-table-exists? HASH-TABLE KEY)

Does the KEY exist in the HASH-TABLE?

hash-table-set!

[procedure] (hash-table-set! HASH-TABLE KEY VALUE)

Set the VALUE for the KEY in the HASH-TABLE.

A setter for hash-table-ref is defined, so

(set! (hash-table-ref HASH-TABLE KEY) VALUE)

is equivalent to

(hash-table-set! HASH-TABLE KEY VALUE)

hash-table-update!

[procedure] (hash-table-update! HASH-TABLE KEY [UPDATE-FUNCTION [DEFAULT-VALUE-FUNCTION]])

Sets or replaces the VALUE for KEY in the HASH-TABLE.

The UPDATE-FUNCTION takes the existing VALUE for KEY and returns the new VALUE. The default is identity

The DEFAULT-VALUE-FUNCTION is called when the entry for KEY is missing. The default uses the (hash-table-initial-value), if provided. Otherwise aborts with an exception.

Returns the new VALUE.

hash-table-update!/default

[procedure] (hash-table-update!/default HASH-TABLE KEY UPDATE-FUNCTION DEFAULT-VALUE)

Sets or replaces the VALUE for KEY in the HASH-TABLE.

The UPDATE-FUNCTION takes the existing VALUE for KEY and returns the new VALUE.

The DEFAULT-VALUE is used when the entry for KEY is missing.

Returns the new VALUE.

hash-table-copy

[procedure] (hash-table-copy HASH-TABLE)

Returns a shallow copy of the HASH-TABLE.

hash-table-delete!

[procedure] (hash-table-delete! HASH-TABLE KEY)

Deletes the entry for KEY in the HASH-TABLE.

hash-table-remove!

[procedure] (hash-table-remove! HASH-TABLE PROC)

Calls PROC for all entries in HASH-TABLE with the key and value of each entry. If PROC returns true, then that entry is removed.

hash-table-clear!

[procedure] (hash-table-clear! HASH-TABLE)

Deletes all entries in HASH-TABLE.

hash-table-merge

[procedure] (hash-table-merge HASH-TABLE-1 HASH-TABLE-2)

Returns a new HASH-TABLE with the union of HASH-TABLE-1 and HASH-TABLE-2. Keys that exist in both tables will be taken from HASH-TABLE-1.

hash-table-merge!

[procedure] (hash-table-merge! HASH-TABLE-1 HASH-TABLE-2)

Returns HASH-TABLE-1 as the union of HASH-TABLE-1 and HASH-TABLE-2. Keys that exist in both tables will be taken from HASH-TABLE-1.

hash-table-map

[procedure] (hash-table-map HASH-TABLE FUNC)

Calls FUNC for all entries in HASH-TABLE with the key and value of each entry.

Returns a list of the results of each call.

hash-table-fold

[procedure] (hash-table-fold HASH-TABLE FUNC INIT)

Calls FUNC for all entries in HASH-TABLE with the key and value of each entry, and the current folded value. The initial folded value is INIT.

Returns the final folded value.

hash-table-for-each

[procedure] (hash-table-for-each HASH-TABLE PROC)

Calls PROC for all entries in HASH-TABLE with the key and value of each entry.

hash-table-walk

[procedure] (hash-table-walk HASH-TABLE PROC)

Calls PROC for all entries in HASH-TABLE with the key and value of each entry.

Hashing Functions

All hash functions return a fixnum in the range [0 BOUND).

When given the fixnum RANDOMIZATION, these functions will use this to perturb the value; if not specified, the value will differ for each invocation of your program. This is for security reasons; an attacker who knows what a value hashes to can deliberately try to cause collisions, thereby flattening your hash table, effectively reducing it to a list. Always make sure you don't expose any hashed value to an attacker.

number-hash

[procedure] (number-hash NUMBER [BOUND RANDOMIZATION])

For use with = as a hash-table-equivalence-function.

object-uid-hash

[procedure] (object-uid-hash OBJECT [BOUND RANDOMIZATION])

Currently a synonym for equal?-hash.

symbol-hash

[procedure] (symbol-hash SYMBOL [BOUND RANDOMIZATION])

For use with eq? as a hash-table-equivalence-function.

keyword-hash

[procedure] (keyword-hash KEYWORD [BOUND RANDOMIZATION])

For use with eq? as a hash-table-equivalence-function.

string-hash

[procedure] (string-hash STRING [BOUND START END RANDOMIZATION])

For use with string=? as a hash-table-equivalence-function. The optional START and END arguments may be given to limit the hash calculation to a specific sub-section of STRING.

string-ci-hash

[procedure] (string-hash-ci STRING [BOUND START END RANDOMIZATION])
[procedure] (string-ci-hash STRING [BOUND START END RANDOMIZATION])

For use with string-ci=? as a hash-table-equivalence-function.

eq?-hash

[procedure] (eq?-hash OBJECT [BOUND RANDOMIZATION])

For use with eq? as a hash-table-equivalence-function.

eqv?-hash

[procedure] (eqv?-hash OBJECT [BOUND RANDOMIZATION])

For use with eqv? as a hash-table-equivalence-function.

equal?-hash

[procedure] (equal?-hash OBJECT [BOUND RANDOMIZATION])

For use with equal? as a hash-table-equivalence-function.

hash

[procedure] (hash OBJECT [BOUND RANDOMIZATION])

Synonym for equal?-hash.

hash-by-identity

[procedure] (hash-by-identity OBJECT [BOUND RANDOMIZATION])

Synonym for eq?-hash.

recursive-hash-max-depth

[parameter] (recursive-hash-max-depth)

The maximum structure depth to follow when computing a hash value. The default is 4.

recursive-hash-max-length

[parameter] (recursive-hash-max-length)

The maximum vector length to follow when computing a hash value. The default is 4.

Author

Original implementation by Felix, then heavily extended by Kon Lovett, now maintained by The CHICKEN Team.

License

Copyright (c) 2008-2014, The Chicken Team
Copyright (c) 2000-2007, Felix L. Winkelmann
All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions
are met:
1. Redistributions of source code must retain the above copyright
   notice, this list of conditions and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright
   notice, this list of conditions and the following disclaimer in the
   documentation and/or other materials provided with the distribution.
3. The name of the authors may not be used to endorse or promote products
   derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE AUTHORS ``AS IS'' AND ANY EXPRESS OR
IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY DIRECT, INDIRECT,
INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 

Version History

0.3
Fix hashing of extended numerics (non-flonum, non-fixnum, see #1521).
0.2
Compile with similar performance options as in CHICKEN 4.
0.1
Taken from the srfi-69 core library unit and released as an egg.