data-structures - 纯功能等效于弱 HashMap ？

Question

像 Java's weak hash map 这样的弱哈希表使用弱引用来跟踪垃圾收集器对无法访问的键的集合，并从集合中删除与该键的绑定(bind)。弱哈希表通常用于实现从图中的一个顶点或边到另一个的间接寻址，因为它们允许垃圾收集器收集图的不可达部分。

这种数据结构是否存在纯粹的功能等价物？如果没有，如何创建一个？

这似乎是一个有趣的挑战。内部实现不可能是纯粹的，因为它必须收集(即变异)数据结构以删除无法访问的部分，但我相信它可以为用户提供一个纯粹的界面，用户永远无法观察到杂质，因为它们只影响数据的一部分根据定义，用户无法再访问的结构。

Answer 1

这是一个有趣的概念。 “纯功能”设置中的一个主要并发症是对象身份通常在“纯功能”意义上是不可观察的。即，如果我复制一个对象或创建一个新的相同对象，在 Java 中，预计克隆不是原始对象。但是在功能设置中，期望新的在语义上与旧的相同，即使垃圾收集器会以不同的方式处理它。

因此，如果我们允许对象身份成为语义的一部分，那将是合理的，否则可能不会。在后一种情况下，即使可以找到一个 hack(我想到了一个，如下所述)，你很可能会让语言实现到处与你争吵，因为它会做各种各样的事情来利用这个事实该对象身份不应该是可观察的。

一个突然出现在我脑海中的“hack”是使用独特的构造值作为键，这样在大多数情况下，值相等将与引用相等一致。例如，我有一个我在 Haskell 中个人使用的库，其界面中有以下内容:

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

像您描述的哈希映射可能主要使用这些作为键，但即使在这里我也能想到一种可能会破坏的方法:假设用户将键存储在某个数据结构的严格字段中，编译器的“unbox-启用严格字段”优化。如果 'Uniq' 只是机器整数的新类型包装器，则可能不再有 GC 可以指向并说“这是关键”的任何对象；因此，当用户打开 key 使用它时， map 可能已经忘记了它。 (编辑:这个特定的例子显然可以解决；使 Uniq 的实现成为不能像那样拆箱的东西；关键是它很棘手，因为编译器试图以很多我们可能不会提供的方式提供帮助预计)

TL;DR:我不会说它不能完成，但我怀疑在许多情况下，“优化”会被弱哈希映射实现破坏或破坏，除非对象标识被赋予一流的可观察状态。