CODEWITHSUNDEEP
rust
Marijn van Vliet
Marijn van Vliet

Reputation: 5399

In Rust, how do I create a HashSet from the keys of a HashMap?

I have two HashMaps and want to compute the intersection of the keys. Is it possible to construct a HashSet out of whatever HashMap::keys() returns? For example:

use std::collections::{HashSet, HashMap};

fn main() {
    let mut map1: HashMap<i64, i64> = HashMap::new();
    let mut map2: HashMap<i64, i64> = HashMap::new();

    // Add some values into the HashMaps for demonstration
    map1.insert(1, 10);
    map1.insert(5, 50);
    map2.insert(3, 30);
    map2.insert(5, 50);

    let set1: HashSet<i64> = HashSet::from(map1.keys());  // How to do this?
    let set2: HashSet<i64> = HashSet::from(map2.keys());  // How to do this?

    let set3 = set1.intersection(&set2); // What I'm looking to accomplish
    // set3 should contain [5], as this is the one key shared by the two HashMaps
}

Upvotes: 18

Views: 8432

Answers (2)

Matthieu M.
Matthieu M.

Reputation: 299750

The simple solution

Your code only needs a few tweaks to actually compile (see Playground):

use std::collections::{HashSet, HashMap};

fn main() {
    let mut map1 = HashMap::new();
    let mut map2 = HashMap::new();

    // Add some values into the HashMaps for demonstration
    map1.insert(1, 10);
    map1.insert(5, 50);
    map2.insert(3, 30);
    map2.insert(5, 50);

    let set1: HashSet<i64> = map1.keys().cloned().collect();
    let set2: HashSet<i64> = map2.keys().cloned().collect();

    let set3 = set1.intersection(&set2);
    println!("{:?}", set3);
}

In particular, note map1.keys().cloned().collect():

  • HashMap<K, V>::keys() returns an Iterator<Item = &'a K>,
  • .cloned() transforms that to an Iterator<Item = K>,
  • .collect() builds a collection from that, since HashSet implements the FromIterator trait.

However, this is not very efficient:

  • Complexity wise: O(map1.size() + map2.size()).
  • Memory wise: potentially large allocations.

The efficient solution

Implement intersection directly on the keys of HashMap.

Upvotes: 16

Peter Hall
Peter Hall

Reputation: 58715

You just need to collect into the HashSet:

let set1: HashSet<i64> = map1.keys().copied().collect(); 
let set2: HashSet<i64> = map2.keys().copied().collect();

Using copied() will dereference the keys and copy them, since you want a HashSet<i64> not a HashSet<&i64>

Upvotes: 7

Related Questions