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.