Lvalue to rvalue reference binding

Insert(key, Value()); // Compiler error here

key here is Key&& key - this is an lvalue! It has a name, and you can take its address. It's just that type of that lvalue is "rvalue reference to Key".

You need to pass in an rvalue, and for that you need to use std::move:

Insert(std::move(key), Value()); // No compiler error any more

I can see why this is counter-intuitive! But once you distinguish between and rvalue reference (which is a reference bound to an rvalue) and an actual rvalue, it becomes clearer.

Edit: the real problem here is using rvalue references at all. It makes sense to use them in a function template where the type of the argument is deduced, because this allows the argument to bind to either an lvalue reference or an rvalue reference, due to reference collapsing rules. See this article and video for why: http://isocpp.org/blog/2012/11/universal-references-in-c11-scott-meyers

However, in this case the type of Key is not deduced when the function is called, as it has already been determined by the class when you instantiated FastHash<std::string, ... >. Thus you really are prescribing the use of rvalue references, and thus using std::move fixes the code.

I would change your code to that the parameters are take by value:

template <typename Key, typename Value, typename HashFunction, typename Equals>
Value& FastHash<Key, Value, HashFunction, Equals>::operator[](Key key)
{
    //  Some code here...

    Insert(std::move(key), Value());

    //   More code here.
}

template <typename Key, typename Value, typename HashFunction, typename Equals>
void FastHash<Key, Value, HashFunction, Equals>::Insert(Key key, Value value)
{
    // ...
}

Don't worry too much about extra copies due to use of value arguments - these are frequently optimised out by the compiler.