aar*_*lue 5 algorithm hash distributed hashtable asymptotic-complexity
Rendezvous哈希(最高随机权重"HRW")的维基百科页面提出以下声明:
虽然可能首先看起来HRW算法在O(n)时间内运行,但事实并非如此.这些站点可以按层次结构进行组织,并且HRW在每个级别应用为层次结构,从而导致O(log n)运行时间,如.[7]
我得到了参考文献的副本,"用于移动Ad-hoc网络中可扩展位置服务的基于哈希的虚拟层次结构".但是,他们的论文中引用的层次结构似乎非常特定于其应用程序域.据我所知,没有明确说明如何推广该方法.维基百科的评论使得日志似乎是一般情况.
我看了几个一般的HRW实现,但它们似乎都没有比线性时间更好的支持.我给了它一些想法,但我没有看到任何方法来分层组织网站,而不会导致父节点在退出时导致低效的重新映射,从而大大打败了HRW的主要优势.
有人知道怎么做这个吗？或者,维基百科是不正确的,在日志时间有一般的方法来实现这一点？
编辑:调查mcdowella的方法:
好的,我想我知道这是如何起作用的.但是你需要比你指定的更多一点.
如果你只是按照你所描述的那样做,你会遇到这样的情况:每个叶子可能只有零个或一个节点,并且叶子最多的子树中有多少个节点存在显着的差异.如果您在每个级别使用HRW进行交换,只需将整个事物设置为常规搜索树,您就会获得完全相同的效果.从本质上讲,你已经实现了一致的散列,以及在桶之间加载不均等的缺陷.计算组合权重,HRW的定义实施,没有增加任何内容; 你最好只是在每个级别进行搜索,因为它可以节省散列,并且可以在不循环每个基数值的情况下实现
但它是可以解决的:您只需要使用HRW从最终级别的许多替代方案中进行选择.也就是说,您需要所有叶节点都在大型桶中,与一致散列中的副本数相当.这些大型桶应相互大致相等,然后您使用HRW选择特定站点.由于存储桶大小是固定的,这是一个O(n)算法,我们得到了所有关键的HRW属性.
老实说,我认为这是值得怀疑的.它不是HRW的实现,因为它只是将HRW与一致的散列相结合.我想这并没有什么不妥,在某些情况下,它甚至可能比使用复制品的常用技术更好.但我认为说明HRW是log(n)是错误的,如果这实际上是作者的意思.
此外,原始描述也值得怀疑.您不需要在每个级别应用HRW,您不应该这样做,因为这样做没有任何优势; 你应该快速做一些事情(比如索引),然后用HRW作最后的选择.
这真的是我们能做的最好的,还是有其他方法来制作HRW O(log(n))？
如果您为每个站点提供一个以基数 k 表示的足够长的随机 ID（可能通过散列非随机 ID），那么您可以将这些站点与树的叶子相关联，该树的每个节点最多有 k 个后代。不需要将任何站点与树的内部节点相关联。
要确定存储项目的位置，请使用 HRW 从树的根部计算出在树节点处的分支方式，并在到达与站点关联的叶子时停止。您可以执行此操作，而无需与任何站点通信，直到您确定要在哪个站点存储该项目 - 您需要知道的只是构建树的站点的哈希 ID。
因为站点仅与叶子相关联，所以树的内部节点不可能被删除，除非与其下的叶子关联的所有站点都被删除，此时它将变得无关紧要。