6
$\begingroup$

From Wikipedia

A hash function is any algorithm or subroutine that maps large data sets of variable length, called keys, to smaller data sets of a fixed length. For example, a person's name, having a variable length, could be hashed to a single integer. The values returned by a hash function are called hash values, hash codes, hash sums, checksums or simply hashes.

I wonder if the range/codomain of a hash function is always the set of natural numbers or integers, because their function values seem to be always used as indices to some array?

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ Anything stored on a contemporary computer must be isomorphic to $\mathbb{N}$, no? It's all just binary. $\endgroup$
    – Xodarap
    Nov 15, 2012 at 18:53

5 Answers 5

Reset to default
6
$\begingroup$

In fact, there's an argument to be made that the 'range' of CRC-style hashes is not the integers (or naturals), but is in fact the field of polynomials over GF(2) modulo a primitive polynomial of degree $n$ (i.e., the field GF$(2^n)$). All of the operations are done on $n$-bit entities, but those entities are only 'numbers' in so much as that's the representation that's used for them; they don't add like numbers or multiply like numbers. While the final value returned to the user is interpreted and stored as a number, no arithmetic operations are generally performed on that value either; only indexing operations, which (for hopefully obvious reasons) require that the result be integer-convertible in some fashion.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ @Tim "Cyclic Redundancy Check" - a very basic form of error-correcting code that's sometimes used for hashing items like strings. See, for instance, en.wikipedia.org/wiki/Cyclic_redundancy_check for a description of the concept and basic algorithms. $\endgroup$
    – Steven Stadnicki
    Nov 18, 2012 at 19:22
6
$\begingroup$

Range of any hash function is a sub-set of natural numbers (this is how we think of it, exactly for access to the arrays, that could lie behind). The actual output of common hash-functions (MD5, SHAX...) is $n$ bits, where $n$ is $128$ for MD5 and $512$ for SHA2 with 80 rounds.

These bits can then be interpreted as natural numbers from interval $[0, 2^n-1]$. They can also be interpreted as integer from $[-2^{n-1},2^{n-1}]$. They can also be interpreted as "strings", although in essence they are only bits. What @Arani is talking about (I think) is probably conversion of this binary number to the hexadecimal format, and viewing it as string.

Improve this answer
$\endgroup$
4
$\begingroup$

It doesn't need to be. There is nothing about the structure of the hash function in general that requires that.

However it is more convenient to use natural numbers/strings. Computation over other objects are normally defined using an encoding of those objects by finite strings or natural numbers and there is not much lost in this conversion.

Improve this answer
$\endgroup$
3
$\begingroup$

It's quite commonly smaller than $\mathbb{N}$ or $\mathbb{Z}$, e.g. $\{-2^{31},...,2^{31}-1\}$ so as to fit in common number types.

Improve this answer
$\endgroup$
2
$\begingroup$

While hash function's outputs (especially cryptographic hash function outputs) are frequently used as strings in software engineering, this is because there exists a bijection between the set of possible strings and subset of N or Z. Thus, MD5, SHA1, SHA2 and SHA3 are all widely known hash functions whose outputs are frequently taken as strings.

Improve this answer
$\endgroup$
2
  • 6
    $\begingroup$ Are the ranges really string? Because these hash functions return binary numbers of length $n$. These numbers are then just transformed into hexadecimal format. $\endgroup$
    – Nejc
    Nov 15, 2012 at 15:10
  • $\begingroup$ @Nejc Yes, I agree with your answer, and I am modifying my answer accordingly. $\endgroup$
    – Arani
    Nov 15, 2012 at 18:46

Your Answer

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

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