纯功能相当于weakhashmap？

Question

弱哈希表如 Java 的弱哈希映射 使用弱引用，用于跟踪垃圾收集器对无法访问的键的收集，并从集合中删除与该键的绑定。弱哈希表通常用于实现从图中的一个顶点或边到另一顶点或边的间接寻址，因为它们允许垃圾收集器收集图中无法到达的部分。

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

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

Answer 1

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

因此，如果我们允许对象身份成为语义的一部分，那就是合理的，否则可能不是。在后一种情况下，即使可以找到黑客攻击（我想到了一个，如下所述），您也可能会遇到语言实现到处与您对抗的情况，因为它会做各种各样的事情来利用这一事实该对象身份不应该是可观察的。

我想到的一个“技巧”是使用构造上唯一的值作为键，这样在大多数情况下，值相等将与引用相等一致。例如，我有一个在 Haskell 中个人使用的库，其界面如下：

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

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

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

Answer 2

从用户的角度来看，纯功能性数据结构无法改变。因此，如果我从哈希映射中获取一个键，等待，然后再次获取相同的键，我必须获得相同的值。我可以握住钥匙，这样它们就不会消失。

唯一可行的方法是 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"]);