Создание хэш-карты с двойным ключом - PullRequest
Новая
       28

Создание хэш-карты с двойным ключом

7 голосов
/ 21 декабря 2011

Я ищу подходящую структуру данных для моей проблемы. Я хотел бы иметь возможность выбирать объекты узлов максимально эффективно, используя два ключа. Вставка и удаление также должны быть эффективными. В основном каждый объект узла имеет пару из двух ключей. Пары уникальны, а отдельные ключи - нет. Мне нужно иметь возможность выбрать группу узлов, которые имеют определенное значение для одного из двух ключей.

Пример:

Узел1 имеет ключи a1 и b1

Узел2 имеет ключи a1 и b2

Узел 3 имеет ключи a2 и b2

Я хотел бы, например, иметь возможность выбрать узел с ключом a1, b1, но также и все узлы, которые имеют b2 в качестве ключа 2.

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

Очевидно, что наличие одного ключа, который объединяет два ключа, не решает проблему, потому что мне также нужно иметь возможность искать один ключ без необходимости поиска по всей карте. Это было бы не очень эффективно. Проблема в эффективности. Я мог бы просто найти в каждой записи на карте определенный ключ, но вместо этого я хотел бы использовать хеш, чтобы я мог выбрать несколько узловых объектов, используя один из двух ключей мгновенно.

Я не ищу что-то вроде MultiKeyMap, потому что в этой структуре данных первый ключ всегда остается неизменным, вы можете только добавлять ключи вместо замены первого ключа другим ключом. Я хочу иметь возможность переключаться между первым и вторым ключом.

Я не хочу хранить несколько объектов с одним и тем же ключом. Если вы посмотрите на пример, вы увидите, что две клавиши вместе всегда уникальны. Это можно рассматривать как один ключ, поэтому я не буду хранить несколько объектов под одним ключом. Но если вы посмотрите на отдельные ключи, они не уникальны, поэтому я хочу сохранить несколько объектов, на которые ссылаются отдельные ключи.

Ответы [ 7 ]

6 голосов
/ 21 декабря 2011

Если вы можете использовать библиотеку, взгляните на Таблица интерфейса Guava.Он связывает строку и столбец со значением.Строка и столбцы могут быть вашими первым и вторым ключами.Также вы можете осуществлять поиск по строке или по столбцу.

Одна из реализаций этого интерфейса - на основе хеша .

5 голосов
/ 21 декабря 2011

Необходимо создать класс ключей (равенство рассматривается как Точка ): 

public class Key {

    int field1;
    int field2;

    public boolean equals(Object o) {
        if (o == null || !(o instanceof Key)) return false;
        Key other = (Key) o;
        return field1 == other.field1 && field2 == other.field2;
    }

    public int hashCode() {
        return field1*field2; // doesn't matter if some keys have same hash code
    }

}

Для выбора ключей с одним конкретным значением в первом поле: 

public List<Key> getKeysWithField1EqualsTo(int value) {
    List<Key> result = new ArrayList<>();
    for (Key k: map.keySet()) {
        if (k.field1 == value) result.add(k);
    }
    return result;
}
2 голосов
/ 21 декабря 2011

Поскольку это зависит от конкретной проблемы, вам, скорее всего, потребуется разработать собственную коллекцию.Я бы обернул два MultiMap s от Apache Commons в свой собственный класс коллекции, который занимается обновлением обеих мультикарт одновременно, и использовал бы мой класс для выполнения вставок и запросов.

1 голос
/ 21 декабря 2011

HashMaps может иметь любой объект в качестве ключа, так почему бы не создать класс с 2 полями и считать этот класс своим ключом. Вы также можете переопределить метод Equals, чтобы узнать, как равны ключи

1 голос
/ 21 декабря 2011

Поскольку HashMap может сортировать только по одному хешу для каждого объекта, вы никогда не сможете выбрать отдельные списки «из коробки». Я бы предложил использовать кортеж с двумя ключами, а затем выполнить итерацию по HashMap и выбрать только те элементы, которые имеют tuple.key1 = X.

1 голос
/ 21 декабря 2011

Напишите простой класс, который может содержать два значения (ключи) и переопределять equals (..) и hashCode () для проверок на равенство, используемых картой.Используйте этот простой класс в качестве ключа для карты.

Здесь вы можете найти класс, совместимый с hashmap (2-й ответ):

Что является эквивалентом пары C ++в Java?

0 голосов
/ 11 августа 2015

Я думаю, что мы можем сделать это следующим образом: для каждого ключа мы можем вычислить соответствующий хэш-код. 

key1 -> hashcode1
key2 -> hashcode2

Затем у нас есть двумерный массив с N столбцами и N строками. 

key1 -> rowIndex: hashcode1 MOD N
key2 -> columnIndex: hashcode2 MOD N

Затем мы сохраняем товар в array[rowIndex][columnIndex].

В этой реализации вы можете получить все записи с целевым ключом 1 и любым ключом 2.Вы также можете получить все записи с целевым ключом 2 и любым ключом 1.

Этот массив может расширяться при большом количестве коллизий, точно так же, как вы делаете с обычным хэш-картой.

...