使用VLists的哈希表

Question

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

此外,在我看来,我可以看到这个数据结构,虽然它可能具有与Hashtable相同的大O复杂性,但它会更慢,因为它会进行额外的查找.是否有人关心如何慢慢地进行详细分析,最好包括缓存行为？在没有碰撞或多次碰撞的情况下,两者之间的绩效关系如何变化？

Answer 1

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