紧凑的 java.util.Map 实现

Question

是否有任何 java.util.Map 实现不存储等于 ValueObjects 的值但只存储其中一个？（这个对象的引用不同，但它们是相等的）

这是一个小测试代码：

Map<Integer, Integer> map = new HashMap<Integer, Integer>(); 
for (int i = 0; i <= 1000000; i++) { 
map.put(i, new Integer(42)); 
}

和可视化 VM 显示：200 万个 Integer 实例这些对象是相等的，但 Map 存储了所有这些对象

仅用于历史记录，我编写了 chiastic-security 的解决方案并对其进行测试以与 HashMap 进行比较：

public class CompactMap<K, V> implements Map<K, V> {

private Map<K, V> map;
private Map<V, V> canonicalMap;

public CompactMap() {
    map = new HashMap<K, V>();
    canonicalMap = new HashMap<V, V>();
}

@Override
public void clear() {
    map.clear();
    canonicalMap.clear();
}

@Override
public boolean containsKey(Object key) {
    return map.containsKey(key);
}

@Override
public boolean containsValue(Object value) {
    return map.containsValue(value);
}

@Override
public Set<java.util.Map.Entry<K, V>> entrySet() {
    return map.entrySet();
}

@Override
public V get(Object key) {
    return map.get(key);
}

@Override
public boolean isEmpty() {
    return map.isEmpty();
}

@Override
public Set<K> keySet() {
    return map.keySet();
}

@Override
public V put(K key, V value) {
    V canonValue = canonicalMap.get(value);
    V previous = null;
    if (canonValue != null) {
        previous = map.put(key, canonValue);
    } else {
        previous = map.put(key, value);
        canonicalMap.put(value, value);
    }
    return previous;
}

@Override
public void putAll(Map<? extends K, ? extends V> m) {
    if (m == null) throw new NullPointerException("Can't exceute putAll for null-map argument");
    for (Map.Entry<? extends K, ? extends V> entry : m.entrySet()) {
        map.put(entry.getKey(), entry.getValue());
    }
}

@Override
public V remove(Object key) {
    V removalValue = map.get(key);
    map.remove(key);
    if (!map.containsValue(removalValue)) {
        canonicalMap.remove(removalValue);
    }
    return removalValue;
}

@Override
public int size() {
    return map.size();
}

@Override
public Collection<V> values() {
    return map.values();
}

}

测试紧凑地图：

    public static void main(String[] args) {
       Map<Integer, Integer> compactMap = new CompactMap<Integer, Integer>();
       //Map<Integer, Integer> usualMap = new HashMap<Integer, Integer>();
       for (int i=0; i<=1000000; i++) {
           compactMap.put(i, new Integer(i % 1000));
           // usualMap.put(i, new Integer(i % 1000));
       }
    }

CompactMap 的 VisualVM 堆转储：

测试哈希映射：

    public static void main(String[] args) {
       // Map<Integer, Integer> compactMap = new CompactMap<Integer, Integer>();
       Map<Integer, Integer> usualMap = new HashMap<Integer, Integer>();
       for (int i=0; i<=1000000; i++) {
           // compactMap.put(i, new Integer(i % 1000));
           usualMap.put(i, new Integer(i % 1000));
       }
    }

HashMap 的 VisualVM 堆转储：

Answer 1

标准实现不处理这个，但你可以很容易地推出你自己的。诀窍是保持一个HashMap<K,V> map来保存你的真实映射，另一个HashMap<V,V> canonical来确保你的值最终不会包含两个相等但不相同的引用。

每当你想在mapwith 中添加一些东西时map.put(key,value)，你应该

1. value在您的canonical地图中查找，看看您以前是否遇到过与此相同的事情。如果canonical.get(value)返回某些内容，那么这就是您应该放入map.
2. 如果它不存在于 中canonical，则调用map.put(key,value)将其添加到主地图中，并且canonical.put(value,value)现在您拥有与该值相等的事物的规范表示。