CODEWITHSUNDEEP
c#hashinteger
David Pfeffer
David Pfeffer

Reputation: 39852

Hash sequential 64 bit number uniformly into 8 bits?

I'm looking for a hash algorithm, that when given a 64 bit sequential value, will hash to 8 bits uniformly.

I don't want to just use the least-significant byte as the hash value.

Upvotes: 3

Views: 1090

Answers (2)

user418938
user418938

Reputation:

As a general case of Oli Charlesworth's solution, you can select coprime with 256 and pre-multiply each byte from your input by that value and then XOR all values together. You'll still get uniform distribution, but for sequential inputs you'll get non-sequential output, for instance:

byte result = 0;
int q = 33149;
foreach (byte b in BitConverter.GetBytes(input)) result += (byte)(b * q);

For 1, 2, 3, 4, 5, 6, ... it will get you 125, 250, 119, 244, 113, 238, etc

Upvotes: 4

Oliver Charlesworth
Oliver Charlesworth

Reputation: 272647

Lacking any further information or constraints, one possibility is just to bitwise-XOR all of the 8 bytes together. This will be uniform for a uniform input.

My C# is rusty, but in pseudocode:

byte hash = 0;
for (int i = 0; i < 8; i++) {
    hash ^= (byte)(val >> (i*8));
}

Upvotes: 2

Related Questions