# [concurrency-interest] Problem with using an unbounded map of Mutex lock objects

Joe Bowbeer joe.bowbeer at gmail.com
Tue Jun 13 03:22:04 EDT 2006

```Correction:

I wrote:

> If the hash function is random, then I think the sums should be
> normally distributed, in which case a fairly wide distribution is
> likely.  (How unlikely is it that the sums all lie within +/- 20% of
> the mean?)
>
> The less normal the distribution, the less random the hash function,
> and the more likely it is that certain sets of data will amplify
> patterns inherent in the hash function, resulting in undesirable lock
> contention.
>

Scratch the bit about "normal distribution".  It's probably not true
and it just confuses the issue anyway.

The point I'm trying to make is that a random number generator will
not typically produce hit counts within +/- 20% of the mean in only
5000 trials, so I think it's unreasonable to expect a hash function to
do that well.

(Is there a statistician in the house?  With 128 buckets and 5000
random trials, how unlikely is it that the hit counts all lie within
+/- 20% of the mean?)

import java.security.SecureRandom;
import java.util.Random;
import java.util.SortedMap;
import java.util.TreeMap;

public class BucketTest {

public static final int NUM_BUCKETS = 128;
public static final int NUM_TRIALS = 5000;

public static void main(String[] args) {
Random rnd = new SecureRandom();
int[] bucket = new int[NUM_BUCKETS];
for (int n = NUM_TRIALS; --n >= 0; )
bucket[rnd.nextInt(bucket.length)]++;
int[] sum = new int[NUM_TRIALS];
for (int i = 0; i < bucket.length; i++)
sum[bucket[i]]++;
SortedMap<Integer, Integer> map =
new TreeMap<Integer, Integer>();
for (int i = 0; i < sum.length; i++)
if (sum[i] != 0)
map.put(i, sum[i]);
System.out.println(map);
double mean = (double) NUM_TRIALS / NUM_BUCKETS;
System.out.println(
((mean - map.firstKey()) * 100.0 / mean) + "% - " +
((map.lastKey() - mean)  * 100.0 / mean) + "%");
}
}

run:

hit counts: {20=1, 27=4, ... , 53=1, 56=1}

range: 48.8% - 43.36%

--Joe
```