哈希表的大小是否取决于密钥的长度？
Does hashtable size depends upon length of key?
我所知道的，
- 哈希table 大小取决于加载因子。
- 必须是最大的素数，并使用那个素数作为
哈希函数中的模值。
- 质数不能太接近2的幂和10的幂
我有疑问，
- 散列的大小table是否取决于密钥的长度？
Cormen 的《算法简介》一书中的以下段落。
n=2000 是指字符串的长度还是将存储在散列中的元素的数量 table?
Good values for m are primes not too close to exact powers of 2. For
example, suppose we wish to allocate a hash table, with collisions
resolved by chaining, to hold roughly n = 2000 character strings,
where a character has 8 bits. We don't mind examining an average of 3
elements in an unsuccessful search, so we allocate a hash table of
size m = 701. The number 701 is chosen because it is a prime near =
2000/3 but not near any power of 2. Treating each key k as an integer,
our hash function would be
h(k) = k mod 701 .
谁能解释一下>
(2) 和 (3) 为假。只要您使用正确的哈希函数，具有 2^n 个桶 (ref) 的哈希 table 是很常见的。在 (1) 上，哈希 table 占用的内存等于桶的数量乘以密钥的长度。注意，对于字符串key，我们通常保留的是指向字符串的指针，而不是字符串本身，所以key的长度就是一个指针的长度，在64位机器上是8字节。
算法方面，不！
密钥的长度在这里无关紧要。
而且，钥匙本身并不重要，重要的是你预测你将拥有的不同钥匙的数量。
实施方面，是的！由于您必须将密钥本身保存在哈希表中，因此它反映了它的大小。
对于你的第二个问题，'n'表示要持有的不同键的数量。
这里是对散列 tables 的权衡的一般概述。
假设你有一个散列 table 和 m 个桶，链存储总共 n 个对象。
如果只存储对对象的引用，消耗的总内存为O (m + n)。
现在，假设对于一个普通对象，其大小为 s，计算一次哈希值需要 O (s) 时间，比较两个这样的对象需要 O (s) 时间。
考虑检查散列 table 中是否存在对象的操作。
存储桶平均有 n / m 个元素，因此操作需要 O (s n / m) 时间。
因此，权衡是这样的：当您增加存储桶的数量时 m，您会增加内存消耗，但会减少单个操作的平均时间。
对于原始问题 - 散列的大小table 是否取决于密钥的长度？ - 不应该，至少不直接。
您引用的段落仅提及字符串作为要存储在散列中的对象的示例 table。
其中提到属性是8位字符串。
另一个是“我们不介意在不成功的搜索中平均检查 3 个元素”。
这将存储对象的属性包装成以下形式：我们平均要在一个桶中放置多少个元素？
字符串本身的长度没有在任何地方提及。
我所知道的，
- 哈希table 大小取决于加载因子。
- 必须是最大的素数，并使用那个素数作为 哈希函数中的模值。
- 质数不能太接近2的幂和10的幂
我有疑问，
- 散列的大小table是否取决于密钥的长度？
Cormen 的《算法简介》一书中的以下段落。 n=2000 是指字符串的长度还是将存储在散列中的元素的数量 table?
Good values for m are primes not too close to exact powers of 2. For example, suppose we wish to allocate a hash table, with collisions resolved by chaining, to hold roughly n = 2000 character strings, where a character has 8 bits. We don't mind examining an average of 3 elements in an unsuccessful search, so we allocate a hash table of size m = 701. The number 701 is chosen because it is a prime near = 2000/3 but not near any power of 2. Treating each key k as an integer, our hash function would be
h(k) = k mod 701 .
谁能解释一下>
(2) 和 (3) 为假。只要您使用正确的哈希函数，具有 2^n 个桶 (ref) 的哈希 table 是很常见的。在 (1) 上，哈希 table 占用的内存等于桶的数量乘以密钥的长度。注意，对于字符串key，我们通常保留的是指向字符串的指针，而不是字符串本身，所以key的长度就是一个指针的长度，在64位机器上是8字节。
算法方面，不！ 密钥的长度在这里无关紧要。 而且，钥匙本身并不重要，重要的是你预测你将拥有的不同钥匙的数量。
实施方面，是的！由于您必须将密钥本身保存在哈希表中，因此它反映了它的大小。
对于你的第二个问题，'n'表示要持有的不同键的数量。
这里是对散列 tables 的权衡的一般概述。
假设你有一个散列 table 和 m 个桶，链存储总共 n 个对象。
如果只存储对对象的引用，消耗的总内存为O (m + n)。
现在，假设对于一个普通对象，其大小为 s，计算一次哈希值需要 O (s) 时间，比较两个这样的对象需要 O (s) 时间。
考虑检查散列 table 中是否存在对象的操作。
存储桶平均有 n / m 个元素，因此操作需要 O (s n / m) 时间。
因此，权衡是这样的：当您增加存储桶的数量时 m，您会增加内存消耗，但会减少单个操作的平均时间。
对于原始问题 - 散列的大小table 是否取决于密钥的长度？ - 不应该，至少不直接。
您引用的段落仅提及字符串作为要存储在散列中的对象的示例 table。 其中提到属性是8位字符串。 另一个是“我们不介意在不成功的搜索中平均检查 3 个元素”。 这将存储对象的属性包装成以下形式：我们平均要在一个桶中放置多少个元素？ 字符串本身的长度没有在任何地方提及。