search

indexmap-rs / indexmap

A hash table with consistent order and fast iteration; access items by key or sequence index
https://docs.rs/indexmap/
Other
1.72k stars 150 forks source link

Differences from linked-hash-map? #9

Closed dtolnay closed 7 years ago

dtolnay commented 7 years ago

What are the reasons someone would prefer one or the other?

They both provide the same basic guarantees: iteration order matches insertion order and "constant time" for various operations.

From the readme it sounds like OrderMap lookups are faster than LinkedHashMap (OrderMap is faster than HashMap, while LinkedHashMap uses HashMap internally). Also linked-hash-map uses gobs of unsafe code.

Would you recommend OrderMap in all cases over LinkedHashMap or are there some disadvantages?

bluss commented 7 years ago

OrderMap's iteration is probably a mountain faster. About lookups we don't claim to be faster than HashMap in general. It benches a bit faster for smaller cases, but we also know that OrderMap has a greater indirection / cache hit cost to lookups.

Very important to note: OrderMap's guarantee is an order that is consistent, not dependent on key hashes, and depends on the sequence of inserts and removals. It does not keep strict insertion order like linked hashmap. It's also unsuitable to use as an LRU cache, and it can not "pop front" and so on.

I recommend OrderMap when it's a good fit, but it's quite different from the linked hashmap.

dtolnay commented 7 years ago

Thanks for the explanation and for weighing in on our yaml-rust discussion.