Implementacja mapy ze zduplikowanymi kluczami

Chcę mieć mapę ze zduplikowanymi kluczami.

Wiem, że istnieje wiele implementacji map (Eclipse pokazuje mi około 50), więc założę się, że musi istnieć taka, która na to pozwala. Wiem, że łatwo jest napisać własną mapę, która to robi, ale wolałbym użyć istniejącego rozwiązania.

Może coś w kolekcjach-wspólnych lub kolekcjach-google?

Szukasz multimapy i rzeczywiście, zarówno wspólne kolekcje, jak i guawa, mają do tego kilka implementacji. Multimapy pozwalają na użycie wielu kluczy, utrzymując zbiór wartości na klucz, tj. Możesz umieścić pojedynczy obiekt na mapie, ale pobierasz kolekcję.

Jeśli możesz używać Java 5, wolałbym Guava, Multimapponieważ jest świadoma generycznych.

Nie musimy polegać na zewnętrznej bibliotece Google Collections. Możesz po prostu zaimplementować następującą mapę:

Map<String, ArrayList<String>> hashMap = new HashMap<String, ArrayList>();

public static void main(String... arg) {
   // Add data with duplicate keys
   addValues("A", "a1");
   addValues("A", "a2");
   addValues("B", "b");
   // View data.
   Iterator it = hashMap.keySet().iterator();
   ArrayList tempList = null;

   while (it.hasNext()) {
      String key = it.next().toString();             
      tempList = hashMap.get(key);
      if (tempList != null) {
         for (String value: tempList) {
            System.out.println("Key : "+key+ " , Value : "+value);
         }
      }
   }
}

private void addValues(String key, String value) {
   ArrayList tempList = null;
   if (hashMap.containsKey(key)) {
      tempList = hashMap.get(key);
      if(tempList == null)
         tempList = new ArrayList();
      tempList.add(value);  
   } else {
      tempList = new ArrayList();
      tempList.add(value);               
   }
   hashMap.put(key,tempList);
}

Upewnij się, że dostroiłeś kod.

Multimap<Integer, String> multimap = ArrayListMultimap.create();

multimap.put(1, "A");
multimap.put(1, "B");
multimap.put(1, "C");
multimap.put(1, "A");

multimap.put(2, "A");
multimap.put(2, "B");
multimap.put(2, "C");

multimap.put(3, "A");

System.out.println(multimap.get(1));
System.out.println(multimap.get(2));       
System.out.println(multimap.get(3));

Wynik to:

[A,B,C,A]
[A,B,C]
[A]

Uwaga: musimy zaimportować pliki biblioteczne.

http://www.java2s.com/Code/Jar/g/Downloadgooglecollectionsjar.htm

import com.google.common.collect.ArrayListMultimap;
import com.google.common.collect.Multimap;

lub https://commons.apache.org/proper/commons-collections/download_collections.cgi

import org.apache.commons.collections.MultiMap;
import org.apache.commons.collections.map.MultiValueMap;

Możesz po prostu przekazać tablicę wartości dla wartości w zwykłym HashMap, symulując w ten sposób zduplikowane klucze, i to od Ciebie zależy, jakich danych użyjesz.

Możesz też po prostu użyć MultiMapy , chociaż sam nie podoba mi się pomysł duplikowania kluczy.

Jeśli chcesz iterować po liście par klucz-wartość (jak napisałeś w komentarzu), to lista lub tablica powinny być lepsze. Najpierw połącz swoje klucze i wartości:

public class Pair
{
   public Class1 key;
   public Class2 value;

   public Pair(Class1 key, Class2 value)
   {
      this.key = key;
      this.value = value;
   }

}

Zastąp Class1 i Class2 typami, których chcesz użyć dla kluczy i wartości.

Teraz możesz umieścić je w tablicy lub liście i iterować po nich:

Pair[] pairs = new Pair[10];
...
for (Pair pair : pairs)
{
   ...
}

Ten problem można rozwiązać za pomocą listy wpisów na mapie List<Map.Entry<K,V>>. Nie musimy używać ani zewnętrznych bibliotek, ani nowej implementacji Map. Wpis mapy można utworzyć w następujący sposób: Map.Entry<String, Integer> entry = new AbstractMap.SimpleEntry<String, Integer>("key", 1);

commons.apache.org

MultiValueMap class

Ucz się na moich błędach ... proszę, nie wdrażaj tego samodzielnie. Multimap Guava to droga do zrobienia.

Typowym ulepszeniem wymaganym w multimapach jest uniemożliwienie zduplikowanych par klucz-wartość.

Wdrażanie / zmienianie tego w implementacji może być denerwujące.

W guawie jest to tak proste, jak:

HashMultimap<String, Integer> no_dupe_key_plus_val = HashMultimap.create();

ArrayListMultimap<String, Integer> allow_dupe_key_plus_val = ArrayListMultimap.create();

