data-structures - 使用 VList 的哈希表

Question

Phil Bagwell 在他2002 年关于 VList 数据结构的论文中指出，您可以使用 VList 来实现持久哈希表。然而，他对它如何工作的解释并没有包含太多细节，我也不明白。谁能给我更详细的解释，甚至是例子？

此外，在我看来，这种数据结构虽然可能具有与 Hashtable 相同的 big-O 复杂性，但会更慢，因为它会进行额外的查找。是否有人愿意详细分析慢了多少，最好包括缓存行为？在没有碰撞或碰撞很多的情况下，两者的性能关系如何变化？

Answer 1

我看了这篇论文，它看起来很初步。事实上，没有发布更高版本，并且原版出现在 IFL（这是一个正在进行中的会议），这表明你可能在浪费你的时间。

Answer 2

嗯，该论文提出的数据结构似乎存在许多问题。

即兴发挥，首先提到的幼稚 vlist 似乎需要独特的参考，以便获得接近所提议的时间保证的任何东西。你失去了大部分分享尾巴的能力。您可以共享列表后面的小节点，但是当您将某些东西放到仍然处于活动状态的 vlist 的 cdr 上时，您最终不得不复制最大的 vlist 节点。该成本与复制整个列表的成本成正比。

通过后面提到的 2d 修改，它再次变为常量，但它是一个相当大的常量，因为您最终至少复制了页面列表（或更糟糕的是，vlist）的头部和列表中的第一页。

老实说，那里的功能哈希列表对我来说似乎没有多大意义。这只是一个简短的宣传，似乎被固定在另一篇无关的论文上，没有足够的细节来真正说明它的实用性。