Cache implementation in Rust
You don't need to have the where clause on your struct. General, rust coders prefer to only restrict the impl blocks and not the structs.

You can avoid Clone, by unpacking the Entry enum, like so:

fn get(&amp;mut self, input: U) -&gt; &amp;W {
    use std::collections::hash_map::Entry;
    match self.values.entry(input) {
        Entry::Occupied(entry) =&gt; entry.into_mut(),
        Entry::Vacant(entry) =&gt; {
            let value = (self.calculator)(entry.key());
            entry.insert(value)
        }
    }
}   


This is, in fact, close to how or_insert_with is implemented.  

Note that this calls the function with &amp;U not U. Your calculator cannot take ownership of the key if you also plan to put into the hashmap. This is awkward for your code because it is using &amp;str as the keys. Hence the type passed to the calculator is &amp;&amp;str. We can resolve this by using the borrow trait. The Borrow traits knows that it can convert &amp;&amp;str to &amp;str, so we could implement it as follows.

// Leave the struct unconstrained
struct Cache&lt;T, U, W&gt; {
    calculator: T,
    values: HashMap&lt;U, W&gt;,
}

// The impl block only constrains for Eq + Hash of the keys.
impl&lt;T, U, W&gt; Cache&lt;T, U, W&gt;
    where 
          U: Eq + Hash
         {

    fn new(calculator: T) -&gt; Cache&lt;T, U, W&gt; {
        Cache {
            calculator,
            values: HashMap::new(),
        }
    }

    // We take a new type parameter, Y.
    // The calculation function takes &amp;Y as a parameter
    // It does not need to be sized because we only use references to it.  
    fn get&lt;Y:?Sized&gt;(&amp;mut self, input: U) -&gt; &amp;W 
        where 
             // Our calculator must take a reference to Y.
             T: Fn(&amp;Y) -&gt; W,
             // The borrow trait will let us convert a &amp;U to a &amp;Y
             U: std::borrow::Borrow&lt;Y&gt; {
        use std::collections::hash_map::Entry;
        match self.values.entry(input) {
            Entry::Occupied(entry) =&gt; entry.into_mut(),
            Entry::Vacant(entry) =&gt; {
                let value = (self.calculator)(entry.key().borrow());
                entry.insert(value)
            }
        }
    }   
}