As above, will break for binary keys.

I think the only reasonable solution is to:

* Parameterize the key encoding function.
* Default to allowing `str`/`bytes` directly through, or issuing a warning then encoding `unicode` values with `utf-8`.
* Always return keys as `bytes`.