Jak zaimplementować mapę z wieloma kluczami? [duplikat]

Commons-collections zapewnia dokładnie to, czego szukasz: http://commons.apache.org/proper/commons-collections/javadocs/api-release/index.html

Wygląda na to, że teraz commons-collections jest wpisane.

Wersję wpisaną na maszynie można znaleźć na: https://github.com/megamattron/collections-generic

To będzie dokładnie wspierać Twój przypadek użycia:

 MultiKeyMap<k1,k2,...,kn,v> multiMap = ??

Nadal będę sugerował rozwiązanie 2 map, ale z tweestem

Map<K2, K1> m2;
Map<K1, V>  m1;

Ten schemat pozwala na dowolną liczbę "aliasów" kluczy.

Pozwala również aktualizować wartość za pomocą dowolnego klucza bez synchronizacji map.

Jeszcze innym rozwiązaniem jest użycie guawa Google

import com.google.common.collect.Table;
import com.google.common.collect.HashBasedTable;

Table<String, String, Integer> table = HashBasedTable.create();

Użycie jest naprawdę proste:

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));

Metoda HashBasedTable.create() w zasadzie robi coś takiego:

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();
    }
});

Jeśli próbujesz stworzyć niestandardowe mapy, powinieneś wybrać drugą opcję (jak sugeruje @Karatheodory), w przeciwnym razie powinieneś być w porządku z pierwszą.

A co z tą klasą "klucza":

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();
    }

}

Deklarowanie Mapy

Map<Key, Double> map = new HashMap<Key,Double>();

Deklarowanie obiektu klucza

Key key = new Key(key1, key2, ..., keyN)

Wypełnianie mapy

map.put(key, new Double(0))

Pobieranie obiektu z mapy

Double result = map.get(key);

Propozycja, zgodnie z sugestią niektórych odpowiedzi:

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);
    }
}

Dlaczego po prostu nie zrezygnować z wymogu, że klucz musi być określonego typu, tzn. wystarczy użyć Map

Czasami leki generyczne po prostu nie są warte dodatkowej pracy.

Stworzyłem to, by rozwiązać podobny problem.

Datastruktura

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();

    }

}

Pobranie wartości:

(Uwaga * Przenieś obiekt z powrotem do wstawionego typu. W moim przypadku był to mój obiekt eventowy)

    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();
        }

    }

Wstawianie

Event e1 = new Event();
e1.setName("Bob");
e1.setTitle("Test");
map.add("key",e1);

Widzę następujące podejścia:

A) Użyj 2 różnych map. Możesz je zapakować do klasy, jak sugerujesz, ale nawet to może być przesadą. Wystarczy użyć mapy bezpośrednio: key1Map.getValue (k1), key2Map.getValue (k2)

B) możesz utworzyć klasę klucza zorientowaną na typ i użyć jej (nieprzetestowanej).

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();
  }
}

Nawiasem mówiąc, w wielu powszechnych przypadkach przestrzeń key1 i przestrzeń key2 nie przecinają się. W takim razie nie musisz robić niczego specjalnego. Po prostu zdefiniuj mapa z wpisami key1=>v oraz key2=>v

Sol: anuluj oba klucze i Utwórz klucz końcowy, użyj tego jako klucza.

Dla wartości kluczowych,

Połącz ket-1 i klucz-2 z come", " w beetween, użyj tego jako oryginalnego klucza.

Klucz = Klucz-1+", " + Klucz-2;

MyMap.put (klucz, wartość);

Podobnie podczas pobierania wartości.

Brzmi jak krotka pytona. Podążając w tym duchu, możesz stworzyć niezmienną klasę własnego pomysłu, która implementuje porównywalne i będziesz ją mieć.

Wszystkie klucze multy prawdopodobnie nie działają, ponieważ put ([key1, key2], val) I get([null, key2]) kończą się używaniem równości [key1, key2] I [null, key2]. Jeśli Mapa zaplecza nie zawiera łyżek hashowych na klucz, poszukiwania są bardzo powolne.

Myślę, że najlepszym sposobem jest użycie dekoratora indeksu (zobacz przykłady key1, key2 powyżej) i jeśli dodatkowy klucz indeksu są właściwościami przechowywanej wartości, możesz użyć nazwy właściwości i reflection, aby zbudować drugie mapy po umieszczeniu (key, val) i dodać dodatkową metodę get (propertyname, propertyvalue) do użycia tego indeksu.

Typ zwracany przez get (propertyname, propertyvalue) może być kolekcją, więc nawet żaden unikalny klucz nie jest indeksowany....

Używałem takiej implementacji dla wielu kluczowych obiektów. Pozwala mi to na użycie niezliczonej liczby kluczy do mapy. Jest skalowalny i dość prosty. Ma jednak ograniczenia: klucze są uporządkowane zgodnie z kolejnością argumentów w konstruktorze i nie będzie działać z tablicami 2D, z powodu użycia tablic.equals (). Aby to naprawić-możesz użyć tablic.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)));
    }
}

