4

Java の弱いハッシュ マップのような弱いハッシュ テーブルは、弱い参照を使用して、ガベージ コレクターによって到達不能なキーのコレクションを追跡し、コレクションからそのキーとのバインディングを削除します。ウィーク ハッシュ テーブルは通常、グラフ内の 1 つの頂点またはエッジから別の頂点またはエッジへの間接化を実装するために使用されます。

このデータ構造に純粋に機能的に相当するものはありますか? そうでない場合、どのように作成できますか?

これは興味深い挑戦のようです。到達不能な部分を削除するためにデータ構造を収集 (つまり、変更) する必要があるため、内部実装は純粋ではありませんが、データの一部にしか影響しないため、不純物を観察することができなかったユーザーに純粋なインターフェイスを提供できると思います。定義上、ユーザーが到達できない構造。

4

2 に答える 2

2

それは興味深いコンセプトです。「純粋に機能的」な設定における 1 つの大きな問題は、オブジェクトの同一性が「純粋に機能的」な意味で通常観察できないことです。IE、オブジェクトをコピーするか、新しい同一のオブジェクトを作成すると、Java ではクローンがオリジナルではないことが予想されます。しかし、機能的な設定では、新しいものは古いものと意味的に同一であることが期待されます。

したがって、オブジェクトの同一性をセマンティクスの一部にすることを許可すれば、それは適切でしょうが、そうでなければおそらくそうではありません。後者の場合、ハッキングが見つかったとしても (以下で説明するハックを考えました)、言語の実装がいたるところであなたと戦っている可能性があります。そのオブジェクトのアイデンティティは観察可能であるとは想定されていません。

私の頭に浮かんだ1つの「ハック」は、構築によって一意の値をキーとして使用することです。これにより、ほとんどの場合、値の等価性が参照の等価性と一致します。たとえば、Haskell で個人的に使用しているライブラリがあり、そのインターフェイスには次のものがあります。

data Uniq s
getUniq :: IO (Uniq RealWorld)
instance Eq (Uniq s)
instance Ord (Uniq s)

あなたが説明したようなハッシュマップは、おそらくこれらをキーとして使用するとほとんど機能しますが、ここでも壊れる可能性がある方法を考えることができます:ユーザーが、コンパイラの「unbox- strict-fields」の最適化が有効になりました。'Uniq' が単なるマシン整数への newtype ラッパーである場合、GC が指して「それが鍵だ」と言うことができるオブジェクトはもはや存在しない可能性があります。そのため、ユーザーがキーを使用するために行って開梱すると、マップはすでにそれを忘れている可能性があります。（編集：この特定の例は明らかに回避できます。Uniqの実装をそのようにアンボックスできないものにします。要点は、コンパイラが多くの方法で役立つようにしようとしているため、注意が必要です。予想）

TL;DR: できないとは言いませんが、多くの場合、「最適化」は弱いハッシュ マップの実装によって中断されるか、中断されると思います。

于 2011-01-17T14:47:36.630 に答える
0

純粋に機能的なデータ構造は、ユーザーの観点からは変更できません。したがって、ハッシュ マップからキーを取得して待機し、同じキーを再度取得する場合は、同じ値を取得する必要があります。鍵を握れるから、消えない。

それが機能する唯一の方法は、API が次世代を提供し、コンテナーの過去のバージョンへのすべての参照が解放されるまで値が収集されない場合です。データ構造のユーザーは、新しい世代が弱く保持されている値を解放するよう定期的に要求することが期待されます。

EDIT（コメントに基づく）：あなたが望む動作は理解していますが、オブジェクトを解放するマップでこのテストに合格することはできません：

FunctionalWeakHashMap map = new FunctionalWeakHashMap();

{ // make scope to make o have no references
   Object o = new SomeObject();
   map["key"] = o;
}  // at this point I lose all references to o, and the reference is weak

// wait as much time as you think it takes for that weak reference to collect, 
// force it, etc

Assert.isNotNull(map["key"]); // this must be true or map is not persistent

私は、このテストが合格する可能性があることを示唆しています

FunctionalWeakHashMap map = new FunctionalWeakHashMap();

{ // make scope to make o have no references
   Object o = new SomeObject();
   map["key"] = o;
}  // at this point I lose all references to o, and the reference is weak in the map

// wait as much time as you think it takes for that weak reference to collect, 
// force it, etc

map = map.nextGen();

Assert.isNull(map["key"]);
于 2011-01-17T14:00:50.723 に答える