VLListを使用するハッシュテーブル

Question

Phil Bagwell氏は、2002 paper on the VList data structureの中で、VListを使用して永続ハッシュテーブルを実装できることを示しています。しかし、どのように働いたかについての彼の説明には詳細は含まれておらず、理解できません。誰かが私にもっと詳しい説明や例を教えてもらえますか？

さらに、このデータ構造は、Hashtableと同じbig-O複雑さを持つかもしれませんが、追加のルックアップを行うために遅くなることがわかります。キャッシュの振る舞いを含め、どれほど遅いかの詳細な分析を誰かが気にしますか？衝突のない場合や多くの場合の2つのパフォーマンスの関係はどのように変化しますか？

Answer 1

私はこの論文を見て、それは非常に予備と表示されます。それ以降のバージョンが公開されておらず、オリジナルがIFL（作業中の種類の会議）であるという事実は、時間を無駄にしている可能性があることを示唆しています。

Answer 2

Hrmm問題の論文で提案されているデータ構造には、多くの問題があるようです。

カフを外すと、最初に言及された素朴なリストは、提案された時間保証の近くに何かを得るために、一意の参照を必要とするようである。あなたはほとんどの部分が尾を共有する能力を失います。小さなノードをリストの後ろに分けて共有できますが、まだアクティブなvlistのcdrに何かを納得させると、最大のvlistノードを複製する必要があります。そのコストは、リスト全体をコピーするコストに比例します。

後で述べる2dの修正では、それは再び一定になりますが、少なくともページリスト（または悪いことに、vlist）の頭とリストの最初のページをコピーしてしまうので、 。

そこにある機能的なハッシュリストのものは、正直なところ私にはあまり意味がないようです。どれほど実用的であるかを実際に明らかにするのに十分な詳細がなくても、関連性のない紙に固執されたようなものだった。