java - 紧凑的 java.util.Map 实现

Question

是否有任何 java.util.Map 实现不存储 equals 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 堆转储:

测试 HashMap :

    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以确保您的值最终不会包含两个相等但不相同的引用。

每当您想向 map 添加内容时与 map.put(key,value) , 你应该

1. 查找value在你的canonical map 看看你以前是否遇到过类似的东西。如果canonical.get(value)返回一些东西，那么这是你应该放入 map 的规范表示.
2. 如果canonical中不存在, 然后调用 map.put(key,value)将它添加到主 map ，还有canonical.put(value,value)这样您现在就有了等于该值的事物的规范表示。