Definiuje klasę, która ma instancję K1 i K2. Następnie użyj tego jako klasy jako typu klucza.

Zobacz Zbiory Google . Lub, jak sugerujesz, Użyj mapy wewnętrznie, i niech ta mapa używa pary. Musisz napisać lub znaleźć parę; jest to dość łatwe, ale nie jest częścią standardowych kolekcji.

Wygląda na to, że Twoje rozwiązanie jest całkiem wiarygodne dla tej potrzeby, szczerze mówiąc nie widzę z tym problemu, jeśli twoje dwa typy kluczy są naprawdę różne. Wystarczy, że napiszesz do tego własną implementację i w razie potrzeby poradzisz sobie z problemami z synchronizacją.

Jeśli zamierzasz używać kombinacji kilku kluczy jako jednego, to może Apache commnons MultiKey to twój przyjaciel. Nie sądzę, żeby to działało jeden po drugim..

W zależności od tego, jak będzie używany, możesz to zrobić z dwiema mapami Map<K1, V> i Map<K2, V> lub z dwiema mapami Map<K1, V> i Map<K2, K1>. Jeśli jeden z klawiszy jest bardziej trwały niż drugi, druga opcja może mieć większy sens.

Wydaje mi się, że metody, które chcesz w swoim pytaniu są obsługiwane bezpośrednio przez Map. Te,które chcesz, to

put(K1 key, K2 key, V value)
put(K1 key, V value)
put(K2 key, V value)

Zauważ, że w map, get() i containsKey() itd Wszystkie biorą Object argumenty. Nic nie stoi na przeszkodzie, aby użyć metody one get() do delegowania wszystkich połączonych map kompozytowych (jak wspomniano w pytaniu i innych odpowiedziach). Być może potrzebujesz rejestracji typu, aby nie mieć problemów z rzucaniem klas (jeśli są specjalne + zaimplementowane naiwnie.

Wpisana Rejestracja pozwoli również na pobranie "poprawnej" mapy do użycia:

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?
   .....
}

Proponuję strukturę

Map<K1, Map<K2, V>>

Chociaż wyszukiwanie drugiego klucza może nie być efektywne

Polecam coś takiego:

    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

    }

Wtedy możesz użyć go jak:
myMap.put(k1,value) lub myMap.put(k2,value)

Zalety: jest prosty, wymusza bezpieczeństwo typu i nie przechowuje powtarzających się danych (tak jak robią to dwa rozwiązania map, choć nadal przechowują zduplikowane wartości).
wady : nie ogólne.

Inne rozwiązanie dające możliwość bardziej skomplikowanych kluczy można znaleźć tutaj: http://insidecoffe.blogspot.de/2013/04/indexable-hashmap-implementation.html

Jak o użyciu struktury danych trie ?

Http://en.wikipedia.org/wiki/Trie

The root of the trie will by blank. Rodzeństwo pierwszego poziomu będzie głównymi kluczami mapy, rodzeństwo drugiego poziomu będzie kluczami drugorzędnymi, a trzeci poziom będzie węzłami terminalowymi, które będą miały wartość wzdłuż will null, aby wskazać zakończenie tej gałęzi. Możesz również dodać więcej niż dwa klucze używając tego samego schematu.

Look up to proste DFS.

A może coś takiego:

Jego oświadczenie mówi, że klucze są unikalne, więc zapisywanie tych samych obiektów wartości dla różnych kluczy jest całkiem możliwe i kiedy wyślesz dowolny klucz pasujący do tej wartości, będziemy mogli wrócić do obiektu wartości.

Patrz kod poniżej:

Klasa obiektu wartości,

    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());
        }

    }

}

Wynik jest następujący:

The Name is Bond... James Bond...

Alfred HitchCock

Alfred HitchCock

Alfred HitchCock

Jeśli klawisze są unikalne, to nie ma potrzeby tworzenia 2 Map, Map Map, Map czegokolwiek. Musi być tylko 1 pojedyncza mapa i tylko prosta metoda owijania, która umieściłaby Twoje klucze i wartość na tej mapie. Przykład:

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");
}

Następnie używaj mapy tak, jak zwykle. Nie potrzebujesz nawet tych fantazyjnych getByKeyN i containsKeyN.

Będzie działać zarówno MultiMap, jak i MultiKeyMap z Commons lub Guava.

Jednak szybkim i prostym rozwiązaniem może być samodzielne rozszerzenie map class buy obsługujące klucz złożony, biorąc pod uwagę, że klucze są prymitywnego typu.

Brudnym i prostym rozwiązaniem, jeśli używasz Map tylko do sortowania, powiedzmy, jest dodanie bardzo małej wartości do klucza, dopóki wartość nie istnieje, ale nie dodawaj minimum (na przykład Double.MIN_VALUE) ponieważ spowoduje błąd. Jak powiedziałem, jest to bardzo brudne rozwiązanie, ale to sprawia, że kod jest prostszy.