# Is the codomain/range of a hash function always $\mathbb{Z}$ or $\mathbb{N}$?

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?

-
Anything stored on a contemporary computer must be isomorphic to $\mathbb{N}$, no? It's all just binary. –  Xodarap Nov 15 '12 at 18:53

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.

-
Thanks! What is " CRC"? –  Tim Nov 18 '12 at 18:11
@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. –  Steven Stadnicki Nov 18 '12 at 19:22

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.

-

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.

-

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.

-

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.

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