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

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?

1 Like

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.

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?

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).

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.

2 Likes

I'm also having difficulty understanding this trait. The docs and the commenters above are explaining it within a context of HashMap. Can someone explain in plain English how this trait can be used for other purposes ? An example where only Borrow would work but AsRef wouldn't would be greatly appreciated.

1 Like

The Borrow trait was designed specifically for the use case of using a borrowed key to look up an entry in a HashMap, HashSet, BTreeMap, or other such container. As such, it's hard to discuss outside of this use case.

AsRef doesn't work for this use case because it lacks the additional restrictions on traits like Hash and Ord. For example, String implements AsRef<[u8]>, but String and u8 don't have compatible Hash implementations, so it would not work to use an &[u8] key to query a HashSet<String>.

4 Likes

This topic was automatically closed 7 days after the last reply. New replies are no longer allowed.