Good Hash function? (32-bit too small, 64-bit too large)

I need to generate a hash value used for uniqueness of many billions of records in Java. Trouble is, I only have 16 numeric digits to play with. In researching this, I have found algorithms for 32-bit hash, which return Java integers. But this is too small, as it only has a range of +/ 2 billion, and have will have more records that that. I cannot go to a 64-bit hash, as that will give me numeric values back that are too large (+/ 4 quintillion, or 19 digits). Trouble is, I am dealin开发者_运维技巧g with a legacy system that is forcing me into a static key length of 16 digits.

Suggestions? I know no hash function will guarantee uniqueness, but I need a good one that will fit into these restrictions.

Thanks

If your generated hash is too large you can just mod it with your keyspace max to make it fit.

myhash = hash64bitvalue % 10^16

If you are limited to 16 decimal digits, your key space contains 10^16 values. Even if you find a hash that gives uniform distribution on your data set, due to Birthday Paradox you will have a 50% chance of collision on ~10^8 items of data, which is an order of magnitude less than your billions of records.

This means that you cannot use any kind of hash alone and rely on uniqueness.

A straightforward solution is to use a global counter instead. If global counter is infeasible, counters with preallocated ranges can be used. For example, 6 most significant digits denote fixed data source index, 10 least significant digits contain monotonous counter maintained by that data source.

So your restriction is 53 bit?

For my understanding order number of bit in hashcode doesn't affect its value (order and value of bit are fully independent from each other). So you could get 64-bit hash function and use only last 53 bits from it. And you must use binary operations for this ( hash64 & (1<<54 - 1) ) not arithmetic.

You don't have to store your hashes in a human readable form (hex, as you said). Just store the 64-bit long datatype (generated by a 64-bit hash function) in your database, which is only 8 bytes. And not the 19 bytes of which you were scared off.

If that isn't a solution, improve the legacy system.

Edit: Wait!

64-bit: 2⁶⁴ =

18446744073709551616

16 hex-digits: 16¹⁶ =

18446744073709551616

Exact fit! So make a hex representation of your 64-bit hash, and there you are.

If you can save 16 alphanumeric characters then you can use a hexadecimal representation and pack 16^16 bits into 16 chars. 16^16 is 2^64.