Indirection hashmap ever useful?

[zeroexcuses]

pub struct Foo {
  data: HashMap<K, V>
}

vs

pub struct Bar<K, V> {
  indirect: HashMap<K, usize>,
  data: Vec<V>
}

Is there ever any advantage to use Bar over Foo? Or is it always just an extra level of indirection ?

[alice]

Well, Bar would let several keys point to the same value without duplicating it.

[zeroexcuses]

That is a good point. Besides that, does Bar have any advantages ?

[cole-miller]

You might be interested in the indexmap crate, which is based on the following closely related data structure:

struct IndexMapCore<K, V> {
    /// indices mapping from the entry hash to its index.
    indices: RawTable<usize>,
    /// entries is a dense vec of entries in their order.
    entries: Vec<Bucket<K, V>>,
}

RawTable is from hashbrown and Bucket<K, V> is basically a key-value pair. One major advantage this offers over HashMap<K, V> is that you can iterate over it as fast as you could a Vec<(K, V)>, and the order of this iteration matches the order in which entries were inserted (at least until you start removing entries, since this is done using Vec::swap_remove to avoid leaving holes in the entries storage). See the README for more details.

[alice]

Well another thing is that iterating over the vector gives you your values in the order you inserted them. (unless you change their order of course)

[geeklint]

Python I believe uses something similar to this construction, although they use the smallest integer key they can for the number of values, which ends up improving the performance of the HashMap considerably for e.g. <256 entries.

There's some more discussion here https://mail.python.org/pipermail/python-dev/2017-December/151263.html

[erelde]

I really liked this talk from Raymond Hettinger, one of the designers of the current python's dictionaries/hashmaps. It takes a bit of a joking, historical, tone.