weakhashmapの純粋に機能的な同等物ですか？

Question

Java's weak hash mapのような弱いハッシュテーブルは、弱参照を使用してガベージコレクタによる到達不能キーのコレクションを追跡し、そのキーを持つバインディングをコレクションから削除します。弱いハッシュテーブルは通常、ガベージコレクタがグラフの到達不能な部分を収集できるようにするために、グラフ内の1つの頂点または辺から他の頂点への迂回を実装するために使用されます。

このデータ構造と同等の機能はありますか？そうでない場合、どのように作成されますか？

これは興味深い課題のようです。到達不可能な部分を取り除くためにデータ構造を収集（つまり突然変異）する必要があるため、内部実装は純粋ではありませんが、データの一部にしか影響を与えないため、不純物を観測することができない純粋なインタフェースをユーザに提示できるユーザは、定義により、もはや手に届かなくなることができる。

Answer 1

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

APIが私に次世代を提供し、コンテナの過去のバージョンへのすべての参照が解放されるまで、値が収集されない場合は、唯一の方法です。データ構造のユーザーは、新世代に弱く保有されている値をリリースするよう定期的に求められます。 （コメントに基づく）

編集：私はあなたが望む行動を理解していますが、オブジェクトを解放するマップと、このテストに合格することはできません。

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"]); 

Answer 2

これは興味深い概念です。 「純粋に機能的」な設定における1つの主要な複雑さは、オブジェクトアイデンティティが「純粋に機能的」な意味で通常は観察できないことである。 I.E。オブジェクトをコピーしたり、新しいものを作成したりすると、Javaではクローンが元のものではないと予想されます。しかし、機能的な設定では、新しいものはガベージコレクタが別の方法で扱うにしても、古いものと意味的に同じであると予想されます。

したがって、オブジェクトアイデンティティをセマンティクスの一部にすることができれば、それは健全か、そうでなければおそらくそうではありません。後者のケースでは、ハックが見つかったとしても（私は1つを考えました、以下で説明します）、事実を悪用するためにあらゆる種類のことを行うため、あなたは言語実装を全面的に戦っている可能性が高いそのオブジェクトアイデンティティは観察可能ではないと考えられます。

私の頭に浮かべている「ハック」は、一意の値をキーとして使用することです。そのため、ほとんどの場合、等価性は参照平等と一致します。例えば、私はそのインターフェイスで、次のとHaskellで個人的に使用し、ライブラリがあります。あなたのようなハッシュマップをキーとしてこれらとおそらくほとんどが仕事だろう記述

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

を、それでもここで私は考えることができますコンパイラの「unbox-strict-fields」最適化を有効にして、あるデータ構造の厳密なフィールドにキーを格納するとします。 'Uniq'がマシン整数への新しいタイプのラッパーである場合、GCが指し示すことができるオブジェクトがなくなり、 "それがキーです"ということができます。ユーザーがキーを使用して解凍して使用すると、そのマップはすでに忘れている可能性があります。（編集：この特定の例は明らかに回避できます; uniqの実装をそのようにunboxすることができないようにする;コンパイラがたくさんの方法で役立つようにしようとしているので、オブジェクトIDが指定されていない限り、多くの場合、「最適化」が弱いハッシュマップ実装によって壊れたり壊れたりすることが考えられます。一流の観察可能な状態。