Task: Create lower-level implementation of LinkedDictionary<TKey, TValue>

[NightOwl888]

The LinkedDictionary<TKey, TValue> is a composite type that internally is using a LinkedList<T> and Dictionary<TKey, TValue>. This is a stopgap to get the behavior we need, but we could achieve better performance by using a lower-level hashtable structure to manage the a single collection of items rather than having 2 collections.

The main differences between Dictionary<TKey, TValue> and LinkedDictionary<TKey, TValue> are:

• LinkedDictionary<TKey, TValue> maintains insertion order across edits
• LinkedDictionary<TKey, TValue> allows a null key

Update

.NET 9.0 now includes an OrderedDictionary<TKey, TValue> that should provide the correct functionality. It is MIT licensed, so there is no issue with copying it. We need to evaluate the collection to ensure it behaves correctly. It does not support null keys, which is why we will still need to bring it into our project and modify it. I believe we can simply return 0 for a null hash key and run the same lookup code, but if not check the source code of LinkedHashMap.java in Apache Harmony (which is Apache 2.0 licensed code).

We already have tests in J2N.Tests.xUnit to confirm it behaves as expected, however we should also review the tests Microsoft provides for OrderedDictionary<TKey, TValue> to determine whether there are any gaps that we missed.

[NightOwl888]

The current thinking on this is to name the class OrderedDictionary<TKey, TValue> as it was named in .NET. "Linked" refers to a specific implementation that uses linked lists (fragmented memory), and OrderedDictionary<TKey, TValue> instead uses blocks of adjacent memory elements. There are pros and cons to each approach, and both might be a reasonable replacement for LinkedHashMap<K, V> in different use cases. We could probably port the data structure of LinkedHashMap<K, V> from Apache Harmony later, but I think we should include the OrderedDictionary<TKey, TValue> first since it is optimized for use in .NET.