How to understand the example of the Borrow trait in the Book?


#1

Hi, I have some troubles in understanding the use of the Borrow trait.

In the first version of the Book section 4.10, following codes are presented to demonstrate the usage of Borrow trait:

fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V>
    where K: Borrow<Q>,
          Q: Hash + Eq

where K is the key type.
Say K is String, &Q is &str, and String impled Borrow, which means inside the content of fn get, there must a place <String as Borrow<str>>::borrow() is called. But why?

Instinctively, shouldn’t the parameter k be transferred into String (in some way) and calculate the hash value (from the temp String), then compared to the inner stored hash value that has already been calculated from the String-type key values?


#2

This is to avoid a needless allocation (of a String in this example) to do a lookup. To hash and then compare equality, the difference between an owned string and a borrowed one (a slice) is immaterial.


#3

So when calling get, the inner stored key (with type String) will be borrowed as &str, from which the hash is calculated and compared with the hash calculated from the parameter?


#4

It’s an implementation choice whether you store hashes of the keys or always compute them on the fly. In the case of HashMap, it stores the hashes. The lookup key is going be hashed and then compared for equality with the candidate stored Strings (which will be borrowed to a &str for the equality check).


#5

An important fact that isn’t explicitly mentioned in the book is this requirement from the Borrow documentation:

If you are implementing Borrow and both Self and Borrowed implement Hash, Eq, and/or Ord, they must produce the same result.

This isn’t enforced by the type system (so you can’t rely on it for memory safety), but it is a documented requirement for all implementers of the Borrow trait. This means that if you have a String and an &str you can hash both of them directly, without first converting them to have the same type.