Двумерные хешмапы в Java (и вообще)

Question

Какой лучший способ эффективно написать двумерный хэш-карту в Java? Просто чтобы привести пример того, о чем я говорю: я разрабатываю некоторые алгоритмы, связанные с коллективным интеллектом, эти алгоритмы работают путем вычисления корреляции между парами элементов ..

Без кэширования этих значений, поскольку они рассчитываются для одних и тех же пар несколько раз, производительность ужасна .. (алгоритмы могут быть O (n ^ 2) , но, возможно, O (n ^ 3) поэтому я подумывал об использовании HashMap для хранения значений, которые будут использоваться несколько раз.

Какой самый эффективный способ реализовать такую ​​структуру данных в Java? Должна быть возможность кэшировать и удалять значение, сгенерированное парой элементов с O (1) , но использование явного класса в любом случае кажется слишком сложным.

Если Java окажется недостаточно, мне придется переключиться на C / C ++, поэтому любые идеи, связанные с этими языками, тоже приветствуются.

Спасибо

Answer 1

Самый простой способ сделать это - определить класс 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> в качестве кэша.

Answer 2

Я частично решил проблему путем объединения хеш-кодов обоих элементов, используя что-то вроде этого:

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 3

Google Collections поддерживает двунаправленные хэш-карты, см. BiMap .

(Кстати, Google Collections, кажется, набирает больше разума по сравнению с Apache Collections.)

Обновление: обратите внимание на разъяснения @danben и @ sateesh. BiMap будет в порядке, если вам нужно получить y с учетом x или x с учетом y. Но, похоже, вы действительно хотите найти точку (x, y) и получить значение, которое содержит вашу кэшированную информацию. В этом случае, воспользуйтесь предложением @ danben.