总是插入哈希 Table 序列
Hash Table sequence always get inserted
我有一个与哈希相关的问题 tables。
让我们考虑一个开放线性模式中维度 2^n 的散列 table。
h(k,i) = (k^n + 2*i)mod(2^n)。表明序列
{1,2,...2^n}总是可以插入散列table。
我试图找出数字插入 table 的模式，然后应用归纳法看看我是否可以证明我们老师给我们的 question.Any 问题似乎是就像这个，我想不出解决这类问题的方法。
你这里有很多术语问题。
- 你哈希table没有dimensions（其实有，但是是一维的，不是2^n），但是有slots/buckets的个数。
- 您问的问题很可能不是您 book/teacher 希望您解决的问题。你告诉：
Show that the sequence {1,2,...2^n} always can be inserted into the
hash table
问题是在你的情况下，任何自然数都可以插入到你的散列中 table。这很明显，因为您的哈希函数将任何数字映射到 [0 到 2^n) 区域中的自然数，并且因为您的哈希函数有 2^n 个槽，所以任何数字都适合您的哈希。
所以澄清你的老师想要什么，解释一下你的哈希函数中的 k 和 i 是什么，然后问另一个准备更充分的问题。
h(k,i) = (k^n + 2*i)mod(2^n). Show that the sequence {1,2,...2^n} always can be inserted into the hash table.
关于散列函数的两个观察：
k^n，对于n >= 1，当k为奇数时为奇数，当k为偶数时为偶数
2*i 将探测每个第二个桶（从最后到第一个循环）
因此，当您散列 {1,2,...2^n} 时，我们知道您将交替查找未使用的奇数索引桶和偶数索引桶。
为了强调这一点，k^n 位将奇数键限制为奇数索引桶，将偶数键限制为偶数索引桶，而 2*i 确保考虑所有此类桶，直到找到一个免费的。有必要恰好一半的键是奇数，一半是偶数，这样 table 就会变满，而 h(k,i) 不会因为 i 递增而找不到未使用的桶。
我有一个与哈希相关的问题 tables。
让我们考虑一个开放线性模式中维度 2^n 的散列 table。
h(k,i) = (k^n + 2*i)mod(2^n)。表明序列{1,2,...2^n}总是可以插入散列table。
我试图找出数字插入 table 的模式，然后应用归纳法看看我是否可以证明我们老师给我们的 question.Any 问题似乎是就像这个，我想不出解决这类问题的方法。
你这里有很多术语问题。
- 你哈希table没有dimensions（其实有，但是是一维的，不是2^n），但是有slots/buckets的个数。
- 您问的问题很可能不是您 book/teacher 希望您解决的问题。你告诉：
Show that the sequence {1,2,...2^n} always can be inserted into the hash table
问题是在你的情况下，任何自然数都可以插入到你的散列中 table。这很明显，因为您的哈希函数将任何数字映射到 [0 到 2^n) 区域中的自然数，并且因为您的哈希函数有 2^n 个槽，所以任何数字都适合您的哈希。
所以澄清你的老师想要什么，解释一下你的哈希函数中的 k 和 i 是什么，然后问另一个准备更充分的问题。
h(k,i) = (k^n + 2*i)mod(2^n). Show that the sequence{1,2,...2^n}always can be inserted into the hash table.
关于散列函数的两个观察：
k^n，对于n >= 1，当k为奇数时为奇数，当k为偶数时为偶数2*i将探测每个第二个桶（从最后到第一个循环）
因此，当您散列 {1,2,...2^n} 时，我们知道您将交替查找未使用的奇数索引桶和偶数索引桶。
为了强调这一点，k^n 位将奇数键限制为奇数索引桶，将偶数键限制为偶数索引桶，而 2*i 确保考虑所有此类桶，直到找到一个免费的。有必要恰好一半的键是奇数，一半是偶数，这样 table 就会变满，而 h(k,i) 不会因为 i 递增而找不到未使用的桶。