# Extend HashSet with \`remove\_by\_hash\` & \`find\_by\_hash\`

**URL:** <https://internals.rust-lang.org/t/extend-hashset-with-remove-by-hash-find-by-hash/19308>\
**Category:** language design\
**Created:** [August 8, 2023, 3:23pm UTC](https://internals.rust-lang.org/t/extend-hashset-with-remove-by-hash-find-by-hash/19308 "2023-08-08T15:23:31Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![Zarathustra2](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/zarathustra2/32/11161_2.png) [@Zarathustra2](https://internals.rust-lang.org/u/Zarathustra2)\
**Post date:** [August 8, 2023, 3:23pm UTC](https://internals.rust-lang.org/t/extend-hashset-with-remove-by-hash-find-by-hash/19308/1 "2023-08-08T15:23:31Z")

</div>

Given the following struct:

```rust
pub struct WebsocketConnection {
   session_id: usize,
   tx: UnboundedSender<Message>,
   user: Option<User>,
   // More fields
}

impl Hash for WebsocketConnection {
    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
        self.session_id.hash(state);
    }
}

```

Since the one field being used for creating the hash is the `session_id` it would be nice if I can retrieve the `WebsocketConnection` from a HashSet only by the `session_id`. The current workaround if you only have the `session_id` is to create a temporary `WebsocketConnection` and then pass that to `remove`/`get`/`contains` which seems kinda annoying. Or instead of using a HashSet one could use `HashMap<session_id, WebsocketConnection>`

C++ has a similar feature: [std::unordered\_set\<Key,Hash,KeyEqual,Allocator\>::find - cppreference.com](https://en.cppreference.com/w/cpp/container/unordered_set/find)

I am wondering if HashSet should be extended with function(s) that allow finding/removing values from a HashSet by its hash or maybe instead allow to find/remove by anything that implements the trait Hash. That way one could write a custom wrapper type for `session_id` and only pass that to remove/find an element.

Best regards, Dario

---

<div class="post-metadata">

**Author:** ![jrose](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/jrose/32/9591_2.png) [@jrose](https://internals.rust-lang.org/u/jrose)\
**Post date:** [August 8, 2023, 3:35pm UTC](https://internals.rust-lang.org/t/extend-hashset-with-remove-by-hash-find-by-hash/19308/2 "2023-08-08T15:35:37Z")

</div>

You can do this today! That’s what the Borrow trait is about in the signature of all those HashSet functions.

---

<div class="post-metadata">

**Author:** ![Zarathustra2](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/zarathustra2/32/11161_2.png) [@Zarathustra2](https://internals.rust-lang.org/u/Zarathustra2)\
**Post date:** [August 8, 2023, 3:41pm UTC](https://internals.rust-lang.org/t/extend-hashset-with-remove-by-hash-find-by-hash/19308/3 "2023-08-08T15:41:30Z")

</div>

Oh I must have misread the the type signature then, let me retake a look. Thanks for pointing that out! 🙂

---

<div class="post-metadata">

**Author:** ![kpreid](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/kpreid/32/8484_2.png) [@kpreid](https://internals.rust-lang.org/u/kpreid)\
**Post date:** [August 8, 2023, 4:24pm UTC](https://internals.rust-lang.org/t/extend-hashset-with-remove-by-hash-find-by-hash/19308/4 "2023-08-08T16:24:24Z")

</div>

Demo:

```rust
use std::hash::Hash;

#[derive(Eq, Hash, PartialEq)]
struct SessionId(pub usize);

pub struct WebsocketConnection {
   session_id: SessionId,
   other_stuff: String,
}

impl PartialEq for WebsocketConnection {
    fn eq(&self, other: &Self) -> bool {
        self.session_id == other.session_id
    }
}
impl Eq for WebsocketConnection {}
impl Hash for WebsocketConnection {
    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
        self.session_id.hash(state);
    }
}

impl std::borrow::Borrow<SessionId> for WebsocketConnection {
    fn borrow(&self) -> &SessionId {
        &self.session_id
    }
}

#[test]
fn borrowing() {
    let set = std::collections::HashSet::from([
        WebsocketConnection {
            session_id: SessionId(10),
            other_stuff: String::from("whatever"),
        }
    ]);
    
    assert!(set.get(&SessionId(10)).is_some());
}

```

The `SessionId` type is just for a little extra type-safety: it would work the same with `Borrow<usize>`.

By the way, I would personally choose the `HashMap` instead, unless I made sure it was _impossible_ to construct an unrelated `WebsocketConnection` with duplicate session ID (e.g. via private `static` atomic counter for assigning IDs). It can be extremely confusing to have values which `Eq + Hash` the same but are functionally different.

---

<div class="post-metadata">

**Author:** ![Zarathustra2](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/zarathustra2/32/11161_2.png) [@Zarathustra2](https://internals.rust-lang.org/u/Zarathustra2)\
**Post date:** [August 8, 2023, 8:41pm UTC](https://internals.rust-lang.org/t/extend-hashset-with-remove-by-hash-find-by-hash/19308/5 "2023-08-08T20:41:02Z")

</div>

Ah perfect, now I get it. Thanks for providing an example!

---

<div class="post-metadata">

**Author:** ![canndrew](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/canndrew/32/1676_2.png) [@canndrew](https://internals.rust-lang.org/u/canndrew)\
**Post date:** [August 10, 2023, 4:39am UTC](https://internals.rust-lang.org/t/extend-hashset-with-remove-by-hash-find-by-hash/19308/6 "2023-08-10T04:39:30Z")

</div>

> By the way, I would personally choose the HashMap instead, unless I made sure it was impossible to construct an unrelated WebsocketConnection with duplicate session ID (e.g. via private static atomic counter for assigning IDs). It can be extremely confusing to have values which Eq + Hash the same but are functionally different.

I agree. It feels like an abuse of `Eq` and `Hash` to implement them like this.

That said, the situation OP is in is one I've seen come up a lot: You have a table of values indexed by some key but the key is stored in the value. You _can_ just clone the key and use a `HashMap`, but that wastes space and makes it possible to represent invalid states where the two keys don't match. It would be better if there was a separate type for this. You can implement that type using a `HashSet` of a private type which has those questionable `Eq + Hash` impls:

```rust
pub struct OwnedKeyHashMap<K, V>
where
    V: Borrow<K>,
{
    set: HashSet<Field<K, V>>,
}

struct Field<K, V>
where
    V: Borrow<K>,
{
    _ph: PhantomData<K>,
    value: V,
}

impl<K, V> Hash for Field<K, V>
where
    V: Borrow<K>,
    K: Hash,
{
    fn hash<H: Hasher>(&self, hasher: &mut H) {
        self.value.borrow().hash(hasher)
    }
}

impl<K, V> PartialEq for Field<K, V>
where
    V: Borrow<K>,
    K: PartialEq,
{
    pub fn eq(&self, other: &Field<K, V>) -> bool {
        self.borrow() == other.borrow()
    }
}

impl<K, V> Eq for Field<K, V>
where
    V: Borrow<K>,
    K: Eq,
{}

impl<K, V> Borrow<K> for Field<K, V>
where
    V: Borrow<K>,
{
    fn borrow(&self) -> &K {
        self.value.borrow()
    }
}

impl OwnedKeyHashMap<K, V>
where
    V: Borrow<K>,
    K: Eq + Hash,
{
    pub fn new() -> OwnedKeyHashMap<K, V> {
        OwnedKeyHashMap {
            set: HashSet::new(),
        }
    }

    pub fn get(key: &K) -> Option<&V> {
        Some(&self.set.get(key)?.value)
    }

    pub fn insert(&mut self, value: V) -> Option<V> {
        let field = Field {
            value,
            _ph: PhantomData,
        };
        let prev_field = self.set.insert(field)?;
        Some(prev_field.value)
    }
}

```

---

<div class="post-metadata">

**Author:** ![system](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/system/32/14092_2.png) [@system](https://internals.rust-lang.org/u/system)\
**Post date:** [November 8, 2023, 4:39am UTC](https://internals.rust-lang.org/t/extend-hashset-with-remove-by-hash-find-by-hash/19308/7 "2023-11-08T04:39:54Z")

</div>

Closed on November 8, 2023, 4:39am UTC

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