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 回答