Implementasi peta dengan kunci duplikat

116

Saya ingin memiliki peta dengan kunci duplikat.

Saya tahu ada banyak implementasi peta (Eclipse menunjukkan kepada saya sekitar 50), jadi saya yakin pasti ada satu yang memungkinkan ini. Saya tahu mudah untuk menulis peta Anda sendiri yang melakukan ini, tetapi saya lebih suka menggunakan beberapa solusi yang ada.

Mungkin sesuatu di commons-collections atau google-collections?

IAdapter
sumber
4
Bagaimana cara kerjanya? Jika Anda meminta nilai yang terkait dengan sebuah kunci, dan kunci ini ada beberapa kali di peta, nilai mana yang harus dikembalikan?
Mnementh
get bisa melempar pengecualian, saya membutuhkan peta ini hanya untuk iterasi.
IAdapter
6
Jika Anda hanya membutuhkannya untuk iterasi, mengapa Anda membutuhkan peta? Gunakan daftar pasangan atau sesuatu ...
Tal Pressman
2
Karena seluruh program saya sudah berfungsi dengan Map dan sekarang saya menemukan bahwa mungkin saja data memiliki kunci duplikat. Jika menggunakan Map dengan cara yang berbeda akan sangat salah kita hanya memiliki 5 implementasi Map dan bukan 50+.
IAdapter

Jawaban:

90

Anda mencari multimap, dan memang baik commons-collections maupun Guava memiliki beberapa implementasi untuk itu. Multimaps memungkinkan beberapa kunci dengan mempertahankan kumpulan nilai per kunci, misalnya Anda dapat meletakkan satu objek ke dalam peta, tetapi Anda mengambil satu koleksi.

Jika Anda dapat menggunakan Java 5, saya lebih suka Guava Multimapkarena bersifat generik.

nd.
sumber
3
Juga, Multimap ini tidak berpura-pura menjadi Peta seperti yang dilakukan apache.
Kevin Bourrillion
7
Perhatikan bahwa Google Collections telah digantikan oleh Guava, jadi berikut ini tautan ke MultiMap versi Guava: code.google.com/p/guava-libraries/wiki/…
Josh Glover
Namun, Multimap tidak sepenuhnya dapat diserialkan, ia memiliki anggota sementara yang menjadikan contoh deserialisasi tidak berguna
dschulten
@dschulten Nah, Multimap adalah antarmuka dan Anda tidak menentukan implementasi yang Anda maksud. com.google.common.collect.HashMultimapmemiliki readObject/ writeObjectmetode, seperti halnya ArrayListMultimap dan Immutable {List, Set} Multimap. Saya akan menganggap contoh deserialisasi yang tidak berguna sebagai bug yang layak dilaporkan.
nd.
1
Apache Collections 4.0 mendukung generics commons.apache.org/proper/commons-collections/javadocs/…
kervin
35

Kami tidak perlu bergantung pada perpustakaan eksternal Koleksi Google. Anda cukup menerapkan Peta berikut:

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

Harap pastikan untuk menyempurnakan kode.

pengguna668943
sumber
14
Anda tidak perlu mengandalkan Multimap Jambu, tentunya. Ini hanya memudahkan hidup Anda, karena Anda tidak perlu menerapkannya kembali, mengujinya, dll.
PhiLho
Ini tidak memungkinkan iterasi yang mulus atas semua pasangan. Pasti ada lebih banyak kekurangan. Saya hendak menyarankan solusi saya yang juga membutuhkan satu kelas tambahan, lalu melihat jawaban @ Mnementh hanya itu.
Mark Jeronimus
2
menulis kode dasar tidak selalu pintar. Google lebih cenderung memiliki tes yang lebih baik
senseiwu
26
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));

Outputnya adalah:

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

Catatan: kita perlu mengimpor file perpustakaan.

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

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

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

import org.apache.commons.collections.MultiMap;
import org.apache.commons.collections.map.MultiValueMap;
Issac Balaji
sumber
2
Saran yang bagus, karena saya menggunakan Spring dalam proyek saya, saya akhirnya menggunakan rasa Spring dari MultiValueMap seperti yang disebutkan dalam dokumen http://docs.spring.io/spring-framework/docs/current/javadoc-api/org/ springframework / util / MultiValueMap.html
ajup
18

Anda cukup meneruskan serangkaian nilai untuk nilai dalam HashMap biasa, sehingga mensimulasikan kunci duplikat, dan terserah Anda untuk memutuskan data apa yang akan digunakan.

Anda juga dapat menggunakan MultiMap , meskipun saya sendiri tidak menyukai ide kunci duplikat.

AlbertoPL
sumber
Terima kasih! Menggunakan TreeMap<String, ArrayList<MyClass>>memecahkan kebutuhan kunci duplikat saya.
Joe
10

Jika Anda ingin mengulang tentang daftar pasangan kunci-nilai (seperti yang Anda tulis di komentar), maka Daftar atau array harus lebih baik. Pertama gabungkan kunci dan nilai Anda:

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

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

}

Ganti Class1 dan Class2 dengan jenis yang ingin Anda gunakan untuk kunci dan nilai.

Sekarang Anda dapat memasukkannya ke dalam array atau daftar dan mengulanginya:

