Why is equal-hash not implemented?

Created by Abdulaziz Ghuloum on on 2008-12-09
Keywords:
equal-hash

The procedure "equal-hash" from the (rnrs hashtables) library is not implemented in Ikarus and is unlikely to be implemented in the future. For hash functions to be useful in practice, they must satisfy two properties:
  1. Computing the hash value must be fast.
  2. The result must have a good distribution, and a small change to the input should yield large change in the computed value.

Unfortunately, for arbitrary objects of arbitrary sizes, there is no way to define a hash function that satisfies the above properties.

One may define a a "fast" hash function as follows:
  (define (equal-hash x) 0)
This function conforms with the requirements of R6RS. It is also fast. However, it's not useful as a hash function. Users are better off using association lists and assoc than using this conforming implementation of equal-hash.

One may also define a "good" hash function as follows:
  (define (equal-hash x)
    (string-hash (with-output-to-string (lambda () (write x)))))
This function also conforms to the requirements of R6RS. It produces good distribution since the whole object contributes to the hash value. However, it is slow. Again, using association lists probably yields faster result for most cases.

Users may know more about the layout of their data, and may be able to produce better hash functions that are customized for their particular needs. This is better than depending on a general-purpose equal-hash function whose run-time behavior and value-distribution are unpredictable and can vary greatly from one implementation of R6RS to the next or from one release to the next.

Users who thinks that one of the two listed functions is satisfactory for their purpose can include it in their programs.