Java 中的二维哈希图（以及一般情况）

Question

在 Java 中高效编写二维哈希图的最佳方法是什么？只是举个例子来说明我正在谈论的内容：我正在开发一些与集体智慧相关的算法，这些算法通过计算元素对之间的相关性来工作。

如果不缓存这些值，因为它们是在同一对上多次计算的，所以性能非常糟糕。（算法可以是 O(n^2) 但也许 O(n^3) 所以我正在考虑使用 HashMap 来存储要多次使用的值。

在Java中实现这种数据结构最有效的方法是什么？应该可以缓存并删除由一对元素生成的值 复杂度(1), ，但无论如何使用显式类似乎太重了。

如果 Java 不够用，我将不得不转向 C/C++，所以任何与这些语言相关的想法也受到欢迎。

谢谢

Answer 1

余部分通过使用这样的级联两个项目的散列码解决了这个问题：

private long computeKey(Object o1, Object o2)
{
    int h1 = o1.hashCode();
    int h2 = o2.hashCode();

    if (h1 < h2)
    {
        int swap = h1;
        h1 = h2;
        h2 = swap;
    }

    return ((long)h1) << 32 | h2;
}

我还是要搞清楚这是存储已经与指定的一个缓存当算法不需要再项删除它们，只是为了避免HashMap填充有废物的所有元素的最有效方式的项目。这是因为一种算法在每次迭代合并两个项目从用过的旧删除它们，但将所生成的新项目。

Answer 2

最简单的方法是定义一个 Pair 班级。它应该是不可变的（哈希键不应该改变），并且 hashCode() 应符合 equals.

类似于（省略方法实现）：

public class Pair() {
  int a, b;

  public Pair(int a, int b);

  public int getA();

  public int getB();

  public boolean equals(Object obj);

  public int hashCode();
}

笔记：

• 如果您不需要整数，则可以使用您想要的任何类型，或者使您的 Pair class generic 如果你希望它灵活。

• (x, y) == (y,x) 取决于你。

有了这个在手，你就可以拥有 HashMap<Pair, SomethingElse> 作为你的缓存。

Answer 3

Google Collections 支持双向哈希图，请参阅 双图.

（顺便说一句，谷歌收藏似乎是 获得更多的关注 超过 Apache 集合。）

更新：请注意@danben 和@sateesh 的澄清。如果您需要给定 x 得到 y，或者给定 y 得到 x，BiMap 就可以了。但听起来您确实想查找 (x, y) 点并返回包含缓存信息的值。在这种情况下，请采纳@danben 的建议。