Task: Create lower-level implementation of LinkedHashSet<T> #95
Labels
design
is:enhancement
New feature or request
pri:normal
up for grabs
This issue is open to be worked on by anyone
Milestone
Our current
LinkedHashSet<T>
implementation uses a quirk of theHashSet<T>
design to produce the correct ordering, but it involves expensive allocations when an item is removed followed by an add or insert. While this is somewhat unlikely in production, these allocations can add up and result in additional undesired GC overhead..NET 9.0 now includes an
OrderedDictionary<TKey, TValue>
that should provide the correct ordering functionality. It is MIT licensed, so there is no issue with copying it.I believe we can just bring over the implementation of the hash code calculation and change the
entries
array from aKeyValuePair<TKey, TValue>
to typeT
. But we need to make sure that anull
value forT
is supported.We should keep the same API members (in the same order in the source code) that we have currently, but replace the implementation to use the new arrays instead of cascading the call to
HashSet<T>
. See the J2N and Microsoft implementations ofHashSet<T>
to get an idea of how each member can be implemented. We should be keeping all of the same optimizations that Microsoft has for these methods (looking at the latest .NET 8.0 implementation).We already have tests in
J2N.Tests.xUnit
to confirm it behaves as expected, we just need to create an implementation that passes the tests.The text was updated successfully, but these errors were encountered: