logo标签列表

具有重复键的映射实现

javaduplicatesguavamultimap
136

我想要一个可以有重复键的映射表。

我知道有很多映射表实现（Eclipse 显示了大约50个），所以我相信一定有一个允许这样做的。我知道编写自己的映射表很容易，但我更愿意使用一些现有的解决方案。

可能在 commons-collections 或 google-collections 中有相关的东西？

4
如果您请求与一个键相关联的值，而且这个键在地图中存在多次，那么应该如何处理？应该返回哪个值？ - Mnementh
获取可能会抛出异常，我只需要这个映射进行迭代。 - IAdapter
6
如果你只需要进行迭代，为什么一开始要使用映射表呢？可以考虑使用成对列表等其他数据结构。 - Tal Pressman
3
因为我的整个程序已经使用了Map，现在我发现数据可能会有重复的键。如果改用其他方式来实现Map，那么就会非常错误，因为我们只需要五种实现而不是50多种。 - IAdapter
20个回答
2

我遇到了一个稍微不同的问题：需要将两个不同的值与相同的键关联起来。为了帮助其他人，我在这里发布我的解决方案，我引入了一个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 );
        }
}

在上面的代码中，关键帧ID从每行的输入文件的第一个字符串中读取，frameTypeHash的值通过拆分剩余行构建，并最初存储为String对象。随着时间的推移，该文件开始具有与相同frameID键相关联的多行（具有不同的值），因此frameTypeHash被覆盖为最后一行作为值。我用另一个HashMap对象替换了String对象作为值字段，这有助于维护单个键到不同值的映射关系。
1

这样的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() .....

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

这个啰嗦的解决方案有多个缺点，容易出错。它意味着我们需要为每个值实例化一个集合，在添加或删除值之前检查其是否存在，在没有值时手动删除等等。
2, org.apache.commons.collections4.MultiMap interface
3, com.google.common.collect.Multimap interface

java-map-duplicate-keys

{{链接1：Java-Map-重复键}}

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;
        }
    }
谢谢@daspilker。我现在才看到你的编辑。很高兴看到有人发现我的代码片段是值得修改的。 - Gabrial David
0
如果存在重复的键，则一个键可能对应多个值。显而易见的解决方案是将键映射到这些值的列表中。
例如，在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
0

通过一些技巧，您可以使用具有重复键的HashSet。警告：这严重依赖于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);
    }
}
0

只需使用简单的Set和Pair。这个Set将排除具有相同键值的对。此外，您可以迭代它。

val set = hashSetOf<Pair<String, String>>()
set.add(Pair("1", "a"))
set.add(Pair("1", "b"))
set.add(Pair("1", "b")) // Duplicate
set.add(Pair("2", "a"))
set.add(Pair("2", "b"))
set.forEach { pair -> println(pair) }

result: (1, a),(2, b),(1, b),(2, a)
0
我使用了以下代码：

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

0

您能否解释一下您尝试实现具有重复键的地图的上下文？我相信肯定有更好的解决方案。映射的目的是为了保留唯一的键，有充分的理由。虽然如果您真的想这样做，您可以始终扩展该类并编写一个简单的自定义映射类，该类具有冲突缓解函数，并使您能够保留具有相同键的多个条目。

注意：您必须实现冲突缓解函数，以便碰撞的键始终转换为唯一集合。可以采用一些简单的方法，如使用哈希码附加键等？

1
情境是我原以为键是唯一的，但事实证明它们可能不是。由于这不经常使用，我不想重构所有内容。 - IAdapter
我想将一个小的XML文件转换成类似于哈希表的数据类型。唯一的问题是XML文件的结构不固定。 - Amit Kumar Gupta
0

为了完整起见，Apache Commons Collections 也有一个 MultiMap。当然，缺点是 Apache Commons 不使用泛型。

1
请注意，他们的MultiMap实现了Map接口，但是违反了Map方法的契约。这让我很不爽。 - Kevin Bourrillion
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接