How do I use the Entry API with an expensive key that is only constructed if the Entry is Vacant?

You cannot, safely. This is a limitation of the current entry API, and there's no great solution. The anticipated solution is the "raw" entry API. See Stargateur's answer for an example of using it.

The only stable solution using the Entry API is to always clone the key:

map.entry(key.clone()).or_insert(some_value);

Outside of the Entry API, you can check if the map contains a value and insert it if not:

if !map.contains_key(&key) {
    map.insert(key.clone(), some_value);
}

map.get(&key).expect("This is impossible as we just inserted a value");

See also:

• [Pre-RFC] Abandonning Morals In The Name Of Performance: The Raw Entry API
• WIP: add raw_entry API to HashMap (50821)
• Extend entry API to work on borrowed keys. (1769)
• Add HashMap.entry_or_clone() method (1203)

For non-entry based solutions, see:

• How to avoid temporary allocations when using a complex key for a HashMap?
• How to implement HashMap with two keys?

In nightly Rust, you can use the unstable raw_entry_mut() feature that allows this:

Creates a raw entry builder for the HashMap.

[...]

Raw entries are useful for such exotic situations as:

• Deferring the creation of an owned key until it is known to be required

In stable Rust, you can add the hashbrown crate which has the same API but stable. The hashbrown crate is actually the underlying implementation of the standard library's hashmap.

Example:

#![feature(hash_raw_entry)]
use std::collections::HashMap;

#[derive(Hash, PartialEq, Eq, Debug)]
struct NoCopy {
    foo: i32,
}

impl Clone for NoCopy {
    fn clone(&self) -> Self {
        println!("Clone of: {:?}", self);
        Self { foo: self.foo }
    }
}

fn main() {
    let no_copy = NoCopy { foo: 21 };

    let mut map = HashMap::new();

    map.raw_entry_mut()
        .from_key(&no_copy)
        .or_insert_with(|| (no_copy.clone(), 42));

    map.raw_entry_mut()
        .from_key(&no_copy)
        .or_insert_with(|| (no_copy.clone(), 84));

    println!("{:#?}", map);
}

Applied to your original example:

fn get_or_create<K>(&mut self, key: K) -> &mut Foo
where
    K: AsRef<str> + Into<String>,
{
    self.map
        .raw_entry_mut()
        .from_key(key.as_ref())
        .or_insert_with(|| (key.into(), Foo))
        .1
}