1

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

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

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

如果 Java 不够用，我将不得不切换到 C/C++，因此也欢迎任何与这些语言相关的想法。

谢谢

4

3 回答 3

4

最简单的方法是定义一个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如果您希望它灵活，则将您的类设为通用。

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

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

于 2010-02-08T04:56:05.050 回答
0

我通过使用以下方式连接两个项目的哈希码部分解决了这个问题：

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浪费项目。这是因为这种算法在每次迭代中合并两个项目，将它们从已使用的项目中删除，但添加新生成的项目。

于 2010-02-11T05:12:33.727 回答
0

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

（顺便说一句，Google Collections 似乎比 Apache Collections获得了更多的关注。）

更新：注意@danben 和@sateesh 的澄清。如果您需要给定 x 或给定 y 的 x，则 BiMap 会很好。但听起来你真的想查找一个 (x, y) 点并取回一个包含缓存信息的值。在这种情况下，请遵循@danben 的建议。

于 2010-02-08T04:32:57.927 回答