哈希表大小取决于密钥的长度？

-2

散列表大小取决于负载因子。
它必须是最大素数，并使用该素数作为哈希函数的模值。
素数不能太接近2的幂和10

怀疑我有权力，

是否哈希表的大小取决于密钥长度？

本书后面的段落由Cormen介绍算法。是否n = 2000字符串的平均长度或将存储在散列表中的元素的数量？

对米佳值是素数不是太接近2确切权力对于例如，假设我们要分配一个哈希表，由链解决冲突，持有大约N = 2000字符串，其中一个字符有8位。我们不介意在不成功的搜索检查3个元素的平均值，所以我们分配的大小为m = 701号701的哈希表的选择，因为它是一个素近= 2000/3但不靠近任何2.功率处理每个密钥k为整数，我们散列函数将是

H（K）= K MOD 701。

有人可以解释它>

来源

2016-07-25 sunil sarode

你是指“大小”是什么意思？桶的数量？平均。每个桶的元素数量？平均。链长？ RAM中与表相关的“全部”使用的字节数？ – AnoE

长度的钥匙 –

我不明白你。我问道：“你的意思是'大小'”，显然就你的问题“是否......”而你回答“密钥的长度”......没有计算。 – AnoE

下面是用哈希表的权衡的概述。假设您有一个散列表，其中有m个存储区，存储链总共存储着n个对象。

如果存储对象中的引用，所消耗的总内存为O (m + n)。

现在，假设对于一个普通对象，其大小为s，需要O (s)时间来计算其散列一次，而O (s)来比较两个这样的对象。考虑检查散列表中是否存在对象的操作。该存储桶平均有n/m个元素，所以该操作将花费O (s n/m)时间。

所以，权衡是这样的：当你增加桶数m时，增加内存消耗，但减少单个操作的平均时间。

对于原来的问题 - 是否哈希表的大小取决于密钥长度？ - 不，它不应该，至少不是直接。

您引用的段落仅提及字符串作为存储在散列表中的对象的示例。提到的一个属性是它们是8位字符串。另一个是“我们不介意在不成功的搜索中检查3个元素的平均值”。然后，将存储对象的属性包装为表单：我们想要放置在单个存储桶中的平均数量是多少？字符串本身的长度在任何地方都没有提及。

来源

2016-07-25 12:27:31 Gassa

所以如果对于n = 10^5如果我做10^5/3将散列表的大小平均为单个桶中的3个元素 –

@sunilsarode确实如此。每个元素都必须进入一个桶。当有10^5个元素但是10^5/3个桶时，平均每桶三个元素。 – Gassa

非常感谢您的回答。 –

（2）和（3）为假。只要您使用正确的散列函数，通常使用带有2^n存储桶（ref）的散列表。在（1）上，哈希表所占用的内存等于桶的数量乘以密钥的长度。请注意，对于字符串键，我们通常保留指向字符串的指针，而不是字符串本身，因此键的长度是指针的长度，在64位机器上是8个字节。

来源

2016-07-25 12:10:47 user172818

可以请你解释一下吗？n = 2000表示将存储在散列表中的元素的平均数量？ –

您的报价很混乱。我不确定这意味着什么。 – user172818

算法明智，不！这里关键字的长度是无关紧要的。另外，密钥本身并不重要，重要的是你预测你将拥有的不同密钥的数量。

执行方面，是的！由于您必须将密钥本身保存在散列表中，因此它会反映其大小。

关于第二个问题，“N”是指持有不同钥匙的数量。

来源

2016-07-25 12:12:34

所以散列表的大小= 701，它将有n = 2000个不同密钥的链接形式 –

哈希表大小取决于密钥的长度？

回答

相关问题