data-structures - 将键插入长度为 9 的哈希表

Question

所以，我正在解决一个需要我在哈希表中按顺序插入键的问题。我在 20 之后停止插入，因为没有更多空间。我提供以下图片以帮助了解上下文。我创建了哈希表，找到了碰撞次数和负载因子。冲突通过开放寻址解决。抱歉，这不是问题，我只需要有人检查一下并告诉我它是否正确。

Answer 1

您的问题存在许多错误和误解。

• 您声明您“在 20 之后停止插入”，但您显示了 15 个键。
• 您的哈希表中有 9 个存储桶，但您声明负载因子为 1。负载因子是键的数量（15 或 20）除以存储桶的数量（9），因此它不是 1。
• 在散列函数h(k,i) k中是键，i是桶的数量。在你的情况下i是 9 所以这个函数(k mod 9 + 5i) mod 9真的没有意义。
• 所有哈希函数都应以mod i.
• 您提供的密钥中没有 15 次冲突。仅当表中有先前的值时才会发生冲突。

这一切都在关于hashtables的维基百科文章中进行了解释。

考虑到此答案下方评论中的说明，我使用以下代码来验证您的结论：

public class Hashing {
    private static final int SIZE = 9;
    private final int[] keys = new int[SIZE];
    private int collisions = 0;

    public void add(int key) {
        int attempt = 0;
        while (keys[hash(key, attempt)] > 0)
            attempt++;
        collisions += attempt;
        keys[hash(key, attempt)] = key;
    }

    private int hash(int key, int attempt) {
        return (key % SIZE + 5 * attempt) % SIZE;
    }

    public static void main(String[] args) {
        Hashing table = new Hashing();
        Stream.of(28, 5, 15, 19, 10, 17, 33, 12, 20).forEach(table::add);
        System.out.println("Table " + Arrays.toString(table.keys));
        System.out.println("Collisions " + table.collisions);
    }   
}

并收到以下输出：

Table [20, 28, 19, 33, 12, 5, 15, 10, 17]
Collisions 15