总是插入哈希 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
递增而找不到未使用的桶。