Variable range hash function for odd / simple buckets
Does anyone know of a hashing function (for strings, if it matters) for a range of variable codes that is always odd (or just if needed)?
Basically I'm looking for a hashing function that will distribute evenly across n buckets where n is odd (or simple, since n will be small).
Java .hashCode()
provides an even distribution, but only for powers of 2.
Here is some quick test code I whipped up that asserts this .
I cross this over to CS StoryExchange Theory as it seems to fall somewhere between theory and engineering.
source to share
Running your program with 37 as the bucket length and the hashing part replaced with
for (String key : keys) {
int hash = key.hashCode();
int index = Math.abs(hash % buckets.length);
buckets[index] = buckets[index] + 1;
}
leads to the following result:
Bucket 0: 4152
Bucket 1: 2593
Bucket 2: 2703
Bucket 3: 2620
Bucket 4: 2742
Bucket 5: 2647
Bucket 6: 2707
Bucket 7: 2673
Bucket 8: 2664
Bucket 9: 2685
Bucket 10: 2734
Bucket 11: 2708
Bucket 12: 2661
Bucket 13: 2678
Bucket 14: 2681
Bucket 15: 2662
Bucket 16: 2682
Bucket 17: 2667
Bucket 18: 2619
Bucket 19: 2572
Bucket 20: 2608
Bucket 21: 2669
Bucket 22: 2670
Bucket 23: 2629
Bucket 24: 2748
Bucket 25: 2651
Bucket 26: 2618
Bucket 27: 2628
Bucket 28: 2740
Bucket 29: 2608
Bucket 30: 2650
Bucket 31: 2645
Bucket 32: 2687
Bucket 33: 2699
Bucket 34: 2627
Bucket 35: 2715
Bucket 36: 2558
Mean: 2702.7027027027025
Standard Deviation: 245.8085241264752
which looks good.
You are not checking the distribution String.hashCode()
. You are testing a distribution if the HashMap method hash()
that uses the hashCode key and was designed to try to get a uniform distribution for its capacity, which SHOULD be power 2. If hashCode()
already returning well-distributed values, simply modulo using a prime number as the divisor. will lead to a good distribution.
source to share