Как реализовать карту с несколькими ключами?
Мне нужна структура данных, которая ведет себя как карта, но использует несколько (по-разному) ключей для доступа к ее значениям.
(Давайте не будем слишком общими, скажем, два ключа)
Ключи гарантированно будут уникальными.
Что-то вроде:
MyMap<K1,K2,V> ...
С такими методами, как:
getByKey1(K1 key)...
getByKey2(K2 key)...
containsKey1(K1 key)...
containsKey2(K2 key)...
У вас есть какие-нибудь предложения?
Единственное, о чем я могу думать, это:
Напишите класс, который использует две Карты внутри.
РЕДАКТИРОВАТЬ Некоторые люди предлагают мне использовать кортеж, пару или аналогичные в качестве ключа для Java-карты, но это не будет работать для меня:
Я должен быть в состоянии, как написано выше, искать значения только по одному из двух указанных ключей.
Карты используют хеш-коды ключей и проверяют их на равенство.
27 ответов
Две карты. Один Map<K1, V> и один Map<K2, V>, Если у вас должен быть один интерфейс, напишите класс-оболочку, который реализует указанные методы.
Commons-collection предоставляет именно то, что вы ищете: https://commons.apache.org/proper/commons-collections/apidocs/
Похоже, теперь набранная коллекция.
Печатную версию можно найти по адресу: https://github.com/megamattron/collections-generic
Это точно поддержит ваш вариант использования:
MultiKeyMap<k1,k2,...,kn,v> multiMap = ??
Я все еще собираюсь предложить решение с 2 картами, но с твиком
Map<K2, K1> m2;
Map<K1, V> m1;
Эта схема позволяет вам иметь произвольное количество ключевых "псевдонимов".
Это также позволяет обновлять значение с помощью любого ключа без синхронизации карт.
Еще одно решение заключается в использовании Google Guava
import com.google.common.collect.Table;
import com.google.common.collect.HashBasedTable;
Table<String, String, Integer> table = HashBasedTable.create();
Использование действительно просто:
String row = "a";
String column = "b";
int value = 1;
if (!table.contains(row, column)) {
table.put(row, column, value);
}
System.out.println("value = " + table.get(row, column));
Метод HashBasedTable.create() в основном делает что-то вроде этого:
Table<String, String, Integer> table = Tables.newCustomTable(
Maps.<String, Map<String, Integer>>newHashMap(),
new Supplier<Map<String, Integer>>() {
public Map<String, Integer> get() {
return Maps.newHashMap();
}
});
если вы пытаетесь создать несколько пользовательских карт, вам следует выбрать второй вариант (как предлагает @Karatheodory), в противном случае у вас все будет в порядке с первым.
Как насчет того, чтобы объявить следующий класс "Ключ":
public class Key {
public Object key1, key2, ..., keyN;
public Key(Object key1, Object key2, ..., Object keyN) {
this.key1 = key1;
this.key2 = key2;
...
this.keyN = keyN;
}
@Override
public boolean equals(Object obj) {
if (!(obj instanceof Key))
return false;
Key ref = (Key) obj;
return this.key1.equals(ref.key1) &&
this.key2.equals(ref.key2) &&
...
this.keyN.equals(ref.keyN)
}
@Override
public int hashCode() {
return key1.hashCode() ^ key2.hashCode() ^
... ^ keyN.hashCode();
}
}
Объявление карты
Map<Key, Double> map = new HashMap<Key,Double>();
Объявление ключевого объекта
Key key = new Key(key1, key2, ..., keyN)
Заполнение карты
map.put(key, new Double(0))
Получение объекта с карты
Double result = map.get(key);
Предложение, предложенное некоторыми ответчиками:
public interface IDualMap<K1, K2, V> {
/**
* @return Unmodifiable version of underlying map1
*/
Map<K1, V> getMap1();
/**
* @return Unmodifiable version of underlying map2
*/
Map<K2, V> getMap2();
void put(K1 key1, K2 key2, V value);
}
public final class DualMap<K1, K2, V>
implements IDualMap<K1, K2, V> {
private final Map<K1, V> map1 = new HashMap<K1, V>();
private final Map<K2, V> map2 = new HashMap<K2, V>();
@Override
public Map<K1, V> getMap1() {
return Collections.unmodifiableMap(map1);
}
@Override
public Map<K2, V> getMap2() {
return Collections.unmodifiableMap(map2);
}
@Override
public void put(K1 key1, K2 key2, V value) {
map1.put(key1, value);
map2.put(key2, value);
}
}
Почему бы просто не отбросить требование, чтобы ключ был определенного типа, то есть просто использовать Map
Иногда дженерики просто не стоят дополнительной работы.
Я создал это, чтобы решить аналогичную проблему.
Структура данных
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
public class HashBucket {
HashMap<Object, ArrayList<Object>> hmap;
public HashBucket() {
hmap = new HashMap<Object, ArrayList<Object>>();
}
public void add(Object key, Object value) {
if (hmap.containsKey(key)) {
ArrayList al = hmap.get(key);
al.add(value);
} else {
ArrayList al = new ArrayList<Object>();
al.add(value);
hmap.put(key, al);
}
}
public Iterator getIterator(Object key) {
ArrayList al = hmap.get(key);
return hmap.get(key).iterator();
}
}
Получить значение:
(Примечание * Приведите Объект обратно к вставленному типу. В моем случае это был мой Объект события)
public Iterator getIterator(Object key) {
ArrayList al = hmap.get(key);
if (al != null) {
return hmap.get(key).iterator();
} else {
List<Object> empty = Collections.emptyList();
return empty.iterator();
}
}
Вставка
Event e1 = new Event();
e1.setName("Bob");
e1.setTitle("Test");
map.add("key",e1);
Я рекомендую что-то вроде этого:
public class MyMap {
Map<Object, V> map = new HashMap<Object, V>();
public V put(K1 key,V value){
return map.put(key, value);
}
public V put(K2 key,V value){
return map.put(key, value);
}
public V get(K1 key){
return map.get(key);
}
public V get(K2 key){
return map.get(key);
}
//Same for conatains
}
Тогда вы можете использовать его как:myMap.put(k1,value) или же myMap.put(k2,value)
Преимущества: он прост, обеспечивает безопасность типов и не хранит повторяющиеся данные (как в решениях для двух карт, хотя все еще хранит повторяющиеся значения).
Недостатки: не общие.
Я вижу следующие подходы:
а) Используйте 2 разные карты. Вы можете обернуть их в класс, как вы предлагаете, но даже это может быть излишним. Просто используйте карты напрямую: key1Map.getValue(k1), key2Map.getValue(k2)
б) Вы можете создать класс ключа с учетом типа и использовать его (не проверено).
public class Key {
public static enum KeyType { KEY_1, KEY_2 }
public final Object k;
public final KeyType t;
public Key(Object k, KeyType t) {
this.k = k;
this.t= t;
}
public boolean equals(Object obj) {
KeyType kt = (KeyType)obj;
return k.equals(kt.k) && t == kt.t;
}
public int hashCode() {
return k.hashCode() ^ t.hashCode();
}
}
Кстати, во многих общих случаях пространство key1 и пространство key2 не пересекаются В этом случае вам не нужно делать ничего особенного. Просто определите карту с записями key1=>v так же как key2=>v
sol: можно соединить оба ключа и сделать окончательный ключ, используйте его в качестве ключа.
для ключевых значений,
соедините кет-1 и ключ-2 с символом "," между ними, используйте его как оригинальный ключ.
ключ = ключ-1 + "," + ключ-2;
myMap.put (ключ, значение);
аналогично при получении ценностей.
Все многопользовательские ключи, вероятно, терпят неудачу, потому что put([key1, key2], val) и get([null, key2]) заканчиваются использованием равных [key1, key2] и [null, key2]. Если резервная карта не содержит хеш-блоков на ключ, тогда поиск выполняется очень медленно.
я думаю, что путь к этому заключается в использовании декоратора индекса (см. примеры key1, key2 выше), и если дополнительные ключи индекса являются свойствами сохраненного значения, вы можете использовать имя свойства и отражение для построения вторичных молочных карт при вводе (ключ, val) и добавьте дополнительный метод get(propertyname, propertyvalue) для использования этого индекса.
тип возвращаемого значения get(propertyname, propertyvalue) может быть коллекцией, поэтому даже ни один уникальный ключ не индексируется....
MultiMap или MultiKeyMap от Commons или Guava будут работать.
Тем не менее, быстрое и простое решение может заключаться в том, чтобы расширить класс Map, самостоятельно обрабатывая составной ключ, учитывая, что ключи относятся к примитивному типу.
Походит на кортеж Питона. Следуя этому духу, вы можете создать собственный неизменный класс, который реализует Comparable, и вы его получите.
Если ключи уникальны, то нет необходимости в 2 картах, картах карт, картах, где бы они ни находились. Должна быть только одна карта и простой метод-обертка, который поместит ваши ключи и значение в эту карту. Пример:
Map<String, String> map = new HashMap<>();
public void addKeysAndValue(String key1, String key2, String value){
map.put(key1, value);
map.put(key2, value);
}
public void testIt(){
addKeysAndValue("behemoth", "hipopotam", "hornless rhino");
}
Затем используйте свою карту, как обычно. Вам даже не нужны эти модные getByKeyN и содержит KeyN.
Как насчет чего-то вроде этого:
Его утверждение говорит, что ключи уникальны, поэтому вполне возможно сохранение одинаковых объектов значений для разных ключей, и когда вы отправите любой ключ, соответствующий указанному значению, мы сможем вернуться к объекту значения.
Смотрите код ниже:
Класс объекта значения,
public class Bond {
public Bond() {
System.out.println("The Name is Bond... James Bond...");
}
private String name;
public String getName() { return name;}
public void setName(String name) { this.name = name; }
}
public class HashMapValueTest {
public static void main(String[] args) {
String key1 = "A";
String key2 = "B";
String key3 = "C";
Bond bond = new Bond();
bond.setName("James Bond Mutual Fund");
Map<String, Bond> bondsById = new HashMap<>();
bondsById.put(key1, bond);
bondsById.put(key2, bond);
bondsById.put(key3, bond);
bond.setName("Alfred Hitchcock");
for (Map.Entry<String, Bond> entry : bondsById.entrySet()) {
System.out.println(entry.getValue().getName());
}
}
}
Результат:
The Name is Bond... James Bond...
Alfred HitchCock
Alfred HitchCock
Alfred HitchCock
Я использовал такую реализацию для нескольких ключевых объектов. Это позволяет мне использовать бесчисленное количество ключей для карты. Это масштабируемо и довольно просто. Но у него есть ограничения: ключи упорядочены в соответствии с порядком аргументов в конструкторе, и он не будет работать с 2D-массивами из-за использования Arrays.equals(). Чтобы это исправить - вы можете использовать Arrays.deepEquals();
Надеюсь, это поможет вам. Если вы знаете причину, по которой его нельзя было использовать в качестве решения таких проблем - пожалуйста, дайте мне знать!
public class Test {
private static Map<InnumerableKey, Object> sampleMap = new HashMap<InnumerableKey, Object>();
private static class InnumerableKey {
private final Object[] keyParts;
private InnumerableKey(Object... keyParts) {
this.keyParts = keyParts;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof InnumerableKey)) return false;
InnumerableKey key = (InnumerableKey) o;
if (!Arrays.equals(keyParts, key.keyParts)) return false;
return true;
}
@Override
public int hashCode() {
return keyParts != null ? Arrays.hashCode(keyParts) : 0;
}
}
public static void main(String... args) {
boolean keyBoolean = true;
double keyDouble = 1d;
Object keyObject = new Object();
InnumerableKey doubleKey = new InnumerableKey(keyBoolean, keyDouble);
InnumerableKey tripleKey = new InnumerableKey(keyBoolean, keyDouble, keyObject);
sampleMap.put(doubleKey, "DOUBLE KEY");
sampleMap.put(tripleKey, "TRIPLE KEY");
// prints "DOUBLE KEY"
System.out.println(sampleMap.get(new InnumerableKey(true, 1d)));
// prints "TRIPLE KEY"
System.out.println(sampleMap.get(new InnumerableKey(true, 1d, keyObject)));
// prints null
System.out.println(sampleMap.get(new InnumerableKey(keyObject, 1d, true)));
}
}
Я бы предложил структуру
Map<K1, Map<K2, V>>
хотя поиск второго ключа может быть неэффективным
Смотрите Google Коллекции. Или, как вы предлагаете, используйте карту внутри, и пусть эта карта использует пару. Вам придется написать или найти Pair<>; это довольно просто, но не является частью стандартных коллекций.
Грязное и простое решение, если вы используете карты только для сортировки, скажем, состоит в том, чтобы добавить очень маленькое значение к ключу, пока значение не существует, но не добавьте минимальное (например, Double.MIN_VALUE), потому что оно вызовет ошибку. Как я уже сказал, это очень грязное решение, но оно упрощает код.
Как насчет использования структуры данных Trie?
http://en.wikipedia.org/wiki/Trie
Корень дерева будет пустым. Братья и сестры первого уровня будут вашими первичными ключами карты, братья и сестры второго уровня будут вашими вторичными ключами, а третий уровень будет терминальными узлами, значение которых будет равно нулю для обозначения завершения этой ветви. Вы также можете добавить более двух ключей, используя одну и ту же схему.
Посмотрите, это просто DFS.
Похоже, ваше решение вполне вероятно для этой цели, честно говоря, я не вижу проблемы с ним, если ваши два ключевых типа действительно различны. Просто заставляет вас писать свою собственную реализацию для этого и решать проблемы синхронизации, если это необходимо.
В зависимости от того, как он будет использоваться, вы можете сделать это с двумя картами Map<K1, V> а также Map<K2, V> или с двумя картами Map<K1, V> а также Map<K2, K1>, Если один из ключей более постоянен, чем другой, второй вариант может иметь больше смысла.
Определите класс, который имеет экземпляр K1 и K2. Затем используйте это как класс в качестве типа ключа.
Мне кажется, что методы, которые вы хотите в вашем вопросе, поддерживаются непосредственно Map. Один (и), который вы, кажется, хотите
put(K1 key, K2 key, V value)
put(K1 key, V value)
put(K2 key, V value)
Обратите внимание, что на карте get() а также containsKey() и т.д. все взять Object аргументы. Ничто не мешает вам использовать тот get() метод делегирования всем составным картам, которые вы объединяете (как отмечено в вашем вопросе и других ответах). Возможно, вам понадобится регистрация типов, чтобы у вас не возникало проблем приведения классов (если они специальные + реализованы наивно.
Типизированная регистрация также позволит вам получить "правильную" карту, которая будет использоваться:
Map<T,V> getMapForKey(Class<T> keyClass){
//Completely naive implementation - you actually need to
//iterate through the keys of the maps, and see if the keyClass argument
//is a sub-class of the defined map type. And then ordering matters with
//classes that implement multiple interfaces...
Map<T,V> specificTypeMap = (Map<T,V) maps.get(keyClass);
if (specificTypeMap == null){
throw new IllegalArgumentException("There is no map keyed by class" + keyClass);
}
return maps.get(keyClass);
}
V put(Object key, V value) {
//This bit requires generic suppression magic - but
//nothing leaves this class and you're testing it right?
//(You can assert that it *is* type-safe)
Map map = getMapForKey(key.getClass());
map.put(object, key);
}
void put(Object[] keys, V value) { //Or put(V value, Object ... keys)
//Might want to catch exceptions for unsupported keys and log instead?
.....
}
Просто некоторые идеи...
Другое возможное решение, обеспечивающее возможность использования более сложных ключей, можно найти здесь: http://insidecoffe.blogspot.de/2013/04/indexable-hashmap-implementation.html
Если вы намерены использовать комбинацию нескольких клавиш в качестве одной, то, возможно, apache commnons MultiKey - ваш друг. Я не думаю, что это будет работать один за другим, хотя..