HashMap entries and the Clone trait

[bllhastings]

Do the Key/Value entries need to implement Clone trait to be inserted into HashMap? If so where is it specified as a trait bound?

Thanks in advance.

[quinedot]

@bllhastings

If so where is it specified as a trait bound?

If we look at the documentation for HashMap and search for clone, we find:

impl<K, V, S> Clone for HashMap<K, V, S> where
    K: Clone,
    V: Clone,
    S: Clone,

and

impl<T> ToOwned for T where
    T: Clone,

The former tells us that we can only clone a HashMap if the key, value, and hasher state types are also Clone. The default hasher state is linked at the top, and it does implement Clone.

The former is a blanket implementation not specific to HashMap; it's the only place ToOwned appears here, so we know that HashMap is ToOwned only if it is Clone.

Altogether, we can conclude that the key and value types need be Clone only for Clone and ToOwned methods, and not insert.

---

Alternative approach: find insert and then scroll up to find its impl block. The required bounds are

impl<K, V, S> HashMap<K, V, S>where
    K: Eq + Hash,
    S: BuildHasher,

so the keys do have some constraints in order for you to insert (but Clone isn't one of them). The values do not, other than the implicit bound of being Sized.

If we get implied bounds on structs, you'd have to check the struct definition for bounds too; HashMap has none beyond the implicit Sized bounds.

[steffahn]

Another approach to answering such a straightforward question is to test it, i.e. “ask the compiler” if you will, with a minimal code example. Though that’s still not quite trivial without some basic Rust experience, in detail:

---

Of course, for testing this in code, we would need to know (or even worse, construct^[1]) a type that can’t be cloned; and for the key type especially one that’s still supporting Eq+Hash… or do we? Actually, not really, generic functions can be super useful to find out what compiles or not, without the need for cooking up with concrete types. We start with

use std::collections::HashMap;

fn test<Key, Value>(m: HashMap<Key, Value>) {}

which compiles? Won’t we need the Hash trait for a HashMap? Maybe the compiler doesn’t tell us the truth and this function is unusable? Here’s a concrete type that doesn’t implement any of the relevant traits (Hash/Eq/Clone).

struct ConcreteType;

and this concrete program does work:

fn main() {
    let x = HashMap::<ConcreteType, ConcreteType>::new();
    test(x);
}

Rust Playground

So the compiler wasn’t lying, and it really isn’t necessary to have Hash here. In order to be called, A generic function always^[2] only requires the kind of conditions that are explicit in its signature. It’s important to understand one convention about trait bounds on data structures: In Rust, we often put minimal trait bounds on the data structure itself, and only further strengthen the bounds on each method that actually uses the trait functionality with that bound. A HashMap doesn’t need hashing until you actually start inserting something!

So… inserting something now:

use std::collections::HashMap;

fn test2<Key, Value>(m: HashMap<Key, Value>, k: Key, v: Value) {
    let mut map = m;
    map.insert(k, v);
}

fails as expected

error[E0599]: the method `insert` exists for struct `HashMap<Key, Value>`, but its trait bounds were not satisfied
 --> src/lib.rs:5:9
  |
5 |     map.insert(k, v);
  |         ^^^^^^
  |
  = note: the following trait bounds were not satisfied:
          `Key: Eq`
          `Key: Hash`
help: consider restricting the type parameters to satisfy the trait bounds
  |
3 | fn test2<Key, Value>(m: HashMap<Key, Value>, k: Key, v: Value) where Key: Eq, Key: Hash {
  |                                                                ++++++++++++++++++++++++

but now, we can follow the compiler suggestion and get

use std::collections::HashMap;
use std::hash::Hash;

fn test2<Key, Value>(m: HashMap<Key, Value>, k: Key, v: Value)
where
    Key: Eq,
    Key: Hash,
{
    let mut map = m;
    map.insert(k, v);
}

which does compile. Result of “asking the compiler”? We do not need Clone to insert something into a HashMap.

---

Of course, if we want to be able to do more, we might need the Clone bounds after all. E.g. cloning the whole map?

use std::collections::HashMap;
use std::hash::Hash;

fn test2<Key, Value>(m: HashMap<Key, Value>, k: Key, v: Value)
where
    Key: Eq,
    Key: Hash,
{
    let mut map = m;
    map.insert(k, v);
    let map2 = map.clone();
}

error[E0599]: the method `clone` exists for struct `HashMap<Key, Value>`, but its trait bounds were not satisfied
  --> src/lib.rs:11:20
   |
11 |     let map2 = map.clone();
   |                    ^^^^^ method cannot be called on `HashMap<Key, Value>` due to unsatisfied trait bounds
   |
   = note: the following trait bounds were not satisfied:
           `Key: Clone`
           which is required by `HashMap<Key, Value>: Clone`
           `Value: Clone`
           which is required by `HashMap<Key, Value>: Clone`
help: consider restricting the type parameters to satisfy the trait bounds
   |
7  |     Key: Hash, Key: Clone, Value: Clone
   |              ~~~~~~~~~~~~~~~~~~~~~~~~~~

now the compiler tells us, we need to add Key: Clone, Value: Clone (which – if you try it – will make the code work again).

---

Side note, I’m writing Key: Eq, Key: Hash, as that’s the automatic compiler suggestion, but IMO Key: Eq + Hash, would be nicer to read. Whether to put that in a where clause or on the parameter is a matter of taste, and perhaps of how long the function signature already is.

---

1. which is worse, since this is supposed to be a quick and simple way of finding an answer to our question, but defining a type and implementing a bunch of traits takes effort ↩︎

2. with some minor exceptions around impl Trait return types and auto-traits ↩︎