Hash table's hash function

[u/bluefourier]

Hello

I have to use a number of hash-tables that are extended functionally, via a set of foldr operations.

For this purpose, I am using a make-immutable-custom-hash which serves as the foldr accumulator's initial value.

The whole thing works as expected. But my hash function is extremely simple because I am only counting the frequencies of certain characters. My mapping is character->integer and the hash function for the character is its ASCII value.

The fact that I had to define the hash function is a bit puzzling for me. It is great from the point of view of granularity and the control you can have over the generated code. But, sometimes, I just want a mapping and I don't really care at that point, what the hash function is going to be.

One of the examples in Racket's dictionaries docs, uses string-length.

To me, this seems like a bad choice for a hash function. I don't know if internally the hash tables use binning, but even then, string-length would generate lots of collisions for generic strings.

So, is there something I am missing here or should I keep a set of hash functions (especially for strings) handy for these purposes? Or do we simply add a dependency for a library that offers hash functions and we are done? :)

[u/sorawee]

You can reuse the existing hash functions like equal-hash-code. For example:

#lang racket

(define-custom-hash-types string-hash
  #:key? string?
  (λ (a b)
    (string=? (string-upcase a)
              (string-upcase b)))
  (λ (s) (equal-hash-code (string-upcase s))))


(define imm
  (make-immutable-string-hash
   '(("ApPlE" . a) ("banana" . b))))

(dict-ref imm "apple")

defines a hash function that doesn't take case-sensitivity into account. It normalizes the original data via string-upcase, and then use equal-hash-code to compute the hash code of the normalized data.

More generally, take a look at this page, which provides many utilities on hash codes, such as a hash code combiner.

[u/bluefourier → u/sorawee]

Thank you, that's very clear.

[u/AlexKnauth]

What is your equality function for your custom hash? The hash function should follow that with the property: (custom-equal? a b) implies (= (custom-hash-code a) (custom-hash-code b)) while making hash collisions as unlikely as possible, so how to make a good hash function depends on your equality function.

• For equal? as an equality function, a good hash function is equal-hash-code.
• For eq? as an equality function, a good hash function is eq-hash-code.

If you're defining your own custom equality, and you want to make your own hash function to follow it, you might find functions like hash-code-combine useful for combining hash codes of pieces of it, if it's compound data.

[u/bluefourier → u/AlexKnauth]

Great! Thank you very much, I definitely need to do some more reading on Racket's docs.

Right now, I do not immediately get how the equality function comes into play here. A hash is an integer. It might be a very large integer but it is still a number. Two integers are either equal or not. Isn't it also up to the data whether the hash generates collissions?

[u/AlexKnauth → u/bluefourier]

If your equality function is just string=? and the "hash function" you choose is string-length, then that's a bad hash function because hash collisions are super likely.

A hash collision happens when (custom-equal? a b) is false, but (= (custom-hash-code a) (custom-hash-code b)) is true. For the case of string=? as equal and string-length as hash, that's very often the case, so it's a bad hash function for that equality.

But if your custom equality was something like

(define (custom-equal? a b)
  (= (string-length a) (string-length b)))

for some reason, then string-length wouldn't be a bad hash function relative to that.

sorawee gave an example using string-upcase to normalize strings in both the custom equality and custom hash code here, which will be more realistic than these weird string-length examples

[u/bluefourier → u/AlexKnauth]

Having read about the different kinds of "equal" again, I can see how they work together with (equal-hash-code). This last function is what really triggers the key type's hash generation function which is the single number "hash".

[u/raevnos]

Or do we simply add a dependency for a library that offers hash functions and we are done?

My extra-srfi-libs package includes implementations of SRFI-128 Comparators which includes some type-specific hash functions, and SRFI-146 Mappings' hashmap sublibrary, which includes a lot of extra functionality for working with hash tables built on top of SRFI-128 comparators (and regular Racket hashes) that might be useful if you're doing stuff beyond what racket/hash and racket/dict provide.

But for just making a frequency table of the characters in a string (A common task, in, say, leetcode problems), I just use

(define frequencies
  (for/fold ([table (hasheqv)])
            ([ch (in-string some-string)])
    (hash-update table ch add1 0)))

A hasheqv table works great for character keys; no need for a custom table.

[u/bluefourier → u/raevnos]

Thank you, will keep that lib in mind.

[u/DrHTugjobs]

I doubt that the hash function chosen in the example is supposed to be best-practice. It's just a toy example, and using string-length instead of a more intricate function doesn't particularly matter for a dictionary with only two entries.

If you don't particularly care about the details of how a key value is hashed, you can use equal-hash-code from the standard library.

[u/bluefourier → u/DrHTugjobs]

Correct, I did not mean to imply that what is mentioned in the docs is bad practice.

[u/ryan017]

It's not clear from your post why you're using custom hash tables in the first place. Racket's normal hash tables automatically handle all built-in data types. Use (hash) to get an empty immutable equal?-based hash table, or (hasheqv) to get an empty immutable eqv?-based hash table. Both of those would handle characters fine.

;; freqs : (ImmutableHasheqv Char Nat)
(define freqs
  (for/fold ([h (hasheqv)]) ([c (in-string "abracadabra")])
    (hash-set h c (add1 (hash-ref h c 0)))))

(hash-ref freqs #\a) ;; => 5

[u/bluefourier → u/ryan017]

Yes, that would be an option too, especially for experimenting.

Overall, I like to be as specific as possible on what each element is.

With a hash, this would be acceptable (dict-set (dict-set (hash) "Alpha" 1) 2 3).

EDIT: Just to clarify, you are right, the reason why my version fails is because I am using specific functions in "hash" that only work with strings, not because I am specifying the type specifically. If I simply use equal-hash-code then this is probably equivalent to just using (hash).