CODEWITHSUNDEEP
algorithmhash
Vincent B.
Vincent B.

Reputation: 514

Hash a 17 char key into 4 bytes value

I have a colleague struggling with a hashing problem.

There is a 17-alphanumeric valued key (a VIN code) that needs to be converted into a 4 byte value (could be alphanumeric as well). Knowing that those 4 bytes will limit the number of keys, what perfect-hash algorithm would you see for this problem?

Upvotes: 1

Views: 1214

Answers (2)

Dante May Code
Dante May Code

Reputation: 11247

After a quick look at Wikipedia, I think you could first "compress" the key, or in other word, you do hash in 2 stages.

Stage 1: break down the key to individual parts according to the standard, and do customized hash independently.

Stage 2: Get hashes together, and do a normal hash.

An naive example:

If your data is limited to United States, there is only 27 possibility of the first 2 bytes, so the first 2 bytes can be hashed to 0 - 26. (Suppose we get a here.)

Then suppose other bytes have N possibilities, and can be hashed to 0 - N-1. (Suppose we get b here.)

The combinational result can be a * N + b. Then do a normal hash (if 26 * N > what 4 bytes can express).

Upvotes: 1

Vincent Cantin
Vincent Cantin

Reputation: 17262

You are talking about a Hash function, so it is ok to have f(x0) == f(x1) with x0 != x1.

A good hash function should have the hashed values homogeneously distributed. You can add the groups of 4 bytes which compose the 17-digit value together, and only keep the remaining 4 bytes with the lowest weight, for example.

Upvotes: 1

Related Questions