LinkedHashMap in .NET

Question

I wonder if there is a counterpart to java.util.LinkedHashMap in .NET? (ie. the elements are (re)ordered automatically if I access an element. (boolean accessOrder) ).

• Cerebrus: I would like to understand the logic whereby merely accessing an element in the collection is regarded as a modification, thereby causing re-ordering.
• Adam Ralph: I'm not familiar with the class in question, but perhaps to allow faster access to most accessed elements?
• Peter Štibraný: You can see details about LinkedHashMap at java.sun.com/javase/6/docs/api/java/util/LinkedHashMap.html It explains usage, and when it is useful (LRU caches).
• nawfal: See generic-key-value-pair-collection-in-that-preserves-insertion-order
• N0thing: I answered this in stackoverflow.com/a/36961779/158179, I put a minimal, no dependencies LinkedHashMap implemented in C#. Hope it helps! (Also: could we link the two questions? They seem to ask more or less the same thing).

Answer 1

Just to clarify a bit for readers: LinkedHashMap only behaves that way when built with one particular constructor overload. Normally the elements are maintained in insert order. (This feels a little odd to me, but never mind.)

I don't believe there's any such class in .NET. It wouldn't be too hard to build one, using a linked list of elements and a dictionary from key to linked list node. Access would then consist of fetching the linked list node, moving it to the head, and returning the value.

I'd be happy to implement it tonight or tomorrow if you want - although probably not with full unit tests etc. (Fully testing a collection is a time-consuming business!)

• configurator: What is such an odd class (that behaves differently depending on ctor) useful for?
• Vojislav Stojkovic: @configurator: A typical optimization for hash tables: move the recently accessed element to the head of its chain; the more frequently accessed an element, the faster it's found. As for behaving differently depending on ctor, think of it as passing a different IComparer to a SortedList.
• Peter Štibraný: @Vojislav: This is not "typical optimization". LinkedHashMap doesn't move entries towards beginning in buckets, it just remembers when was each entry used, and moves entry to beginning of 'recently used entries' list. This affects only iteration order, not lookup speed of next searches.
• WolfmanDragon: Here is the beauty of LinkedHashMap. It makes a HashMap that is backed by a linked list. If you pass in presorted information, say from a resultSet, then it keeps the information sorted. It can be iterated over in order of insertion and is fast. If I could only ever use one collection, this is it.
• Paul Draper: @configurator, There are very many times that you need both fast lookup and iteration in the original order of insertion.

Answer 2

A bit of Googling seems to show that there is no built in C# equivalent for LinkedHashMap, but there are some third party options available.

Answer 3

Here's a C# implementation I found on a forum:

It's undocumented, but does have some tests. It is not generic, however. At least it's something I guess.

@Jon: I'd appreciate it too if you could do a quick implementation. I imagined that a Dictionary on top of a LinkedList would be best, but I hear there are garbage collection issues with LinkedList that slows things down.

• George Polevoy: Garbage collection issue can be solved with node pool. You would need custom doubly-linked list implementation though.

Answer 4

I used System.Collections.Specialized.OrderedDictionary as a replacement for LinkedHashMap. It worked for me. Is there anything I'm missing about OrderedDictionary (yes, it's not generic, but it is available with .Net 2 or newer)?

• Stan Bashtavenko: It seems to me that OrderedDictionary is different from LinkedHashMap in two important ways. 1) LInkedHashMap entry moves up to front after it was read. That is the order is determined by both insertion and selection (access). 2) LinkedHashMap has overloading method removeEldestEntry. Both of these features are valuable if you want to build a cache.

Answer 5

I know this is an old topic, but there is an awesome open source project to implement LinkedHashMap in .NET C5

Here is LinkedHashMap source code.

• Martin Kersten: That is a mighty big class. 3k+ lines and 117 kb source code. I would never use that in an actual project. Granted there are many different sub-classes in that big one but do I really think they have that many tests that everything is well covered... So I guess I will mix my own implementation by simply combining a linked list with a dictionary. After all what is needed for my case is to establish a order for the keys of the dictionary and that is about it.

Answer 6

Nhibernate has a NHibernate.Util.LinkedHashMap implementation.

If you already have it on your code, as I had, it can be handy

Answer 7

As there is still no LinkedHashMap in C#, and I needed this functionality, I've implemented one on the latest net core (3.1). https://github.com/idlerboris/LinkedHashMap/blob/master/CustomCollections/CustomCollections/LinkedHashMap.cs. It's covered with basic tests and seems to be good, but feel free to contribute/report issues.

Answer 8

