U64 -> T, T -> u64 w/o storing twice

#1

We have T: Hash + Eq

Furthermore, we want to be able to maintain a set and do u64 -> T and T -> u64.

One way to do this is

pub struct Foo {
  a: HashMap<u64, T>,
  b: HashMap<T, u64>,
}

However, this requires storing every T twice. Is there a way to do this while storing each T only once ?

#2

Arc<T>?

#3

If T is small and cheap to copy (eg i32) then that's probably the best representation. If T is large/expensive to copy, then you could make it Foo<Arc<T>> - ie, make it a requirement in the API that T has a cheap Clone implementation (in time and space). Or just make it use Arc/Rc itself, though that will be much more expensive if T doesn't need it.

1 Like
#4

Not without some extra indirection. But might as well leave that up to the caller -- if you require T: Clone then people can always pass Arc<Whatever> if they don't want multiple copies.

2 Likes
#5

You may be interested in the bimap crate

2 Likes
#6

This also sounds like a problem potentially solved by [internment] (https://crates.io/crates/internment), if you don't mind having an opaque pointer type instead of a u64. Depends on what you're trying to accomplish. Internment works by replacing the u64 with a pointer to T, which further requires a stable heap location for the T.

1 Like
#7

If you don't need to control the actual u64 values, but just have them as cheap keys, then you might be able to work with usize in an IndexSet. You'll get a usize index from insert_full, or later you can look that up with get_index_of(&T). You can retrieve items with get_index(usize)/[usize] or get(&T).

1 Like
#8

I got inspired by this post and here's my take at this problem (playground link),
let me know if you find any bug. Key points:

  • No unsafe code
  • Allocates only a Vec and 2 HashMaps. No Rcs needed
  • Requires nightly because of the currently unstable hash_raw_entry feature
2 Likes
#9

You could use hashbrown directly to get stable raw_entry, or even use RawTable if you allow unsafe. The split storage is pretty close to how IndexMap works, for another reference.

1 Like
#10

RawTable::get, RawTable::insert_entry and RawTable::remove_entry looks exactly like what I needed, and they're also safe! Here's the modified version playground link

2 Likes
#11

Great! It happens that I added those safe methods myself in hashbrown#202, so I'm happy to see them get more use. :slightly_smiling_face:

1 Like