Open NightOwl888 opened 4 years ago
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.
The
LinkedDictionary<TKey, TValue>
is a composite type that internally is using aLinkedList<T>
andDictionary<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>
andLinkedDictionary<TKey, TValue>
are:LinkedDictionary<TKey, TValue>
maintains insertion order across editsLinkedDictionary<TKey, TValue>
allows anull
keyUpdate
.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 supportnull
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 anull
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 forOrderedDictionary<TKey, TValue>
to determine whether there are any gaps that we missed.