具有复合键和分层默认值的集合

Question

我想按键存储值。

按键可以是复合的，每个按键最多有两个组件。

我想映射

Compound key {A,null} to Value 1 

此值1将是所有查找用于具有作为其第一成分的密钥的缺省值，除非确切的匹配密钥已经被添加到地图。

所以，如果我添加到地图

Compound key {A,Z} having Value 2 

当我做了一下，我想都看{A,*}类型的UPS返回1，所以{A,F}返回1，因为它没有规定那么回落到默认。这个例外是{A,Z}，它返回2，因为它明确指定。

我可以从第一个原则做到这一点，通过在检查单个组件匹配之前检查是否存在确切的键（两个组件）匹配。

但是，是否有一个现有的集合可以为我做到这一点？

如果我有任意数量的组件，该怎么办？

Answer 1

对于这样的事情，我使用Map<String, Map<String, Integer>>您可以根据自己的喜好将其嵌套。

原来，这工作得很好用null：

Map<String, Map<String, Integer>> mapOfMap = new HashMap<String, Map<String, Integer>>(); 

    //Make one of these for every first key 
    Map<String, Integer> mapOfInt = new HashMap<String, Integer>(); 

    mapOfInt.put(null, 1); 
    mapOfInt.put("Z", 2); 

    mapOfMap.put("A", mapOfInt); 


    System.out.println(mapOfMap.get("A").get(null)); 
    System.out.println(mapOfMap.get("A").get("Z")); 

显示：如果你想

1 
2 

一类隐藏的所有细节（我不会怪你的）尝试这样的：

import java.util.HashMap; 
import java.util.Map; 

public class DoubleKeyMap<K1, K2, V> 
{ 
    Map<K1, Map<K2, V>> mapOfMap; 

    public void put(K1 key1, K2 key2, V value) 
    { 
     if (mapOfMap == null) 
     { 
      mapOfMap = new HashMap<K1, Map<K2, V>>(); 
     } 

     if (! mapOfMap.containsKey(key1)) 
     { 
      mapOfMap.put(key1, new HashMap<K2, V>()); 
     } 

     mapOfMap.get(key1).put(key2, value); 

    } 

    public V get(K1 key1, K2 key2) 
    { 
     if (! mapOfMap.containsKey(key1)) 
     { 
      key1 = null; 
     } 
     if (! mapOfMap.get(key1).containsKey(key2)) 
     { 
      key2 = null; 
     } 
     return mapOfMap.get(key1).get(key2); 
    } 

    public static void main(String[] args) 
    { 
     DoubleKeyMap<String, String, Integer> bigMap = new DoubleKeyMap<String, String,Integer>(); 
     bigMap.put("A", null, 1); 
     bigMap.put("A", "Z", 2); 

     System.out.println(bigMap.get("A", null)); 
     System.out.println(bigMap.get("A", "Z")); 
     System.out.println(bigMap.get("A", "F")); 
    } 
} 

显示：

1 
2 
1 

Answer 2

我认为下面的要求是不可能用一个简单的Map履行：

When I do a look up, I would like ALL look ups of type {A,*} to return 1, with the exception of {A,Z}, which returns 2.

事实上，可以想象，这是可能的，而且map.get(new Compound(A,B))返回与new Compound(A,null)关联的值。那么，这意味着new Compound(A,B)和new Compound(A,null)将具有相同的散列码并且相等。现在，如果我执行map.put(new Compound(A,B),3)，它将覆盖与new Compound(A,null)关联的值，这不是您想要的值。

你需要实现你自己的类型来做到这一点。对于其他组件，实现可以使用Map<Compound<T1,T2>,Integer>来包装化合物值为非空的第二组分，而Map<T1,Integer>。您首先会查看第一张地图，如果您没有找到匹配，请尝试第二张地图。我看不出有什么办法以一种聪明的方式将它扩展到任何数量的组件。

Answer 3

还没有彻底想过到其他方法的任何潜在影响，但你可以做的是覆盖Hashmap.get()

