基于键列表获取子HashMap的最佳方法是什么？

Question

我有一个HashMap，我想得到一个包含仅来自第一个HashMap元素的新HashMap，其中K属于特定列表。 我可以查看所有键并填充新的HashMap，但我想知道是否有更有效的方法？ 谢谢

- aregnier

Answer 1

使用Java8流，有一种函数式（优美）的解决方案。如果keys是要保留的键列表，而map是源Map。

keys.stream()
    .filter(map::containsKey)
    .collect(Collectors.toMap(Function.identity(), map::get));

完整的示例：

    List<Integer> keys = new ArrayList<>();
    keys.add(2);
    keys.add(3);
    keys.add(42); // this key is not in the map

    Map<Integer, String> map = new HashMap<>();
    map.put(1, "foo");
    map.put(2, "bar");
    map.put(3, "fizz");
    map.put(4, "buz");

    Map<Integer, String> res = keys.stream()
        .filter(map::containsKey)
        .collect(Collectors.toMap(Function.identity(), map::get));

    System.out.println(res.toString());

输出: {2=bar, 3=fizz}

编辑: 添加一个filter用于过滤掉地图中不存在的键

- T.Gounelle

---

这种方法的问题在于，如果你注释掉 map.put(2, "bar"); 这一行，就会出现 NullPointerException。 - Paul Boddington

Answer 2

是的，有解决办法：

Map<K,V> myMap = ...;
List<K> keysToRetain = ...;
myMap.keySet().retainAll(keysToRetain);

Set上的retainAll操作会更新底层的map。请参考java文档。

编辑 请注意，此解决方案会修改Map。

- T.Gounelle

---

但他要求一个新的 HashMap。 - KrishPrabakar

只需将原始地图传递给第二个地图的构造函数来复制原始地图：Map<K,V> map2 = new HashMap<>( myMap )。然后调用 map2.retainAll( keysToRetain );。 - Basil Bourque

Answer 3

借助Guava。

假设你有一个映射Map<String, String>，并且想要从List<String>列表中获取值的子映射。

Map<String, String> map = new HashMap<>();
map.put("1", "1");
map.put("2", "2");
map.put("3", "4");

final List<String> list = Arrays.asList("2", "4");

Map<String, String> subMap = Maps.filterValues(
                map, Predicates.in(list));

更新/注记：正如评论中@assylias所提到的，使用contains()会导致O(n)。因此，如果列表很大，这可能会对性能产生巨大影响。

另一方面，HashSet.contains()是常数时间O(1)，因此，如果有可能使用Set而不是List，这可能是一个好方法（请注意，将List转换为Set无论如何都需要O(n)，所以最好不要转换:))

- vtor

---

与视图相同的注释：如果列表较大，则可能会非常慢。 - assylias

非常好的观点。我更新了我的答案，提到了在处理大型列表时的性能影响。 - vtor

我很想在这个项目中使用Guava，但我不能。此外，这个解决方案很有趣，但我想知道是否有一种不需要外部库的解决方案。 - aregnier

问题是基于键进行过滤，而不是值，因此 Maps.filterKeys() 是正确的选择。 - tkruse

Answer 4

如果您有Map m1和List keys，那么请尝试以下操作：

Map m2 = new HashMap(m1);
m2.keySet().retainAll(keys);

- Evgeniy Dorofeev

---

@tkruse 这就是使用 HashMap 复制构造函数所实现的文字意思。 - M. Justin

Answer 5

根据您的使用情况，这可能是一种更高效的实现方式。

public class MapView implements Map{
  List ak;
  Map map;
  public MapView(Map map, List allowableKeys) {
     ak = allowableKeys;
     map = map;
  }
  public Object get(Object key) {
    if (!ak.contains(key)) return null;
    return map.get(key);
  }
}

- ControlAltDel

---

如果使用新的映射而不是视图，那么ak.contains的时间复杂度为O(n)而不是O(1)，这可能会成为一个问题。 - assylias

结果的 MapView 不是 HashMap，甚至不是 Map。 - tkruse

Answer 6

不必查找所有键，您可以循环遍历列表并检查HashMap是否包含映射。然后创建一个新的HashMap，其中包含已过滤的条目：

List<String> keys = Arrays.asList('a', 'c', 'e');

Map<String, String> old = new HashMap<>();
old.put('a', 'aa');
old.put('b', 'bb');
old.put('c', 'cc');
old.put('d', 'dd');
old.put('e', 'ee');

// only use an inital capacity of keys.size() if you won't add
// additional entries to the map; anyways it's more of a micro optimization
Map<String, String> newMap = new HashMap<>(keys.size(), 1f);

for (String key: keys) {
    String value = old.get(key);
    if (value != null) newMap.put(key, value);
}

- helpermethod

---

不能使用new作为变量名。 - Bubletan

@Bubletan 没错，将变量重命名为newMap。 - helpermethod

@helpermethod，你应该使用new HashMap<>(keys.size(), 1f);，否则会使用负载因子0.75，并且地图可能会被重新调整大小。 - assylias

ìf (value != null) 不是HashMap中 containsKey 的有效替代。你可以写成 hashMap.put("key", null)，然后你的 if (value != null) 测试就会被欺骗。尽管如此，这种设计在现阶段已经非常频繁了，但在Map中设置null值似乎本来就不是一个好主意。 - GPI

