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

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ Not every informal concept has a standard formal definition. $\endgroup$
    – Yuval Filmus
    Commented Apr 10, 2020 at 10:20
  • 2
    $\begingroup$ I'm not sure why you require your function to be surjective. $\endgroup$
    – Yuval Filmus
    Commented Apr 10, 2020 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
    Commented Apr 10, 2020 at 10:29
  • 2
    $\begingroup$ It is quite common to find hash functions whose output is a bitstring. $\endgroup$
    – Yuval Filmus
    Commented Apr 10, 2020 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
    Commented Apr 10, 2020 at 12:42

1 Answer 1

Reset to default
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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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