# An extension of HashMap's use of Borrow **URL:** \ **Category:** libs\ **Created:** [November 14, 2016, 9:05pm UTC](https://internals.rust-lang.org/t/an-extension-of-hashmaps-use-of-borrow/4384 "2016-11-14T21:05:57Z")\ **Posts on this page:** 11\ **Page:** 1
**Author:** ![bluss](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/bluss/32/2264_2.png) [@bluss](https://internals.rust-lang.org/u/bluss)\ **Post date:** [November 14, 2016, 9:05pm UTC](https://internals.rust-lang.org/t/an-extension-of-hashmaps-use-of-borrow/4384/1 "2016-11-14T21:05:57Z")
Here’s a prototype of an extension of what `HashMap::get` is using `Borrow` for. ### What Problem does it Solve? You have a hash table with key type `(String, String)` and you want to do a table lookup without allocating strings. It allows lookup not using a custom type like `Pair(&str, &str)` (or even using the `(&str, &str)` tuple if libstd buys into it). ### Implementation Two things are needed: The substitute key (`Q`) must be hashable (like the `K` type), and there must be a `K` to `Q` equality function (a function to avoid the limitations of Borrow). ```rust /// Key lookup trait. /// /// This trait allows hash table lookup to be customized. /// It has one blanket implementation that uses the regular `Borrow` solution, /// just like `HashMap` and `BTreeMap` do, so that you can pass `&str` to lookup /// into a map with `String` keys and so on. /// /// # Contract /// /// The implementor must hash like `K`. pub trait Lookup : Hash { /// Compare self to `key` and return `true` if they are equal. fn equal(&self, key: &K) -> bool; } impl Lookup for Q where Q: Eq + Hash, K: Borrow, { fn equal(&self, key: &K) -> bool { *self == *key.borrow() } } ``` Implementation in a custom hash map here: [https://github.com/bluss/ordermap/pull/10/files](https://github.com/bluss/ordermap/pull/10/files) (API for `.get()` was identical to std’s HashMap). The trait could also be called `Equivalent`. ### Drawbacks - Type inference regressions? (Don’t know) - Ad hoc. ---
**Author:** ![withoutboats](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/withoutboats/32/4560_2.png) [@withoutboats](https://internals.rust-lang.org/u/withoutboats)\ **Post date:** [November 14, 2016, 9:35pm UTC](https://internals.rust-lang.org/t/an-extension-of-hashmaps-use-of-borrow/4384/2 "2016-11-14T21:35:13Z")
Why is this bounded by Hash? What about BTreeMap? ---
**Author:** ![bluss](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/bluss/32/2264_2.png) [@bluss](https://internals.rust-lang.org/u/bluss)\ **Post date:** [November 14, 2016, 10:06pm UTC](https://internals.rust-lang.org/t/an-extension-of-hashmaps-use-of-borrow/4384/3 "2016-11-14T22:06:11Z")
It was just made for a hash table first. You’re right that removing the Hash bound makes it easy to expand to use by BTreeMap. ---
**Author:** ![eddyb](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/eddyb/32/8411_2.png) [@eddyb](https://internals.rust-lang.org/u/eddyb)\ **Post date:** [November 15, 2016, 1:28am UTC](https://internals.rust-lang.org/t/an-extension-of-hashmaps-use-of-borrow/4384/4 "2016-11-15T01:28:22Z")
> [@bluss](#): > > The trait could also be called `Equivalent`. We used to have a trait called `Equiv`. I wonder if `T: PartialEq` is enough here nowadays. ---
**Author:** ![bluss](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/bluss/32/2264_2.png) [@bluss](https://internals.rust-lang.org/u/bluss)\ **Post date:** [November 15, 2016, 10:00am UTC](https://internals.rust-lang.org/t/an-extension-of-hashmaps-use-of-borrow/4384/5 "2016-11-15T10:00:09Z")
`PartialEq` would be enough, but the separate `equal` method is needed to make the default blanket impl that uses `Borrow`. ---
**Author:** ![fitzgen](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/fitzgen/32/3625_2.png) [@fitzgen](https://internals.rust-lang.org/u/fitzgen)\ **Post date:** [November 15, 2016, 3:41pm UTC](https://internals.rust-lang.org/t/an-extension-of-hashmaps-use-of-borrow/4384/6 "2016-11-15T15:41:04Z")
I ran into this exact issue the other day. Frustrating not being able to avoid the allocation, despite all the care that goes into avoiding double lookups. Big plus one for this from me 🙂 ---
**Author:** ![fitzgen](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/fitzgen/32/3625_2.png) [@fitzgen](https://internals.rust-lang.org/u/fitzgen)\ **Post date:** [November 15, 2016, 5:52pm UTC](https://internals.rust-lang.org/t/an-extension-of-hashmaps-use-of-borrow/4384/7 "2016-11-15T17:52:43Z")
Related: It would also be great to extend the entry API to take a type `L` where `L: ToOwned, Key: Borrow` rather than a `Key` directly so that if the key is already in the map, we can avoid an unnecessary allocation. ---
**Author:** ![Amanieu](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/amanieu/32/4095_2.png) [@Amanieu](https://internals.rust-lang.org/u/Amanieu)\ **Post date:** [November 15, 2016, 7:00pm UTC](https://internals.rust-lang.org/t/an-extension-of-hashmaps-use-of-borrow/4384/8 "2016-11-15T19:00:59Z")
I had something like this in mind, which allows a key to be extracted from any type. This allows you to place bounds (such as `Eq + Hash` for `HashMap` and `Ord` for `BTreeMap`) directly on the key type, and keeps the key extraction mechanism independent of any particular collection type. This example code makes use of associated type constructors and specialization, but it could be made to work without those features. ```rust pub trait ExtractKey { type Key<'a>; fn extract_key(&self) -> Self::Key; } // Default implementation which just returns self impl ExtractKey for T { default type Key<'a> = &'a T; default fn extract_key(&self) -> &T { self } } struct Example(String, i32, f64); impl ExtractKey for Example { // Since Key is generic over lifetimes, we can return fields in an // arbitrary order, which can be used to control BTreeMap ordering. type Key<'a> = (f64, &'a str); fn extract_key(&self) -> (&'a str, f64) { (self.2, &self.0) } } ``` ---
**Author:** ![danieldg](https://avatars.discourse-cdn.com/v4/letter/d/3bc359/32.png) [@danieldg](https://internals.rust-lang.org/u/danieldg)\ **Post date:** [September 4, 2017, 2:35am UTC](https://internals.rust-lang.org/t/an-extension-of-hashmaps-use-of-borrow/4384/9 "2017-09-04T02:35:14Z")
I have a partial implementation of this for HashMap/BTreeMap, although it’s named differently (I didn’t see this thread until I was done). Patch at [https://github.com/rust-lang/rust/commit/e3ec035c338927f277ca7d4509587185e6cac1f1](https://github.com/rust-lang/rust/commit/e3ec035c338927f277ca7d4509587185e6cac1f1) - not sure about the type or method names, and it needs a few more added (the Range ops on BTree, for one). ---
**Author:** ![kamalmarhubi](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/kamalmarhubi/32/1385_2.png) [@kamalmarhubi](https://internals.rust-lang.org/u/kamalmarhubi)\ **Post date:** [September 4, 2017, 8:23pm UTC](https://internals.rust-lang.org/t/an-extension-of-hashmaps-use-of-borrow/4384/10 "2017-09-04T20:23:22Z")
Related urlo post from today: [https://users.rust-lang.org/t/hashmap-with-tuple-keys/12711/2](https://users.rust-lang.org/t/hashmap-with-tuple-keys/12711/2) ---
**Author:** ![bluss](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/bluss/32/2264_2.png) [@bluss](https://internals.rust-lang.org/u/bluss)\ **Post date:** [March 25, 2019, 8:27am UTC](https://internals.rust-lang.org/t/an-extension-of-hashmaps-use-of-borrow/4384/11 "2019-03-25T08:27:22Z")
Closed on March 25, 2019, 8:27am UTC This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.