哈希表中的负载因子和空间利用率有什么区别？请有人解释一下！
问问题
3761 次
2 回答
1
负载系数
定义：
Hashtable的负载因子是元素与桶的比率。较小的负载因子会导致更快的平均查找时间，但会增加内存消耗。默认负载因子 1.0 通常在速度和大小之间提供最佳平衡。
换句话说，太小load factor会导致更快地访问 HashTable 的元素（同时查找给定元素，或迭代，...）但也需要更多的内存使用。
相反，高负载因子会更慢（平均而言），内存使用量更少。
Abucket持有一定数量的物品。
有时，表中的每个位置都是一个存储桶，其中包含固定数量的项目，所有项目都散列到同一位置。这加快了查找速度，因为可能不需要查看其他位置。
- 线性探测和双散列： 负载因子定义为
n/prime，其中n是表中的项目数，是表prime的大小。因此，负载因子为 1 意味着表已满。
下面是一个 benchmark 的例子（这里是在大量的条件下实现的prime）：
load --- successful lookup --- --- unsuccessful lookup ---
factor linear double linear double
------------------------------------------------------------------------
0.50 1.50 1.39 2.50 2.00
0.75 2.50 1.85 8.50 4.00
0.90 5.50 2.56 50.50 10.00
0.95 10.50 3.15 200.50 20.00
表源。
- 一些哈希表使用其他冲突解决方案： 例如，在单独的链接中，哈希到相同位置的项目存储在链接列表中，查找时间由必须检查的列表节点的数量来衡量。对于成功的搜索，这个数字是
1+lf/2，其中lf是负载因子。因为每个表位置都有一个链表，链表可以包含许多项，所以负载因子可以大于 1，而 1 是普通哈希表中可能的最大值。
空间利用
这个想法是我们将数据记录存储在哈希表中。每条记录都有一个key字段和一个关联的data字段。记录存储在基于其密钥的位置。为每个给定键生成此位置的函数称为 a hash function。
假设每个关键字段包含一个整数，数据字段包含一个字符串（字符串类型的字符数组）。一种可能的哈希函数是hash(key) = key % prime.
定义：
空间利用率将是完全使用的桶数（相对于负载因子）与哈希表中保留的桶总数的比率。
由于技术原因，质数的存储桶效果更好，这（模数是使用的存储桶的数量）可能会浪费内存。
结论：不必进行线性搜索或二分搜索，哈希表通常会在一次比较后完成查找！然而，有时需要进行两次（甚至更多）比较。因此，哈希表提供（几乎）理想的查找时间。代价是，为了获得如此出色的查找时间，内存空间被浪费了。
如您所见，我不是专家，我在撰写本文时正在获取信息，因此欢迎任何评论以使其更准确或更少……嗯……错了……
I switched it in Community Wiki mode (Feel free to improve)
于 2013-06-21T06:17:36.820 回答
0
Load factor是衡量哈希表相对于其总数的填充程度的度量buckets。假设您有 1000 个存储桶，并且您只想存储最多 70% 这个数字。如果load factor比率超过（存储超过 700 个元素）这个最大比率，则可以增加哈希表大小以有效容纳更多元素。
Space utilization是已填充的桶数与哈希表中桶总数的比率。
通常，当负载因子增加时，空间利用率会增加，并且在ideal哈希表中，负载因子和空间利用率应该是线性相关的。但是，在大多数情况下，空间利用率是sublinear负载因子的函数，因为在高负载因子比率的情况下，某些存储桶被分配以容纳 1 个以上的元素。
为了获得接近理想情况的散列性能，您可能需要一个perfect hashing function.
一个完美的散列函数将一个键映射到一个唯一的地址。如果潜在地址的范围与键的数量相同，则该函数是最小（在空间上）完美散列函数
于 2013-06-21T06:07:27.267 回答