java - 查找所有散列到相同散列值的 n 个键

Question

给出的哈希函数:

public int hash4(int k) {
    Random rand = new Random(k);
    return rand.nextInt(size);
}

目标是找到使用此哈希函数哈希到相同哈希值(导致冲突)的 n(size) 个键 (k)。 Size 是一个由用户传入的常量，大小永远不会大于 1000。键的最大值是 n^2，并且您不能一遍又一遍地使用相同的键。任何帮助将不胜感激!

我尝试解决这个问题，使用数字 1-n 作为键从 1 到 n 循环，寻找模式。

Answer 1

假设有 n 个桶，有 n² 个键，使用 pigeonhole principle ，我们知道一个桶至少有n个键

为了解决这个问题，我们需要循环所有的键

int keys = n * n;
for(int i = 0; i < keys; i++)

接下来我们查看哪些键发生碰撞的方法是将每个键存储在每组碰撞的列表/集合中

List<List<Integer>> collisions = new ArrayList<List<Integer>>(n);
for(int i = 0; i < n; i++)
    collisions.add(new LinkedList<Integer>());
collisions.get(hash(key)).add(key);

一旦我们有了所有的碰撞，就很容易寻找至少有 n 个碰撞的列表

for(List<Integer> collision : collisions)
    if(collision.size() >= n)
        return collision; //or just print

把它们放在一起......

List<Integer> findCollisions(int n)
{
    List<List<Integer>> collisions = new ArrayList<List<Integer>>(n);
    for(int i = 0; i < n; i++)
        collisions.add(new LinkedList<Integer>());
    int keys = n * n;

    for(int i = 0; i < keys; i++)
        collisions.get(hash(i)).add(i);

    for(List<Integer> collision : collisions)
        if(collision.size() >= n)
            return collision;
    return null; //this should never happen, due to pigeonholes, but compiler doesn't know
}