0
$\begingroup$

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

$\endgroup$
7
  • 2
    $\begingroup$ Not every informal concept has a standard formal definition. $\endgroup$ – Yuval Filmus Apr 10 '20 at 10:20
  • 2
    $\begingroup$ I'm not sure why you require your function to be surjective. $\endgroup$ – Yuval Filmus Apr 10 '20 at 10:21
  • $\begingroup$ 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? $\endgroup$ – user8469759 Apr 10 '20 at 10:29
  • 2
    $\begingroup$ It is quite common to find hash functions whose output is a bitstring. $\endgroup$ – Yuval Filmus Apr 10 '20 at 10:36
  • 1
    $\begingroup$ That said, in cryptography there are formal definitions of hash functions. But that's not what you're after. $\endgroup$ – Yuval Filmus Apr 10 '20 at 12:42
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ So the image set is actually integers by definition, right? Any reference? $\endgroup$ – user8469759 Apr 13 '20 at 11:56
  • $\begingroup$ @user8469759, see how it is used. $\endgroup$ – vonbrand Apr 13 '20 at 17:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.