ハッシュテーブル内の衝突の数を一連の値から数えるにはどうすればよいですか？

Question

数値のセットとハッシュテーブルのサイズを指定した場合、どのようにして衝突数をシミュレートできますか？

Answer 1

セット内の数値のハッシュ値を計算し、重複したハッシュ値の数を数えます。この

単純な実装は次のようになります。

List<Integer> yourValues = /* Your set of numbers */; 
Map<Integer, Set<Integer>> map = new HashMap<>(); 
// Insert all elements into buckets based on their hash value 
yourValues.forEach(value -> { 
    if (!map.containsKey(value.hashCode())) 
     map.put(value.hashCode(), new HashSet<>()); 
    map.get(value.hashCode()).add(value); 
}); 
// Sum up the number of values in each bucket, subtract the number of buckets, so only duplicate values are counted 
int collisions = map.values().stream().map(Set::size).reduce(0, Integer::sum) - map.size(); 
System.out.printf("Number of collisions: %d\n", collisions);