Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
2  
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
add comment

5 Answers

up vote 6 down vote accepted

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.

share|improve this answer
    
Thanks! What is " CRC"? –  Tim Nov 18 '12 at 18:11
1  
@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
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
6  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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