用于共享大型不可变对象的工厂/缓存策略

Question

我的问题与之前的后优化哈希集初始化（Scala | Java）非常相似，我想使用哈希集来加速（目前我正在使用哈希集），但哈希集没有显示其（恒定时间）优势。

对于提到的解决方案：

你可以通过实习来减少同等费用。这意味着您通过工厂方法获取类的新对象，工厂方法检查请求的新对象是否已经存在，如果已经存在，则返回对现有对象的引用。如果您断言这种类型的每个对象都是以这种方式构造的，那么您就知道每个不同对象只有一个实例，并且equals与object identity等价，这是一种廉价的引用比较（Scala中的eq）。

然而，我不太确定检查的有效方法是什么

请求的新对象是否已存在

对于大型对象（例如带有hashmap参数的case类对象、其他一些对象结构...等）

通过比较这些复杂字段中的每一个并没有显示出多少性能优势，不是吗？或者如果是，还有其他方法吗？

此外，我也很困惑，如何

等于等于对象标识，这是一种廉价的引用比较（Scala中的eq）。

在代码中。

我认为上面提到的强化技术基本上是一个对象缓存。因此，我参考了Java中针对小型不可变对象的后缓存策略中提到的技术。但是，我仍然不明白对于大型对象有什么有效的方法。

为了方便起见，我引用了帖子中的缓存技术（Java），并指出了我的想法和问题：

private static final int N_POINTS = 10191; 
private static final Point[] POINTS = new Point[N_POINTS];

public static Point of(int x, int y, int z) {
    int h = hash(x,y,z); ///  I can use hash code of each complicated field to construct the value
    int index = (h & 0x7fffffff) % N_POINTS;
    Point p = POINTS[index];
    if (p != null && p.x == x && p.y == y && p.z == z) /// Not working for large objects?
       return p;
    return POINTS[index] = new Point(x,y,z);
} 

总之，为大型对象实现高效缓存策略的最佳实践是什么，以便我可以利用Scala中的哈希集？

谢谢

Answer 1

interning的目标是使用引用等式实现等于方法，如：this eq that（或this==that，在Java中）。很明显，与比较一些字段集的更传统的equals相比，此实现将具有最佳的运行时特性。

这种比较只有在由对象的一组字段确定的每个“唯一对象”有一个且只有一个实例时才有效。

实习只有在实习生操作的前期成本可以被equals的（可能很多）调用的最小成本完全抵消的情况下才有效，由HashMap驱动。

正如您所注意到的，这种实习可能需要一种潜在的昂贵的缓存机制：有运行时开销（执行检查）和内存开销（缓存的大小）。

>

实现这种缓存的一种方法是使用trie，可能在每个节点使用哈希表实现，其中每个“级别”对应于对象中的一个字段（第一级-字段1、第二级、字段2等...）用于“用于建立唯一性的字段集”。

还有其他可行的方法来实现这样的缓存。请原谅我避免进一步讨论此类问题，并允许我提出避免处理该问题的方法。

声明：通过使用快速哈希（并在内部缓存），一个“传统”的equals实现，以及从足够小的哈希映射或哈希集开始，您可能会获得足够有效的结果

理想情况下，哈希表中几乎没有冲突，对equals的调用次数最少。

[此方法假设“唯一定义对象的字段”是不可变的。如果不正确，可以进行适当的调整以进行补偿。]

构建

“用于建立唯一性的字段集”字符串值的串联，用逗号分隔。

了解您的对象/字段特征将有助于确定如何创建这样一个唯一的字符串。

有了这样一个值，我们可以避免单独的实习生/缓存机制，并通过在这个唯一字符串中实现equals和hashCode来保留大部分好处：

def equals(thatObj: Any) = thatObj match {
    case that : MyType => unique.equals(that.unique)
    case _             => false
  }

def hashCode() = unique.hashCode

[编辑：Rüdiger Klaehn提供了这个链接，提供了令人信服的证据来避免String.intern（）]

使用字符串。实习并调整等于以利用它：

private val unique = buildUnique().intern

def equals(thatObj: Any) = thatObj match {
    case that : MyType => unique.eq(that.unique) // In Java: unique == that.unique
    case _             => false
  }