有些情况下，你可能想在HashMap中存储null值（你仍然可以验证它是否包含键来区分具有null值的映射或特定键的缺失值）……例如当你使用它来缓存计算密集型函数的结果时（结果可能为null）……这样是可行的。 - aregnier

Answer 7

你甚至可以种植自己的：

public class FilteredMap<K, V> extends AbstractMap<K, V> implements Map<K, V> {

    // The map I wrap.
    private final Map<K, V> map;
    // The filter.
    private final Set<K> filter;

    public FilteredMap(Map<K, V> map, Set<K> filter) {
        this.map = map;
        this.filter = filter;
    }

    @Override
    public Set<Entry<K, V>> entrySet() {
        // Make a new one to break the bond with the underlying map.
        Set<Entry<K, V>> entries = new HashSet<>(map.entrySet());
        Set<Entry<K, V>> remove = new HashSet<>();
        for (Entry<K, V> entry : entries) {
            if (!filter.contains(entry.getKey())) {
                remove.add(entry);
            }
        }
        entries.removeAll(remove);
        return entries;
    }

}

public void test() {
    Map<String, String> map = new HashMap<>();
    map.put("1", "One");
    map.put("2", "Two");
    map.put("3", "Three");
    Set<String> filter = new HashSet<>();
    filter.add("1");
    filter.add("2");
    Map<String, String> filtered = new FilteredMap<>(map, filter);
    System.out.println(filtered);

}

如果你担心所有的复制，也可以使用过滤后的Set和Iterator。

public interface Filter<T> {

    public boolean accept(T t);
}

public class FilteredIterator<T> implements Iterator<T> {

    // The Iterator
    private final Iterator<T> i;
    // The filter.
    private final Filter<T> filter;
    // The next.
    private T next = null;

    public FilteredIterator(Iterator<T> i, Filter<T> filter) {
        this.i = i;
        this.filter = filter;
    }

    @Override
    public boolean hasNext() {
        while (next == null && i.hasNext()) {
            T n = i.next();
            if (filter.accept(n)) {
                next = n;
            }
        }
        return next != null;
    }

    @Override
    public T next() {
        T n = next;
        next = null;
        return n;
    }
}

public class FilteredSet<K> extends AbstractSet<K> implements Set<K> {

    // The Set
    private final Set<K> set;
    // The filter.
    private final Filter<K> filter;

    public FilteredSet(Set<K> set, Filter<K> filter) {
        this.set = set;
        this.filter = filter;
    }

    @Override
    public Iterator<K> iterator() {
        return new FilteredIterator(set.iterator(), filter);
    }

    @Override
    public int size() {
        int n = 0;
        Iterator<K> i = iterator();
        while (i.hasNext()) {
            i.next();
            n += 1;
        }
        return n;
    }

}

public class FilteredMap<K, V> extends AbstractMap<K, V> implements Map<K, V> {

    // The map I wrap.
    private final Map<K, V> map;
    // The filter.
    private final Filter<K> filter;

    public FilteredMap(Map<K, V> map, Filter<K> filter) {
        this.map = map;
        this.filter = filter;
    }

    @Override
    public Set<Entry<K, V>> entrySet() {
        return new FilteredSet<>(map.entrySet(), new Filter<Entry<K, V>>() {

            @Override
            public boolean accept(Entry<K, V> t) {
                return filter.accept(t.getKey());
            }

        });
    }

}

public void test() {
    Map<String, String> map = new HashMap<>();
    map.put("1", "One");
    map.put("2", "Two");
    map.put("3", "Three");
    Set<String> filter = new HashSet<>();
    filter.add("1");
    filter.add("2");
    Map<String, String> filtered = new FilteredMap<>(map, new Filter<String>() {

        @Override
        public boolean accept(String t) {
            return filter.contains(t);
        }
    });
    System.out.println(filtered);

}

- OldCurmudgeon

Answer 8

如果您的键有顺序，可以使用TreeMap。

看看TreeMap.subMap()。

但是，它不允许您使用列表来实现这一点。

- user1717259

---

@OP指定了一个HashMap，而你在谈论TreeMap。 - ControlAltDel

Answer 9

复制地图并删除不在列表中的所有键：

Map map2 = new Hashmap(map);
map2.keySet().retainAll(keysToKeep);

- kapex

Answer 10

你可以在返回的 K HashMap 上使用 clone() 方法。

就像这样：

import java.util.HashMap;

public class MyClone {    
     public static void main(String a[]) {    
        Map<String, HashMap<String, String>> hashMap = new HashMap<String, HashMap<String, String>>();    
        Map hashMapCloned = new HashMap<String, String>();    

        Map<String, String> insert = new HashMap<String, String>();

        insert.put("foo", "bar");
        hashMap.put("first", insert);

        hashMapCloned.put((HashMap<String, String>) hashMap.get("first").clone());

    }    
}

可能会有一些语法错误，因为我还没有测试过，但是尝试着像这样做。

- Bruno Paulino

---

最好使用超类型/接口来声明变量，而不是具体类。 - KrishPrabakar