Pair[] pairs = new Pair[10];
...
for (Pair pair : pairs)
{
   ...
}
Mnementh
sumber
Bagaimana saya menerapkan add () atau put (). Saya tidak ingin jumlah dimensi yang hardcore.
Amit Kumar Gupta
2
Dalam hal ini gunakan Daftar. Contoh kedua berubah menjadi List <Pair> pairs = new List <Pair> (); For-loop tetap sama. Anda dapat menambahkan pasangan dengan perintah ini: pair.add (pair);
Mnementh
Sejujurnya, ini mungkin jawaban terbaik.
PaulBGD
6

Masalah ini dapat diatasi dengan daftar entri peta List<Map.Entry<K,V>>. Kami tidak perlu menggunakan pustaka eksternal atau implementasi baru dari Map. Entri peta dapat dibuat seperti ini: Map.Entry<String, Integer> entry = new AbstractMap.SimpleEntry<String, Integer>("key", 1);

Thach Van
sumber
3

Belajarlah dari kesalahan saya ... tolong jangan terapkan ini sendiri. Multimap jambu biji adalah cara yang tepat.

Peningkatan umum yang diperlukan dalam multimaps adalah melarang duplikat pasangan kunci-nilai.

Menerapkan / mengubah ini dalam implementasi Anda bisa mengganggu.

Di Jambu biji sesederhana:

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

ArrayListMultimap<String, Integer> allow_dupe_key_plus_val = ArrayListMultimap.create();
radang dingin
sumber
2

Saya memiliki varian yang sedikit berbeda dari masalah ini: Ini diperlukan untuk mengaitkan dua nilai berbeda dengan kunci yang sama. Hanya mempostingnya di sini jika itu membantu orang lain, saya telah memperkenalkan HashMap sebagai nilainya:

/* @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 );
        }
}

Dalam kode di atas, key frameID dibaca dari string pertama file input di setiap baris, nilai untuk frameTypeHash dibangun dengan memisahkan baris yang tersisa dan disimpan sebagai objek String aslinya, selama periode waktu file mulai memiliki beberapa baris ( dengan nilai yang berbeda) terkait dengan kunci frameID yang sama, sehingga frameTypeHash diganti dengan baris terakhir sebagai nilainya. Saya mengganti objek String dengan objek HashMap lain sebagai bidang nilai, ini membantu dalam mempertahankan kunci tunggal untuk pemetaan nilai yang berbeda.

Suresh Vadali
sumber
2

Tidak perlu perpustakaan mewah. Peta ditentukan oleh kunci unik, jadi jangan menekuknya, gunakan daftar. Arus sangat kuat.

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

Dan hanya itu. Contoh penggunaan:

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()...
BiggDatta
sumber
1
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;
        }
    }
Gabrial David
sumber
Terima kasih @daspilker. Saya hanya melihat hasil edit Anda sekarang. Senang melihat seseorang menemukan potongan saya layak jika diedit.
Gabrial David
1
 1, Map<String, List<String>> map = new HashMap<>();

solusi verbose ini memiliki banyak kekurangan dan rentan terhadap kesalahan. Ini menyiratkan bahwa kita perlu membuat instance Collection untuk setiap nilai, memeriksa keberadaannya sebelum menambahkan atau menghapus nilai, menghapusnya secara manual ketika tidak ada nilai yang tersisa, dan sebagainya.

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

java-map-duplikat-kunci

Daria Yu
sumber
1

bagaimana dengan impl MultiMap seperti itu?

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

}
George
sumber
0

Bisakah Anda juga menjelaskan konteks yang Anda coba terapkan pada peta dengan kunci duplikat? Saya yakin mungkin ada solusi yang lebih baik. Peta dimaksudkan untuk menyimpan kunci unik untuk alasan yang baik. Padahal jika Anda benar-benar ingin melakukannya; Anda selalu dapat memperluas kelas tulis kelas peta kustom sederhana yang memiliki fungsi mitigasi tabrakan dan akan memungkinkan Anda menyimpan banyak entri dengan kunci yang sama.

Catatan: Anda harus mengimplementasikan fungsi mitigasi tabrakan sedemikian rupa, sehingga kunci yang bertabrakan diubah menjadi set unik "selalu". Sesuatu yang sederhana seperti, menambahkan kunci dengan kode hash objek atau sesuatu?

Priyank
sumber
1
Konteksnya adalah saya pikir kunci itu akan unik, tetapi ternyata tidak mungkin. Saya tidak ingin memperbaiki semuanya karena tidak akan sering digunakan.
IAdapter
saya ingin mengubah file XML kecil menjadi hashmap seperti tipe data. Hanya masalahnya adalah struktur file XML tidak diperbaiki
Amit Kumar Gupta
0

sekedar melengkapi, Apache Commons Collections juga memiliki MultiMap . Kelemahannya tentu saja adalah Apache Commons tidak menggunakan Generik.

newacct
sumber
1
Perhatikan bahwa MultiMap mereka mengimplementasikan Map tetapi melanggar kontrak metode Map. Itu menggangguku.
Kevin Bourrillion
0

Dengan sedikit retasan, Anda dapat menggunakan HashSet dengan kunci duplikat. PERINGATAN: ini sangat bergantung pada implementasi 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);
    }
}
Erdem
sumber
0

Jika ada kunci duplikat maka sebuah kunci mungkin sesuai dengan lebih dari satu nilai. Solusi yang jelas adalah memetakan kunci ke daftar nilai-nilai ini.

Misalnya dengan Python:

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
cyberthanasis
sumber
0

Saya menggunakan ini:

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

Alex Arvanitidis
sumber