What is the best implementation of hashCode integer?

Question

I created several hashCode implementations of an integer for use in hashTable, but none of them apparently closed the uniform distribution. So, what would be the best implementation of hashCode for an integer assuming a hash table size of about a hundred, and integers of the order of several thousand? Thanks in advance.

Answer 1

I suggest a “better” implementation, whatever that means, almost certainly

Integer.valueOf(value).hashCode() 

Answer 2

Since your hash table is quite small, the modular function will be the easiest implementation, and if the input numbers are random, the distribution should be random too.

 public int hashCode(int x){ return x%tableSize; } 

the best implementation would be to use multiplication as described here .

 (x*someNumber) % table size; 

Other hash functions are described here , check them out. Hope this helps.

Answer 3

If the keys of your data are evenly distributed, just use the integer as the key. If your keys are not evenly distributed, you need to change the integer so that its distribution is more even across the spectrum of all integers. How to do this depends on how your keys are distributed and the exact implementation of the card.

Are you sure you are not doing premature optimization? On a map with only 100 entries, this really doesn't really matter if you have a constant search time (well-distributed) or linear search time (each entry has a key collision). Iterating over 100 points is so fast; outside of benchmarking, you probably won't notice the difference. It would be interesting to evaluate if the list would not be faster on average than a map with such a small data set.

Answer 4

Thus, you have thousands of values ​​along the X axis and you want to "convert" them to a much smaller range, hundreds, along the Y axis. Obviously, you can divide by 10 or get a module, but you also want to distribute them as much as possible homogeneous in the target range.

I think you need a compression function.

You can, for example, apply a sine function to an input and multiply by the size of the hash table. What value should the period have? It depends: the closer you expect the input values, the higher the period (so two close values ​​will give two very different results). And vice versa: if the input values ​​are not expected very close, a short period may occur.

 private int hashCode(int input, int tableSize) { return (int)(tableSize*Math.sin(PERIOD*input)); } 

Answer 5

MurmurHash3 completion avalanche function:

 int h = key; h ^= h >>> 16; h *= 0x85ebca6b; h ^= h >>> 13; h *= 0xc2b2ae35; h ^= h >>> 16;