哈希表的大小是否取决于密钥的长度?
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 个元素”。 这将存储对象的属性包装成以下形式:我们平均要在一个桶中放置多少个元素? 字符串本身的长度没有在任何地方提及。