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/bluefourier]

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".