当插槽数量未知时如何使用哈希表？(How to use hash tables when amount of slots is unknown?)

当插槽数量未知时如何使用哈希表？(How to use hash tables when amount of slots is unknown?)

当使用时所需的插槽数量未知时，如何使用哈希表和链接？ 换句话说，我需要在定义所有键和值之前使用哈希表，我该怎么做？ 我似乎无法弄明白，因为我认为我需要知道为了使哈希函数将键映射到那些插槽所需的插槽数量，但也许我没有完全理解哈希表。

如果有人能帮助我，我将不胜感激！

最好的问候，Skyfe。

How do I use hash tables & chaining when the amount of slots required is yet unknown at usage? In other words I need to use the hash table before all keys and values for it are defined, how do I do this? I can't seem to figure it out since I assumed I'd need to know the amount of slots required in order to make a hash function to map the keys to those slots, but maybe I did not quite get the idea right of a hash table.

If anyone could help me out it'd be much appreciated!

Best regards, Skyfe.

最满意答案

一种方法是简单地采用摊销动态数组的想法。

您可以决定几个因素 - 初始大小，最大负载和增长因子。 例如，您可以使用初始大小= 100，最大负载= 0.5和增长因子= 2。

如果插入了足够多的项目，那么在某些时候您将拥有超过50 = 100 * 0.5项目。 此时，您将分配一个大小为200 =初始大小*增长因子= 100 * 2的数组，重新分配项目，并擦除旧数组。 等等。

两个说明：

在实践中，您可能不希望完全按给定的增长因子进行多次操作，因为您可能希望数组长度为素数。 因此，您乘以因子，找到最接近的较大素数（您应该预先计算）。

收缩是一样的，但你应该使用不同的滞后因子。 见上面的链接。

One way to do so is simply adopt the idea of amortized dynamic arrays.

You decide on a few factors, say - an initial size, a maximal load, and a growth factor. As an example, you could use initial size = 100, maximal load = 0.5, and growth factor = 2.

If enough items are inserted, at some point you'll have more than 50 = 100 * 0.5 items. At this point you allocate an array of size 200 = initial size * growth factor = 100 * 2, redistribute the items, and erase the old array. Etc.

Two notes:

In practice, you wouldn't want to mulitply exactly by a given growth factor, as you probably want the array length to be prime. So you multiply by the factor, find the nearest larger prime (which you should precompute).

Shrinking is the same, but you should use different factors for hysteresis. See the above link.