5.7 Custom Comparison and Hash Functions ¶

I firmly believe that associating comparison and hashing functions with each type, by defining methods for that type on compare and (for CHAMP) hash-value, suffices for the vast majority of use cases. But there are occasional situations when it might be preferable, when creating a collection, to supply alternative comparison and (when relevant) hashing functions for it to use. (I refer to the comparison and hashing functions used by a collection as the organization of the collection.)

• In extremely performance-sensitive situations, when the time required for the actual comparison or hash computation is very small, it is possible for the generic function dispatch time to become relatively significant. The extreme case would be a WB-set of fixnums; comparing two fixnums takes just a few instructions. The WB-tree collections, on a lookup, call the comparison function several times (the number of calls is slightly more than log₂ of the size of the set), so the generic function dispatch can make a noticeable difference for them. (In contrast, lookup on a CHAMP collection calls the hash function once, and the comparison function at most once.) In such cases, you may wish to provide a custom comparison function.
• Sometimes you want to maintain a collection in a specific order as it gets updated. A common example is a dictionary of words, which you want to keep in lexicographic order instead of always putting shorter words before longer ones, as compare does. The WB-tree collections with a custom comparison function will do this for you.

As mentioned above, complete hashing of a large object, such as a deeply nested s-expression, takes time linear in the size of the object. The time cost could be significant, but unless the structures tend to differ only at the ends or leaves, there might be little benefit to hashing the whole thing; a bounded hash that restricts the number of elements considered might work just as well, in the sense of preventing hash collisions, yet be much cheaper to compute.

If you’re defining a comparison function and hash function to use with CHAMP collections, there are two requirements:

• They must be mutually consistent: for any pair of objects on which the comparison function returns :equal or :unequal, the hash function must return the same value on both objects.
• You must tell FSet to use the hash function together with the comparison function by calling define-hash-function. This is because the API functions and macros to create a collection with a custom organization always take only the comparison function name; the hash function is implicit.

Macro: define-hash-function compare-fn-name hash-fn-name ¶

Establishes that hash-based collections that are created using the named comparison function should use the specified hashing function also.

Once you’ve written a custom comparison function, and for CHAMP, associated a custom hashing function with it, you can supply the comparison function’s name to various constructor functions and macros; for details, see FSet API Reference. For sets and bags, a single comparison function is required; for maps and binary relations, two are needed, one for keys (domain elements) and the other for values (range elements). In all cases, they are specified as function names, i.e., symbols, rather than CL function objects; this is so they can be printed out in a reasonable way.

FSet assumes that any two objects that are eql also compare :equal. Be sure not to use eq to compare characters or numbers.

As mentioned above, all elements of a set or bag are candidates for comparison or hashing, as are all keys of a map. So you need to make sure that any custom compare or hash functions you supply for a collection can accept all its elements or keys.

If a comparison function ever returns :unequal, then it must, as the first thing it does, call fset2:unwrap-equivalent-node on each parameter and substitute the result for the original value of the parameter. For instance:

(defun my-compare (a b)
  (let ((a (fset2:unwrap-equivalent-node a))
	(b (fset2:unwrap-equivalent-node b)))
    ...))

• Strict Weak Orderings
• Non-FSet Collections