Miałem nieco inny wariant tego problemu: wymagane było skojarzenie dwóch różnych wartości z tym samym kluczem. Po prostu zamieszczając go tutaj, na wypadek, gdyby pomogło innym, jako wartość wprowadziłem HashMap:

/* @param frameTypeHash: Key -> Integer (frameID), Value -> HashMap (innerMap)
   @param innerMap: Key -> String (extIP), Value -> String
   If the key exists, retrieve the stored HashMap innerMap 
   and put the constructed key, value pair
*/
  if (frameTypeHash.containsKey(frameID)){
            //Key exists, add the key/value to innerHashMap
            HashMap innerMap = (HashMap)frameTypeHash.get(frameID);
            innerMap.put(extIP, connName+":"+frameType+":"+interfaceName);

        } else {
            HashMap<String, String> innerMap = new HashMap<String, String>();
            innerMap.put(extIP, connName+":"+frameType+":"+interfaceName);
            // This means the key doesn't exists, adding it for the first time
            frameTypeHash.put(frameID, innerMap );
        }
}

W powyższym kodzie klucz frameID jest odczytywany z pierwszego ciągu pliku wejściowego w każdym wierszu, wartość frameTypeHash jest konstruowana przez podzielenie pozostałej linii i pierwotnie była przechowywana jako obiekt String, przez pewien czas plik zaczął mieć wiele wierszy ( z różnymi wartościami) skojarzony z tym samym kluczem frameID, więc frameTypeHash został nadpisany ostatnią linią jako wartością. Zastąpiłem obiekt String innym obiektem HashMap jako polem wartości, co pomogło w utrzymaniu pojedynczego klucza do różnych mapowań wartości.

Nie są wymagane żadne wymyślne biblioteki. Mapy są definiowane przez unikalny klucz, więc nie zginaj ich, używaj listy. Strumienie są potężne.

import java.util.AbstractMap.SimpleImmutableEntry;

List<SimpleImmutableEntry<String, String>> nameToLocationMap = Arrays.asList(
    new SimpleImmutableEntry<>("A", "A1"),
    new SimpleImmutableEntry<>("A", "A2"),
    new SimpleImmutableEntry<>("B", "B1"),
    new SimpleImmutableEntry<>("B", "B1"),
);

I to wszystko. Przykłady użycia:

List<String> allBsLocations = nameToLocationMap.stream()
        .filter(x -> x.getKey().equals("B"))
        .map(x -> x.getValue())
        .collect(Collectors.toList());