public V get(Object key) { V ret = super.get(key); if (ret==null){ //safe cast to Compound key Compound c=...; ret = super.get(new Compound(c.firstPart, null)); } return ret; } 您可以创建一个复合键，可以让更多的选民，你也可以定义的顺序它这样做。 例如 Compound.getGeneralizedKey（）返回一个新的化合物，使您的搜索顺序无效。

话虽如此，请注意，您的每个get操作现在都是O（n）操作。即对于每个get，您将需要n次执行get。

PS。如果您不需要实现Map接口，它会更好，如果你推翻Hashmap添加像getRecursive(Compound key)

Answer 4

一个更安全的方法，“如果我有分量的任意号码？”

那么，然后抑制一些警告heck出去，并与好隐藏的原始地图去旧学校。

import java.util.HashMap; 
import java.util.Map; 


/** 
* Map lookup with arbitrary number of keys, as set with first use of lay() 
* Missing keys map to null if null key exists 
*/ 
public class MultiKeyMap<K, V> 
{ 
    int expectedNumberOfKeys = -1; 
    V value; 

    @SuppressWarnings("rawtypes") 
    Map<K, Map> topMap = new HashMap<K, Map>(); 

    /** Map to value from keys */ 
    @SuppressWarnings({ "rawtypes", "unchecked" }) 
    public V lay(V value, K... keys) 
    { 
     if (keys == null) 
     { 
      //there are no keys. 
      expectedNumberOfKeys = 0; 
      V oldValue = this.value; 
      this.value = value; 
      return oldValue; 
     } 

     if (expectedNumberOfKeys != -1 && expectedNumberOfKeys != keys.length) 
     { 
      throw new IllegalArgumentException("Expecting " + expectedNumberOfKeys + " keys. Was " + keys.length); 
     } 

     expectedNumberOfKeys = keys.length; 

     Map<K, Map> currentMap = topMap; 

     //all but last key 
     for(int i = 0; i < keys.length - 1; i++) 
     { 
      K key = keys[i]; 

      currentMap = linkToNextMap(currentMap, key); 
     } 

     //last key 
     V oldValue = ((Map<K,V>)currentMap).put(keys[keys.length - 1], value); 
     return oldValue; 

    } 

    @SuppressWarnings({ "rawtypes", "unchecked" }) 
    Map<K,Map> linkToNextMap(Map<K,Map> map, K key) 
    { 
     Map<K, Map> nextMap = null; 

     if (! map.containsKey(key)) 
     { 
      map.put(key, new HashMap<K, Map>()); 
     } 

     nextMap = map.get(key); 

     return nextMap; 
    } 

    /** 
    * Get value maped from keys. Must include as many keys as laid down. 
    * Keys not found are taken as null keys 
    */ 
    @SuppressWarnings({ "rawtypes", "unchecked" }) 
    public V get(K... keys) 
    { 
     if (keys == null) 
     { 
      return value; 
     } 

     //System.out.println(topMap+" <- topMap");//TODO remove 

     if (expectedNumberOfKeys == -1) 
     { 
      return null; 
     } 

     if (expectedNumberOfKeys == 0) 
     { 
      return value; 
     } 

     if (expectedNumberOfKeys != keys.length) 
     { 
      throw new IllegalArgumentException("Expecting " + expectedNumberOfKeys + " keys. Was " + keys.length); 
     } 

     Map<K, Map> currentMap = topMap; 

     //All but last key 
     for(int i = 0; i < keys.length - 1; i++) 
     { 
      currentMap = (Map) getDefault(currentMap, keys[i]); 
     } 

     //Last key 
     V result = (V) getDefault(currentMap, keys[keys.length - 1]); 

     return result; 
    } 

    @SuppressWarnings("rawtypes") 
    Object getDefault(Map map, K key) 
    { 
     Object result = null; 

     if (map != null) 
     { 

      //Use default key (null) if not found 
      if (! map.containsKey(key)) 
      { 
       key = null; 
      } 

      result = map.get(key); 
     } 

     return result; 
    } 

    public static void main(String[] args) 
    { 
     //Build {null={D=4, null=3}, A={null=1, Z=2}} 
     MultiKeyMap<String, Integer> map2 = new MultiKeyMap<String, Integer>(); 
     map2.lay(1, "A", null); 
     map2.lay(2, "A", "Z"); 
     map2.lay(3, null, null); 
     map2.lay(4, null, "D"); 
     System.out.println(map2.get("A", null)); //1   
     System.out.println(map2.get("A", "Z")); //2 
     System.out.println(map2.get("A", "F")); //1 F not found so treating as null 
     System.out.println(map2.get(null, null));//3 
     System.out.println(map2.get(null, "D")); //4 
     System.out.println(map2.get("F", "D")); //4 F not found so treating as null 
     System.out.println(); 

     //Build {null={D={C=4}, null={C=3}}, A={null={B=1}, Z={B=2}}} 
     MultiKeyMap<String, Integer> map3 = new MultiKeyMap<String, Integer>(); 
     map3.lay(1, "A", null, "B"); 
     map3.lay(2, "A", "Z", "B"); 
     map3.lay(3, null, null, "C"); 
     map3.lay(4, null, "D", "C"); 
     System.out.println(map3.get("A", null, "B")); //1 
     System.out.println(map3.get("A", "Z", "B")); //2 
     System.out.println(map3.get("A", "F", "B")); //1 F not found so treating as null 
     System.out.println(map3.get(null, null, "C"));//3 
     System.out.println(map3.get(null, "D", "C")); //4 
     System.out.println(map3.get("F", "D", "C")); //4 F not found so treating as null 
    } 
} 

显示：

1 
2 
1 
3 
4 
4 

1 
2 
1 
3 
4 
4 

我知道没有人会投票支持这一点，但我无法入睡，直到我把它拿出来我的头。

晚安好。