0

假设我有一个唯一数字列表（例如 105、342、432、34 等），我想将它们映射到索引（0、1、2、3 等）。有没有通用的方法来做到这一点？如果没有，假设您事先知道列表中的所有数字，并且可以硬编码它们的值。如果这没有帮助，另一个限制因素可能是这些数字“几乎是连续的”。这意味着它们大部分是连续的，但可能存在间隙（您提前知道）。

4

1 回答 1

1

您想要做的基本上是实现哈希映射（或字典）。有许多用于实现这种结构的语言的库。
幕后发生的事情，以一种非常简化的方式，比如说，一个数组和一个散列函数，它将你的数字映射到数组的一个索引，以实现对基于元素的 O(1) 摊销访问在他们的钥匙上。
第二个重要方面是如何处理碰撞。例如，您的数字的散列函数是f(x) = x mod 10. 13和33都将被散列为3. 这是一个冲突，必须处理。例如，您可以创建元素的有序列表并将它们分配给数组的槽。搜索元素时，您将散列其键并在指定数组的位置搜索列表以查找精确的键匹配。
这只是一切的开始，您可以在 Hash function和Hash map on wikipedia 中找到有关这一切的更多信息。
值得一提的是，在您的情况下，您只想自己存储密钥。通常我们需要存储更复杂的对象并通过它们的键来搜索它们，它们通常是数字或字符串，但也可以是任何类型的更复杂的对象。

编辑
我刚刚意识到，您的问题更多是关于为您的特定场景找到最佳哈希函数，而不是针对与您类似的问题的更通用的解决方案。
如果我理解正确，您是说您事先知道数字？如果确实是这种情况，您可以将数字分配给数组中的每个索引，以非常硬编码的形式（如您自己建议的那样），例如：

if (num == 105)
    idx = 0;
else if (num == 342)
    idx = 1;
...

如果你不知道你的数字，但你知道它们中最小的和最大的，你可以将它们散列到索引中：

f(x) = (x - smallest_num) mod (greatest_num - smallest_num + 1)

在这种情况下，f(x)是一个完美的散列函数，这意味着不会有任何冲突。鉴于您的数字并不总是连续的，您的数组仍然会有一些空位。

注意：我仍然不确定您打算对此做什么，因此我不确定我是否正确回答了您的问题。特别是您可能事先知道您的号码，或者您可能对它们了解很多，这让我感到困惑。也许如果您的目的得到澄清，我们可以为您提供以不同方式实现目标的方法。

于 2012-07-01T20:23:45.997 回答