# Formal definition of hash function

I was reading through the classic CLRS with the intention of reviewing the hash tables theory, more specifically the hash function definition I just wanted a reference to quote.

I cannot find a formal definition given but I think it's fair to say a hash function (not univerisal) $$h$$ is a surjective map from a set of keys $$K$$ to a subset of integers $$U$$, for each $$k \in K$$ we define $$h(k)$$ to be the hash value of $$k$$. From the explanation given in CLRS it seems though this restriction on $$U$$ (be integers) might be too restrictive, however since I think the definition has to show some practical aspects I think this might be correct.

Can you either give me: 1. A paper/book with a formal definition 2. Confirm if my definition is correct?

Thank you

• Not every informal concept has a standard formal definition. – Yuval Filmus Apr 10 '20 at 10:20
• I'm not sure why you require your function to be surjective. – Yuval Filmus Apr 10 '20 at 10:21
• I probably don't need surjection, since you have the notion of uniform hash. So a non uniform might imply you don't hit every value in the image space. So no formal definition then? Are there examples of hash functions whose values are not integers? – user8469759 Apr 10 '20 at 10:29
• It is quite common to find hash functions whose output is a bitstring. – Yuval Filmus Apr 10 '20 at 10:36
• That said, in cryptography there are formal definitions of hash functions. But that's not what you're after. – Yuval Filmus Apr 10 '20 at 12:42

A hash function is used to map a set of keys to a subrange of the integers (it is used as an index into an array, in the end). So it must be (assuming zero based arrays, as in C), $$h \colon \mathcal{U} \to [0, m - 1]$$ if $$\mathcal{U}$$ is the universe of keys.