Create a commutative hash based on three sets of numbers?
I need to create a commutative hash based on three sets of evaluation structures.
Each point has a "start", "end" and "number".
Both beginnings and ends are usually huge numbers (8-9 digits), but a number between 1 and 4.
I need them to be commutative, so the order doesn't matter. I am using XOR at the moment, but it seems to be giving bad results.
Since I work with large large datasets, I would prefer a performance-friendly solution. Any suggestions? Thank you =]
public static int getCustomHash(cnvRegion c1, cnvRegion c2, cnvRegion c3)
{
int part1 = (c1.startLocation * c2.startLocation * c3.startLocation);
int part2 = (c1.endLocation * c2.endLocation * c3.endLocation);
int part3 = (c1.copyNumber + c2.copyNumber + c3.copyNumber)*23735160;
return part1 ^ part2 ^ part3;
}
source to share
Thomas Wang discusses hash functions here .
- See knuth method and 64 to 32 bit mixing functions.
Paul Hsieh also has a whole hashing page that describes his "SuperFastHash" function, which has received mixed feedback.
EDIT
Since you want your custom hash to be commutative (I'm assuming between cnvRegion options), you could write something like this:
public int hash6432shift(long key)
{
key = (~key) + (key << 18); // key = (key << 18) - key - 1;
key = key ^ (key >>> 31);
key = key * 21; // key = (key + (key << 2)) + (key << 4);
key = key ^ (key >>> 11);
key = key + (key << 6);
key = key ^ (key >>> 22);
return (int) key;
}
public static int getCustomHash(cnvRegion c1, cnvRegion c2, cnvRegion c3)
{
int part1 = (c1.startLocation ^ c2.startLocation ^ c3.startLocation);
int part2 = (c1.endLocation ^ c2.endLocation ^ c3.endLocation);
int part3 = (c1.copyNumber ^ c2.copyNumber ^ c3.copyNumber);
int hash1 = hash6432shift(((long)part1 << 0x20) | part2);
return hash6432shift(((long)hash1 << 0x20) | part3);
}
Ultimately, however, the task of finding a hash function that is fast and provides good collision resistance is highly dependent on the data you are processing.
Let me give you an example:
Let's say that the values you are hashing are large ten-digit numbers and they represent a UNIX timestamp (time elapsed in seconds since 01/01/1970). In this case, hashing multiple timestamps that occur over a limited amount of time - for example, within a month - is simply a matter of eliminating the part that doesn't change and using only the part of the timestamp that changes a lot. This is the same as saying that you are eliminating areas of low entropy.
v1 = 1241536920 // 5/5/2009 3:22:00 PM
v2 = 1241529720 // 5/5/2009 1:22:00 PM
v3 = 1241270520 // 5/2/2009 1:22:00 PM
v4 = 1242825720 // 5/20/2009 1:22:00 PM
It's pretty clear that we could safely eliminate the first 3-4 digits and use the remaining digits as a hash. Also, if these values usually happen within a few minutes of each other, you can also delete the last 2-3 digits.
This leaves you with only 4 digits that you can use as a hash with pretty good collision resistance for our example.
My point is that hash functions can be highly optimized if you know the statistical distribution of the values you are trying to use the hash for.
source to share
First, I think the requirements are not entirely clear. If you are using three datasets c1, c2 and c3. Then, if you include again, c1.copyNumber and c2.copyNumber and hash. Should this give the same result or not? If you switch c1.startLocation using c1.endLocation. Should this result in the same hash or not?
I am assuming that you would like to have different hash results in both cases and that the only permutation that should not change the hash result is permutations of datasets c1, c2, c3.
If so, I would suggest the hash of the three datasets first, regardless of the smaller values. That is, h1 = H (c1) h2 = H (c2) h3 = H (c3) where H can be any hash function (like CRC32, Adler32, SHA1, etc.) depending on how hard you want to avoid collisions.
The next step is to calculate the commutative hash h1, h2, h3. If you want to avoid collisions, if h1, h2, h3 are rearranged, then the following works. Calculate polynomial
- P (x) = (x-h1) (x-h2) (x-h3)
then a hash polynomial (rsp. its coefficients) with any good hash function. That is what will be
- H (h1 + h2 + h3 || h1 * h2 + h1 * h3 + h2 * h3 || h1 * h2 * h3), where || is a concatenation.
If you want to avoid any unnecessary collision at all costs, then the coefficients must be computed as integers with integer points, and a collision-resistant hash function such as SHA1 should be used. Due to the unique property of factorization of polynomials if, it follows that the coefficients of the polynomial are different if h1, h2 and h3 are different. But it seems that avoiding collisions at all costs is overkill in your case.
Thus, instead of just calculating the polynomial P (x), one could simply evaluate it for an arbitrary value of RIe if h1, h2, h3 are only 32-bit values, then calculating the following might be sufficient: (the following appears pseudocode like C. I don't know what C # uses for 64-bit integers)
const long long R = SOME_RANDOM_64_BIT_CONSTANT;
long long hash0 = (R - h1) * (R - h2) * (R - h3);
int hash = (int) (hash0 >> 32);
I use 64-bit multiplication because they are fast enough on modern processors, and I use the upper 32-bit hash code rather than the lower 32-bit, since the lower 32 bits are somewhat biased. Ie, the least significant bit is much more likely 0 than 1.
source to share