LinkedHashMap Implementation?

[damepatr]

Should we implement a class that is similar to java.util.LinkedHashMap<K,V>?

Theoretical Comparison to Hashtable:

Performance Metric	LinkedHashtable	Hashtable
Add, Contains, and Remove Time Complexity	Increases slightly, but still O(1)	O(1)
Iteration and Resize Time Complexity	O(Entries)	O(Buckets+Entries)
Memory Complexity	Increases, but still O(Buckets+Entries)	O(Buckets+Entries)

[svick]

First of all, Hastable is effectively obsolete, so I'm going to assume you're actually talking about Dictionary<K, V> (which has similar time complexity as Hashtable).

Now, I don't quite understand the reasoning behind this suggestion. You're effectively saying that the theoretical time complexity is the same as the existing types and don't provide any other arguments. So why should this type be added?

Especially keep in mind that:

1. Time complexity is useful for estimating performance, but it's the actual performance that matters.
2. Following a linked list tends to be much slower that iterating an array.
3. Iterating a dictionary/map is probably a relatively uncommon operation.
4. Having two types with slightly different performance characteristics is probably not worth it, so the difference would need to be substantial.

[danmoseley]

Agreed with the above, plus if you're interested In such a thing I'd suggest implementing one in your own repo and comparing using benchmark.Net on a range of sizes and loads and operations. Make sure to do a fair comparison including similar argument checks to the existing one. Then you can share hard data.

[damepatr]

First of all, Hastable is effectively obsolete, so I'm going to assume you're actually talking about Dictionary<K, V> (which has similar time complexity as Hashtable).

Yeah, that's correct. I didn't actually take a look at the code for Dictionary<TKey,TValue>, but I'm assuming that it is an implementation of a hash table.

Now, I don't quite understand the reasoning behind this suggestion. You're effectively saying that the theoretical time complexity is the same as the existing types and don't provide any other arguments. So why should this type be added?

When iterating and resizing a hash table, you have to iterate through each bucket in the hash table and check if it contains elements. If there are many empty buckets, performance isn't optimal. Here's a quick example:

var dictionary = new Dictionary<string, string>(1000000); // Assuming larger capacity creates more buckets.
foreach(KeyValuePair<string, string> kvp in dictionary) // Assuming dictionary is iterated even though it contains no elements.
{
    Console.WriteLine("Key = {0}, Value = {1}", kvp.Key, kvp.Value);
}

The performance here wouldn't be optimal because the foreach loop will have to check if many empty buckets contain elements.

[damepatr]

I will remove this comment from my original post:

* O(Entries+Buckets)=O(Entries) since the hash table is resized according to its load factor. However, performance can differ based on the number of buckets, which is why I have included it.

If Dictionary<TKey,TValue> were resized as elements are removed, this would be accurate. However, I'm assuming that Dictionary<TKey,TValue> is only resized as elements are added.

[damepatr]

• Time complexity is useful for estimating performance, but it's the actual performance that matters.
• Following a linked list tends to be much slower that iterating an array.

Yeah, I definitely agree. We'll want to compare performance with Dictionary<TKey,TValue>. The theoretical performance may not be the best in practice.

• Having two types with slightly different performance characteristics is probably not worth it, so the difference would need to be substantial.

Yeah, I agree. I didn't consider that linked list iteration will be slower, so performance may be closer than I was initially thinking. It will require investigation.

[danmoseley]

Another important point (this comes up whenever new collections are proposed) -- most types do not need to be in the core libraries. You can create a nuget package and publish it, or contribute to another package.

There are only a few reasons a type must be in the core libraries., eg,

1. core libraries need to use it themselves. clearly Dictionary is here for this reason.
2. it needs to do special runtime magic so it must be in corelib (or used by corelib, reason 1)
3. it's so fundamental that if it was missing most apps would need to go find it . PriorityQueue got in for this reason, but it was arguable.

there are many reasons to not be there, eg.,

1. core libraries ship only annually
2. they patch shipped releases only selectively
3. there is a lot of process added around API reviews, code reviews etc. only dotnet/runtime committers can commit to it.
4. it adds more cognitive load to users, eg., if you have the using statement, now more types appear. users have to stop and think.
5. IL size
6. codegen size. generic instantiations bloat the size of generated code. So if someone was using Dictionary<K,V> over reference types, code would already be generated by someone else; if they instead used yours, new code would be generated.

[damepatr]

I'm going to close this discussion. As mentioned above, (a) the implementation for this may be best as a separate library and (b) we're not sure if the performance improvements are worth the implementation.

If needed, we can reopen the discussion or create an issue in the future.