nameToLocationMap.stream().forEach(x -> 
do stuff with: x.getKey()...x.getValue()...

class  DuplicateMap<K, V> 
{
    enum MapType
    {
        Hash,LinkedHash
    }

    int HashCode = 0;
    Map<Key<K>,V> map = null;

    DuplicateMap()
    {
        map = new HashMap<Key<K>,V>();
    }

    DuplicateMap( MapType maptype )
    {
        if ( maptype == MapType.Hash ) {
            map = new HashMap<Key<K>,V>();
        }
        else if ( maptype == MapType.LinkedHash ) {
            map = new LinkedHashMap<Key<K>,V>();
        }
        else
            map = new HashMap<Key<K>,V>();
    }

    V put( K key, V value  )
    {

        return map.put( new Key<K>( key , HashCode++ ), value );
    }

    void putAll( Map<K, V> map1 )
    {
        Map<Key<K>,V> map2 = new LinkedHashMap<Key<K>,V>();

        for ( Entry<K, V> entry : map1.entrySet() ) {
            map2.put( new Key<K>( entry.getKey() , HashCode++ ), entry.getValue());
        }
        map.putAll(map2);
    }

    Set<Entry<K, V>> entrySet()
    {
        Set<Entry<K, V>> entry = new LinkedHashSet<Map.Entry<K,V>>();
        for ( final Entry<Key<K>, V> entry1 : map.entrySet() ) {
            entry.add( new Entry<K, V>(){
                private K Key = entry1.getKey().Key();
                private V Value = entry1.getValue();

                @Override
                public K getKey() {
                    return Key;
                }

                @Override
                public V getValue() {
                    return Value;
                }

                @Override
                public V setValue(V value) {
                    return null;
                }});
        }

        return entry;
    }

    @Override
    public String toString() {
        StringBuilder builder = new  StringBuilder();
        builder.append("{");
        boolean FirstIteration = true;
        for ( Entry<K, V> entry : entrySet() ) {
            builder.append( ( (FirstIteration)? "" : "," ) + ((entry.getKey()==null) ? null :entry.getKey().toString() ) + "=" + ((entry.getValue()==null) ? null :entry.getValue().toString() )  );
            FirstIteration = false;
        }
        builder.append("}");
        return builder.toString();
    }

    class Key<K1>
    {
        K1 Key;
        int HashCode;

        public Key(K1 key, int hashCode) {
            super();
            Key = key;
            HashCode = hashCode;
        }

        public K1 Key() {
            return Key;
        }

        @Override
        public String toString() {
            return  Key.toString() ;
        }

        @Override
        public int hashCode() {

            return HashCode;
        }
    }

 1, Map<String, List<String>> map = new HashMap<>();

to rozwlekłe rozwiązanie ma wiele wad i jest podatne na błędy. Oznacza to, że musimy utworzyć instancję Collection dla każdej wartości, sprawdzić jej obecność przed dodaniem lub usunięciem wartości, usunąć ją ręcznie, gdy nie ma żadnych wartości itp.

2, org.apache.commons.collections4.MultiMap interface
3, com.google.common.collect.Multimap interface 

java-map-duplicate-keys

a co z takim implem MultiMap?

public class MultiMap<K, V> extends HashMap<K, Set<V>> {
  private static final long serialVersionUID = 1L;
  private Map<K, Set<V>> innerMap = new HashMap<>();

  public Set<V> put(K key, V value) {
    Set<V> valuesOld = this.innerMap.get(key);
    HashSet<V> valuesNewTotal = new HashSet<>();
    if (valuesOld != null) {
      valuesNewTotal.addAll(valuesOld);
    }
    valuesNewTotal.add(value);
    this.innerMap.put(key, valuesNewTotal);
    return valuesOld;
  }

  public void putAll(K key, Set<V> values) {
    for (V value : values) {
      put(key, value);
    }
  }

  @Override
  public Set<V> put(K key, Set<V> value) {
    Set<V> valuesOld = this.innerMap.get(key);
    putAll(key, value);
    return valuesOld;
  }

  @Override
  public void putAll(Map<? extends K, ? extends Set<V>> mapOfValues) {
    for (Map.Entry<? extends K, ? extends Set<V>> valueEntry : mapOfValues.entrySet()) {
      K key = valueEntry.getKey();
      Set<V> value = valueEntry.getValue();
      putAll(key, value);
    }
  }

  @Override
  public Set<V> putIfAbsent(K key, Set<V> value) {
    Set<V> valueOld = this.innerMap.get(key);
    if (valueOld == null) {
      putAll(key, value);
    }
    return valueOld;
  }

  @Override
  public Set<V> get(Object key) {
    return this.innerMap.get(key);
  }

  @Override
  etc. etc. override all public methods size(), clear() .....

}

Czy mógłbyś również wyjaśnić kontekst, dla którego próbujesz zaimplementować mapę ze zduplikowanymi kluczami? Jestem pewien, że mogłoby być lepsze rozwiązanie. Mapy mają na celu przechowywanie unikalnych kluczy nie bez powodu. Chociaż jeśli naprawdę chcesz to zrobić; zawsze możesz rozszerzyć klasę i napisać prostą niestandardową klasę mapy, która ma funkcję ograniczania kolizji i umożliwiłaby przechowywanie wielu wpisów z tymi samymi kluczami.

Uwaga: Należy zaimplementować funkcję ograniczania kolizji, tak aby kolidujące klucze były konwertowane na unikalny zestaw „zawsze”. Coś prostego, jak dodanie klucza z hashcode obiektu czy coś takiego?

aby być kompletnym, Apache Commons Collections ma również MultiMap . Wadą jest oczywiście to, że Apache Commons nie używa Generics.

Przy odrobinie hackowania możesz użyć HashSet ze zduplikowanymi kluczami. OSTRZEŻENIE: jest to silnie zależne od implementacji HashSet.

class MultiKeyPair {
    Object key;
    Object value;

    public MultiKeyPair(Object key, Object value) {
        this.key = key;
        this.value = value;
    }

    @Override
    public int hashCode() {
        return key.hashCode();
    }
}

class MultiKeyList extends MultiKeyPair {
    ArrayList<MultiKeyPair> list = new ArrayList<MultiKeyPair>();

    public MultiKeyList(Object key) {
        super(key, null);
    }

    @Override
    public boolean equals(Object obj) {
        list.add((MultiKeyPair) obj);
        return false;
    }
}

public static void main(String[] args) {
    HashSet<MultiKeyPair> set = new HashSet<MultiKeyPair>();
    set.add(new MultiKeyPair("A","a1"));
    set.add(new MultiKeyPair("A","a2"));
    set.add(new MultiKeyPair("B","b1"));
    set.add(new MultiKeyPair("A","a3"));

    MultiKeyList o = new MultiKeyList("A");
    set.contains(o);

    for (MultiKeyPair pair : o.list) {
        System.out.println(pair.value);
    }
}

Jeśli istnieją zduplikowane klucze, klucz może odpowiadać więcej niż jednej wartości. Oczywistym rozwiązaniem jest mapowanie klucza do listy tych wartości.

Na przykład w Pythonie:

map = dict()
map["driver"] = list()
map["driver"].append("john")
map["driver"].append("mike")
print map["driver"]          # It shows john and mike
print map["driver"][0]       # It shows john
print map["driver"][1]       # It shows mike

Użyłem tego:

java.util.List<java.util.Map.Entry<String,Integer>> pairList= new java.util.ArrayList<>();