Does HashSet preserve insertion order *if no items are deleted*

Question

I know there have been several questions regarding HashSet and order preserving and very simple tests show that if adding and removing items the order will not be preserved at all.

But my question is explicitly related to whether insertion order is preserved if no items are ever deleted from the HashSet.

Back in 2009 Jon Skeet (https://stackoverflow.com/a/657289/10894153) said that:

It's possible that if you never remove any items, it will preserve insertion order. I'm not sure, but I wouldn't be entirely surprised.

He reasoned at the time that:

I haven't looked at the internal structures or source code (which I don't have, obviously).

Clearly this has changed and with .NET now being open sourced, I'm wondering if anyone can validate with certainty whether insert order is indeed preserved on a HashSet when no items are deleted.

Prior to asking this question I have performed a couple of quick tests with adding 1000 items to a HashSet and insertion order was preserved, but this is by no means proof that it will always be the case even if no deletions occur.

EDIT

As pointed out by HimBromBeere, official documentation for the HashSet states that order is not preserved and therefore even if current implementations maintain (although it is clear that they do not guarantee it) insertion order this may change in the future.

That being said, I am interested in whether insertion order is maintained when no deletions occur in the current implementation (.NET 4.7.2)

Answer 1

That being said, I am interested in whether insertion order is maintained when no deletions occur in the current implementation.

Yes, it is maintained in 4.7.2. As of 18 Jan 2019.

I suspect part of the issue here is understanding the difference between contract and implementation.

The implementation of HashSet in 4.7.2 will maintain insertion order (if you don't remove items). But you didn't originally ask that. You asked whether:

insertion order is guaranteed

And for that question, the answer is unequivocally No. A method's guarantees are not defined by the implementation, but by the contract. And the contract states:

A set is a collection that contains no duplicate elements, and whose elements are in no particular order.

There is simply no way to read that statement in any other way than that there are no guarantees as to order.

Now - you can choose to ignore the guarantees, and deploy an app relying on the current behaviour. And, as long as Microsoft doesn't release a Windows Update patch that changes the behaviour (or your code runs in a different implementation like Mono etc), you will probably be OK. But probably is not the same as definitely (or guaranteed).