pretty late to the game, but I implemented the LinkedHashMap (Java) equivalent in C# as LinkedDictionary as follows:

 public class LinkedDictionary<K, V> : IDictionary<K, V>, ICollection<KeyValuePair<K, V>>, IEnumerable<KeyValuePair<K, V>>
 {
 private List<K> list = new List<K>();
 private Dictionary<K, V> dictionary = new Dictionary<K, V>();
 public LinkedDictionary()
 {
 }
 public V this[K key] {
 get {
 return this.dictionary[key];
 }
 set {
 this.dictionary[key] = value;
 if (!this.list.Contains(key))
 {
 this.list.Add(key);
 }
 }
 }
 
 public int Count => this.dictionary.Count;
 public bool IsReadOnly => false;
 ICollection<K> IDictionary<K, V>.Keys => this.list;
 ICollection<V> IDictionary<K, V>.Values
 {
 get
 {
 List<V> values = new List<V>(this.dictionary.Count);
 foreach(K key in this.list)
 {
 V value = default(V);
 this.dictionary.TryGetValue(key, out value);
 values.Add(value);
 }
 return values;
 }
 }
 public void Add(KeyValuePair<K, V> item)
 {
 this.dictionary.Add(item.Key, item.Value);
 if (!this.list.Contains(item.Key))
 {
 this.list.Add(item.Key);
 }
 }
 public void Add(K key, V value)
 {
 this.dictionary.Add(key, value);
 if (!this.list.Contains(key))
 {
 this.list.Add(key);
 }
 }
 public void Clear()
 {
 this.dictionary.Clear();
 this.list.Clear();
 }
 public bool Contains(KeyValuePair<K, V> item)
 {
 return this.dictionary.Contains(item);
 }
 public bool ContainsKey(K key)
 {
 return this.dictionary.ContainsKey(key);
 }
 public void CopyTo(KeyValuePair<K, V>[] array, int arrayIndex)
 {
 throw new NotImplementedException();
 }
 public bool Remove(KeyValuePair<K, V> item)
 {
 if (this.Contains(item)){
 this.list.Remove(item.Key);
 return this.dictionary.Remove(item.Key);
 } else
 {
 return false;
 }
 }
 public bool Remove(K key)
 {
 if (this.dictionary.ContainsKey(key))
 {
 this.list.Remove(key);
 return this.dictionary.Remove(key);
 }
 else
 {
 return false;
 }
 }
 public bool TryGetValue(K key, [MaybeNullWhen(false)] out V value)
 {
 return this.dictionary.TryGetValue(key, out value);
 }
 public V Get(K key)
 {
 V value = default(V);
 this.dictionary.TryGetValue(key, out value);
 return value;
 }
 public IEnumerator<KeyValuePair<K, V>> GetEnumerator()
 {
 foreach (K key in this.list){
 V value = default(V);
 this.dictionary.TryGetValue(key, out value);
 yield return new KeyValuePair<K, V>(key, value);
 }
 }
 IEnumerator IEnumerable.GetEnumerator()
 {
 return this.GetEnumerator();
 }
 private class LinkedDictionaryIterator<K, V> : IEnumerator<V>
 {
 private int i;
 private readonly Dictionary<K, V> dictionary;
 private readonly List<K> list;
 
 public LinkedDictionaryIterator(Dictionary<K, V> dictionary, List<K> list)
 {
 this.dictionary = dictionary;
 this.list = list;
 this.i = 0;
 }
 public void Dispose()
 {
 
 }
 public bool MoveNext()
 {
 return this.i < this.dictionary.Count;
 }
 public void Reset()
 {
 this.i = 0;
 }
 public KeyValuePair<K, V> Current
 {
 get
 {
 int ii = this.i;
 ++this.i;
 V value = default(V);
 K key = this.list[ii];
 this.dictionary.TryGetValue(key, out value);
 return new KeyValuePair<K, V>(key, value);
 }
 }
 V IEnumerator<V>.Current
 {
 get
 {
 int ii = this.i;
 ++this.i;
 V value = default(V);
 K key = this.list[ii];
 this.dictionary.TryGetValue(key, out value);
 return value;
 }
 }
 object IEnumerator.Current
 {
 get
 {
 return Current;
 }
 }
 }

And a simple UnitTest where I compare it to Dictionary

 class UnitTest_LinkedDictionary
 {
 [Test]
 public void Test00()
 {
 LinkedDictionary<string, int> d = new LinkedDictionary<string, int>();
 d.Add("1", 1);
 d.Add("2", 2);
 d.Add("3", 3);
 d.Remove("2");
 d.Add("4", 4);
 d.Select(i => $"{i.Key}: {i.Value}").ToList().ForEach(Console.WriteLine);
 }
 [Test]
 public void Test01()
 {
 Dictionary<string, int> d = new Dictionary<string, int>();
 d.Add("1", 1);
 d.Add("2", 2);
 d.Add("3", 3);
 d.Remove("2");
 d.Add("4", 4);
 d.Select(i => $"{i.Key} :{i.Value}").ToList().ForEach(Console.WriteLine);
 }
 }

As it is based on a Dictionary and a List it at least adds the time complexity of List accesses and Dictionary accesses.