在F#中使用散列值,在.net中使用弱散列表

Question

散列消耗包括在内存中仅保留给定对象的一个​​副本; 也就是说,如果两个对象在语义上相等(相同的内容),那么它们应该在物理上相等(内存中的相同位置).该技术通常通过保持全局散列集并仅在它们不等于散列集中的对象时创建新对象来实现.

另一个要求是,如果除了哈希表之外的任何东西都没有引用哈希表中的对象,那么它们应该是可收集的.否则说,哈希表应该包含弱引用.

由于需要有恒定的时间,因此需要进行浅层,散列和相等测试,因此问题更加复杂; 因此,对象具有唯一标识符,当将新对象添加到表中时,该标识符会递增.

我有一个工作实现,它使用System.Collections.Generic.Dictionary<key, node>where key元组给出一个浅层的节点摘要(适用于默认的散列和相等测试)并且node是对象.唯一的问题是Dictionary保持对节点的强引用!

我可以使用a Dictionary,WeakReference但这不会释放指向悬空引用的键.

有些人主张使用,System.Runtime.CompilerServices.ConditionalWeakTable但是这个类似乎反过来了:它在收集密钥时释放了值,而我需要在收集值时释放密钥.

可以尝试使用,System.Runtime.CompilerServices.ConditionalWeakTable<node, node>但我需要自定义散列和相等测试...并且ConditionalWeakTable记录不使用GetHashCode()虚方法,而是使用默认的散列函数.

因此,我的问题是:是否有一些相当于Dictionary保持对值的弱引用并在引用变为悬空时释放键？

Answer 1

你是对的，CWT 没有解决散列consing 问题，因为它回避了这个问题——它的键假定引用相等。然而，可能值得指出的是，CWT 不保留键或值。这是一个小测试：

open System.Collections.Generic
open System.Runtime.CompilerServices

let big () =
    ref (Array.zeroCreate (1024 * 1024) : byte [])

let test1 () =
    let d = Dictionary(HashIdentity.Reference)
    for i in 1 .. 10000 do
        stdout.WriteLine(i)
        let big = big ()
        d.Add(big, big)
    d

let test2 () =
    let d = ConditionalWeakTable()
    for i in 1 .. 10000 do
        stdout.WriteLine(i)
        let big = big ()
        d.Add(big, big)
    d

在我的机器上，test1内存不足并test2成功。似乎只有 CWT 不保留键和值时才会发生这种情况。

对于哈希consing，你最好的选择可能是Artem在评论中建议的。如果这听起来太复杂，那么将控制权交给用户也很有意义，例如：

let f = MyFactory() // a dictionary with weak reference values hidden inside
f.Create(..) : MyObject // MyObject has no constructors of its own
f.Cleanup() // explicitly cleans up entries for collected keys 

那么您就不需要引入线程、研究 GC 内部工作原理或施展任何魔法。库的用户可以决定在哪里适合清理或简单地“忘记”工厂对象 - 这将收集整个表。