YouTube

Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

Chinese, Simplified subtitles

← 布谷鸟哈希的例子

Get Embed Code
2 Languages

Showing Revision 2 created 05/16/2013 by Lian7.

  1. 不,它肯定不会总是成功。
  2. 关于它成功的频率,有一些非常不错的概率保证,
  3. 取决于哈希表大小和数量。
  4. 但是很容易举反例,嗯,在这里我们有 2个哈希表。
  5. 如果我们有 3 项,其中每个有相同的 H1 和 H2 —
  6. 所以,例如如果我们有 3 项,H1 和 H2 都是0,
  7. 我们不可能有办法把他们放进哈希表,
  8. 因为我们只有 2 个空档,任何的哈希函数等于 0。
  9. 因此,在实践中我们选择一定次数的迭代,然后我们继续迭代,
  10. 试图填满该哈希表,直到我们决定我们做了太多次迭代。
  11. 所以如果是这样,那么我们就停下来,我们选择新的哈希函数,然后我们重新开始。
  12. 再次说明,完成这个过程频率,有非常不错的概率保证。
  13. 所以启发这项工作的研究中,
  14. 我们尝试使用的保证
  15. 是我们可以保证失败的机率低于百万分之一。
  16. 所以一旦我们构造了哈希表,查找过程是非常简单的。
  17. 对于想要查找的项,我们要计算所有哈希函数。
  18. 例如,如果我想要查找项目 B,我计算出项目 B 的哈希函数。
  19. 在这里,哈希函数 1 等于 0,哈希函数 2 等于 1。
  20. 所以我要做的是在所有表中查找
  21. 使用特定的哈希函数,直到找到我要找的。
  22. 所以首先,我要去看看表 1 ,我知道我要在空档 0 中看看。
  23. 在这里我看看空档 0,我说,"等一下,那不是 B。"
  24. 然后我得去表 2,看到其哈希值等于 1,
  25. 所以我会在表 2中看空档1,我会说,"啊,B在这里!"
  26. 我现在找到了我要找的值。
  27. 现在如果我们在所有这些位置都找不到它,那它就不在哈希表。
  28. 现在在这里很好的地方是,这查找事件不变。
  29. 它只是要求 T 查找,而 T 是一个常数。
  30. 它可能是 2,它可能会是 3,等等。
  31. 这不同于链接。
  32. 链接的查找时间可变。
  33. 它取决于在桶里有多少项目,
  34. 如果我们在桶里有很多项目,我们就必须一直查看到最后,
  35. 这有可能花费很长时间,
  36. 而在哈希表中,我们可以保证我们确切的工作量,
  37. 在这些哈希表中查找任何项都是固定的工作量。