java - 用于共享大型不可变对象(immutable对象)的工厂/缓存策略

Question

我的问题很像之前的帖子Optimal HashSet Initialization (Scala | Java) ，我想在其中使用 HashSet 进行加速(目前我正在使用 Set)，但是 HashSet 没有展示其(恒定时间)优势。

对于提到的解决方案:

You can minimize the cost of equals by interning. This means that you acquire new objects of the class through a factory method, which checks whether the requested new object already exists, and if so, returns a reference to the existing object. If you assert that every object of this type is constructed in this way you know that there is only one instance of each distinct object and equals becomes equivalent to object identity, which is a cheap reference comparison (eq in Scala).

但是，我不太确定什么是有效的检查方式

whether the requested new object already exists

对于大对象(例如，带有 hashmap 参数的 case 类对象，一些其他对象结构...等)

通过比较每个复杂的字段并没有给出太多的性能优势，不是吗？或者如果是，还有其他方法吗？

另外，我也很疑惑如何制作

equals becomes equivalent to object identity, which is a cheap reference comparison (eq in Scala).

在代码中。

上面提到的intening技术，我觉得基本上就是一个对象缓存。 因此，我引用了帖子中提到的技术 Caching strategy for small immutable objects in 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 中的 HashSet？

谢谢，

Answer 1

实习的目标是使 equals 方法能够使用引用相等来实现，如下所示: this eq that(或 Java 中的 this == that)。 很明显，此实现将具有最佳的运行时特性 比较一些字段集的传统 equals 越多。

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

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

正如您所注意到的，这个实习生-ing 可能需要一个潜在的昂贵的缓存机制: 有运行时开销(执行检查) 和内存开销(缓存的大小)。

• 最直接的缓存方法是使用 HashMap 和传统的 equals。 hashCode 应该是惰性的；缓存它的结果，因此不需要重新计算。 可能需要考虑线程问题。

• 实现这种缓存的一种方法是使用 trie ，可能在每个节点上用哈希表实现，并且每个“级别”对应于对象中的一个字段(第一级 - 字段 1，第二级，字段 2 等)用于“用于”的“字段集”建立独特性。”

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

选项 1:无缓存

声明:您很可能通过以下方式获得足够有效的结果 使用快速哈希(并在内部缓存)， equals 的“传统”实现， 并以 sufficient minimal size 的 HashMap 或 HashSet 开始

理想情况下哈希表中的冲突很少， 并且对 equals 的调用次数最少。

选项 2:将多个字段映射到一个唯一的 String

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

构建并缓存一个对应于唯一对象实例的private unique: String。 例如，对于一些简单的对象，以下可能是唯一的:

The concatenation of the string values of the "set of fields used to establish uniqueness," separated by commas.

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

有了这样的值，我们就可以避免单独的intern/caching机制 并通过实现 equals 和 hashCode 保留大部分好处 就此 unique 字符串而言:

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

def hashCode() = unique.hashCode

选项 2 的替代方案:

[编辑:Rüdiger Klaehn 提供 this link which offers compelling evidence to avoid String.intern() ]

使用 String.intern 并调整 equals 以利用它:

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
  }