4

假设我们事先知道键和分布，并且我们想要构建快速查找字典。我们插入并且从不删除项目。

例如这里有频率的键

  • xyz 1000
  • 美国广播公司 5
  • 20 岁左右

好的散列只是第一个字符的一些函数，它将 xyz 映射到 1 个存储桶，并将 abc,abd 映射到存储桶 2。 xyz 主导分布，因此我们专注于此。仅查看 1 个字符比查看所有 3 个字符要快。此外，在查找存储桶中的元素数量为 1 时，我们确定要查找的键必须在该存储桶中。无需将 xyz 与 xyz 进行比较。

由于我们事先知道密钥和分布，我们可以使用完美的散列，但是散列函数可能会很慢。

我不是在寻找最佳解决方案，而是在寻找实用的解决方案。

4

1 回答 1

1

一些考虑，然后我将提出我的解决方案：

  • 如果你实现一个查找表，你需要实现两件事：ahash function和 acollision solving technique

  • 一个快速但低效的哈希函数通常会导致缓慢的冲突解决：哈希函数的一致性。在您知道分布的情况下，这将有所帮助，我将在下面写。

您可以在存储桶中包含“xyz”以及另外 100 个以“x”开头且分布不均的键。GET 的最坏情况可能是 O(100) 或通常是 O(d)，其中 d 是桶的大小，这可能与 O(1) 相差甚远。

我的解决方案考虑了分布。不是针对散列函数，而是针对碰撞技术。

如果您考虑使用链接（散列到相同值的键保存在列表中=您提到的存储桶），您可以基于分布实现列表，如下所示：

  • 避免在列表的开头默认插入并在O(1) 中插入并在 O(d) 中使用GET ，d - 存储桶的大小
  • 但是在 O(d) 中按分布的递减顺序插入，并且对于具有高分布的键，GET 接近 O(1)。因为具有高分布的键将保留在第一个位置。

这样：

  • 您将拥有非常快的GET操作（如果您的 GET 操作比 INSERT 操作更频繁 => 这对您来说可能是一笔很好的交易）
  • 您可以使用快速简单的哈希函数，因为您仅基于第一个字符提出了该函数
于 2013-09-22T16:14:46.783 回答