F#中的哈希共享技术和.NET中的弱哈希表

Question

F#中的哈希共享技术和.NET中的弱哈希表

17

哈希共享是指在内存中只保留一个特定对象的副本；也就是说，如果两个对象在语义上相等（具有相同的内容），则它们在物理上应该相等（在内存中位置相同）。通常通过保持全局哈希集并仅在它们不等于哈希集中的对象时创建新对象来实现该技术。

另一个要求是，哈希表中的对象应该是可回收的，如果除哈希表之外没有任何东西引用它们，则可以回收。换句话说，哈希表应该包含弱引用。

此问题进一步复杂化，需要具有常数时间、浅层哈希和相等性测试；因此，对象具有唯一标识符，当向表添加新对象时，它会增加。

我有一个工作实现，使用System.Collections.Generic.Dictionary<key, node>，其中key是给出节点的浅层摘要的元组（适合默认哈希和相等性测试），而node是对象。唯一的问题是Dictionary会保留对节点的强引用！

可以使用Dictionary来添加 WeakReference，但这不会释放指向悬空引用的键。

有人主张使用System.Runtime.CompilerServices.ConditionalWeakTable，但是这个类似乎相反：它在收集键时释放值，而我需要在收集值时释放键。

可以尝试使用System.Runtime.CompilerServices.ConditionalWeakTable<node, node>，但我需要自定义哈希和相等性测试...并且文档说明ConditionalWeakTable不要使用GetHashCode()虚拟方法，而是使用默认的哈希函数。

因此，我的问题是：是否有某个等效于Dictionary，它将保留对值的弱引用并在引用变为悬空时释放键？

- David Monniaux

当值被收集时，您是否需要立即释放密钥？或者您可以放宽要求，在稍后的时间释放密钥吗？ - Jack P.

说句实话，我也有一个使用“Weak”模块中的哈希表的OCaml实现，以及一个使用“WeakHashMap”的Java实现。 - David Monniaux

1

你能否使用 OCaml 代码作为参考实现，在 F# 中实现弱哈希表？如果我没记错，弱哈希集使用弱数组，可以用 Array<WeakReference> 实现。 - fmr

2

这似乎与“压缩WeakReference字典”有关：Compacting a WeakReference Dictionary。 - Artem Koshelev

1

此外，DependentHandle 可能会有所帮助：.NET 和 C# 中的 Ephemerons。 - Artem Koshelev

显示剩余4条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- t0yv0 · Accepted Answer

您说得没错，CWT并不能解决哈希共享的问题，因为它存在一个假设——其键假定引用相等。但是，值得指出的是，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 没有像值一样保持键时才会发生这种情况。

对于哈希共享，你最好采用 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内部工作原理或者进行任何操作。库的使用者可以决定何时清理或者只是“遗忘”工厂对象-这将收集整个表格。