data-structures - 哈希表中空间利用率和负载因子的区别

Question

Hashtable 中的负载因子和空间利用率有什么区别？请大佬解释一下!

Answer 1

负载系数

定义:

The load factor of a Hashtable is the ratio of elements to buckets. Smaller load factors cause faster average lookup times at the cost of increased memory consumption. The default load factor of 1.0 generally provides the best balance between speed and size.

换句话说，太小 load factor将导致更快地访问 HashTable 的元素(在查找给定元素时，或迭代，...)但也需要更多的内存使用。

相反，高负载因子会更慢(平均而言)，内存使用更少。

一个 bucket持有一定数量的元素。

有时表中的每个位置都是一个桶，其中将保存固定数量的项目，所有这些项目都散列到同一位置。这加快了查找速度，因为可能不需要去查看另一个位置。

线性探测以及双重散列:负载系数定义为 n/prime ，其中 n是表中的项目数，prime是 table 的大小。因此，负载因子为 1 意味着表已满。

这是一个基准测试的例子(这里是在一个大 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

表 source .

一些哈希表使用其他冲突解决方案:例如，在单独的链接中，散列到相同位置的项目存储在链表中，查找时间由必须检查的列表节点的数量来衡量。对于成功的搜索，此号码是 1+lf/2 ，其中 lf是负载因子。因为每个表位置都有一个链表，链表可以包含多个项目，所以负载因子可以大于 1，而 1 是普通哈希表中可能的最大值。

空间利用率

这个想法是我们将数据记录存储在哈希表中。每条记录都有一个 key字段和相关联的 data field 。该记录存储在基于其键的位置。为每个给定键生成此位置的函数称为 hash function .

假设每个键字段包含一个整数，数据字段包含一个字符串(字符串类型的字符数组)。一种可能的哈希函数是 hash(key) = key % prime .

定义:

The space utilization would be the ratio of the number of full used buckets (relatively to the load factor) to the total number of buckets reserved in the hash table.

出于技术原因，质数的桶效果更好，其中(以雌性使用的桶数为模)可以包含在 中。内存浪费 .


结论:哈希表通常只需进行一次比较即可完成查找，而不必进行线性搜索或二分搜索!然而，有时需要进行两次(甚至更多次)比较。因此，哈希表提供(几乎)理想的查找时间。权衡是为了获得这么长的查找时间，内存空间被浪费了。

如您所见，我不是专家，我在撰写本文时正在获取信息，因此欢迎任何评论以使其更准确或更少......好吧......错......

         I switched it in Community Wiki mode (Feel free to improve)