[Solved]: Is the codomain/range of a hash function always $\mathbb{Z}$ or $\mathbb{N}$?

Problem Detail: 

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?

Asked By : Tim

Answered By : Steven Stadnicki

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/6680

3.2K people like this

 Download Related Notes/Documents