多选散列

  • 之所以选择多选哈希是因为它采用了多个哈希函数的实现。

  • 在较高级别上,当存在多个哈希函数时,每个项目都映射到多个存储桶,因此Algorithmdesigner可以自由选择将哪个项目驻留在其中。

  • 事实证明,这种自由度允许算法所获得的分配比通过实现单个哈希函数所获得的分配更加平衡。

  • 我们将介绍主要的算法思想和主要的数学工具,以证明这些算法产生的分配范围的界限。

  • 我们将看到分析足以承受基本模型的变化,在我们看来,该模型可以解释这些算法在实际应用中的有效性。

列举了“入桶式”模型的示例,说明了多选散列算法

  • 进行负载平衡过程推理的通用框架是“球”和“箱”的框架,其中需求(键,进程,文件等)由“球”和资源(表插槽,服务器,存储设备)表示单位等。)以“垃圾箱”表示。

  • 在此设置下,没有。通过实施一些分配规则,将球的数量依次扔入n个仓中。

  • 目标是在完成过程后了解球在箱中的分配,通常限制最大装载箱中的负载(=球数)。

  • 根据该模型,通过应用一个或多个哈希函数将球分配给箱。

  • 这些哈希函数负责将球的唯一ID(通常隐含在模型中)映射到通常为1 ... n的一组垃圾箱。

  • 实现散列函数以将垃圾箱映射到球,而不是简单地随机绘制垃圾箱,在通常情况下(在随后的某个时间,需要从其ID恢复球的位置)非常有用。