17

Hash-consing包括在内存中只保留给定对象的一个​​副本；也就是说，如果两个对象在语义上是相等的（相同的内容），那么它们应该在物理上是相等的（在内存中的相同位置）。该技术通常通过保持全局哈希集并仅在它们不等于哈希集中的对象时才创建新对象来实现。

一个额外的要求是，如果哈希表中的对象没有被哈希表之外的任何东西引用，则它们应该是可收集的；否则，哈希表应该包含弱引用。

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

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

我可以使用Dictionaryto WeakReference，但这不会释放指向悬空引用的键。

有些人提倡使用System.Runtime.CompilerServices.ConditionalWeakTable，但这个类似乎做相反的事情：它在收集键时释放值，而我需要在收集值时释放键。

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

因此我的问题是：是否有一些等价物Dictionary会保留对值的弱引用并在引用悬空时释放键？

4

1 回答 1

3

你是对的，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 内部是如何工作的，或者做任何魔法。库的用户可以决定在哪里清理或简单地“忘记”工厂对象 - 这将收集整个表。

于 2013-03-27T16:06:34.413 回答