Alternative To Ordered HashMap

1

Hi all,

I'm trying to build an OrderedHashMap. OrderedHashMap is really just a hash map that can be iterated in the same order of the insertion. In programming language with garbage collection, it's quite easy to implement, we just need a hash map and a linked list. Everytime we insert an entry, we put it into a hash map and append the linked list. Iterating through all the entries is easy as well, we just need to iterate the linked list.

In rust it's quite challenging. Currently, I can make it work by using Rc or Arc to store the key. So, I have something like this:

struct OrderedHashMap<K,V> {
   keys: Vec<Rc<K>>,
   map: HashMap<Rc<K>, V>,
}

Note: here I'm using Vec because in my case there is no update or remove. We can only insert values. And inserting an existiing key is noop.

My questions are:

  1. Is there a better way to do this? Using Rc<K> in the HashMap prevents me to call self.map.get(k) where k is a borrowed version of K. So If I have OrderedHashMap<String,i32>, I can't call get with &str.
  2. Is there existing rust library that can do this?
2

indexmap is it.

3 Likes
3

Nice, thank you. This is what I'm looking for.

4

Also linked_hash_map.

The roll-your-own implementation isn't particularly hard in Rust, either. The particular issue you encountered can be solved by wrapping the internal HashMap in a newtype and requiring the same Borrow<K> bound as it would, except that K is not Rc<RealKeyType>. This works because Rc<T> can be converted to &T which is trivially Borrow<T>.

Moreover, storing keys behind Rc means that they can be unsized. Thus, you don't need to make an OrderedMap<String, V>, you can make an OrderedMap<str, V> and index it directly with &str.
Minimal demonstration.

2 Likes
5

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.