[API Proposal]: New method HashSet<T>.AddOrUpdate that replaces an existing element if found

[theodorzoulias]

Background and motivation

When adding an existing key to a Dictionary<TKey,TValue> collection, there is an option to either preserve or replace the existing value.

dictionary.TryAdd(key, value); // Preserve
dictionary[key] = value; // Replace

There is no such option for the HashSet<T> collection. There is only an Add method with preserving behavior.
So this proposal is to introduce a new AddOrUpdate method with replacing behavior:

API Proposal

namespace System.Collections.Generic;

public class HashSet<T>
{
    /// <summary>Adds the specified element to a set, replacing an existing equal element if found.</summary>
    /// <param name="item">The element to add to the set.</param>
    public void AddOrUpdate(T item);
}

API Usage

Recently I wrote a custom ICollection<T> collection intended for JSON serialization, that has the functionality of the KeyedCollection<TKey,TItem>, but instead of a List+Dictionary combo is backed by a HashSet<T>. Practically it is a dictionary that is serialized in JSON as a list. I wanted to replicate the existing deserialization behavior of the Dictionary<TKey,TValue> collection regarding duplicate keys, which is to preserve the last key found in the JSON document and silently discard the earlier duplicates. So I implemented the ICollection<TItem>.Add method like this:

abstract class JsonKeyedCollectionBase<TKey, TItem> : ICollection<TItem>
{
    private readonly HashSet<TItem> _set;

    /* ... */

    void ICollection<TItem>.Add(TItem item)
    {
        if (_set.Add(item)) return;
        bool removed = _set.Remove(item);
        bool added = _set.Add(item);
        Debug.Assert(removed);
        Debug.Assert(added);
    }
}

The whole implementation can be found here. If the proposed API was available, I could make the above implementation simpler and (presumably) more efficient like this:

    void ICollection<TItem>.Add(TItem item) => _set.AddOrUpdate(item);

Alternative Designs

No response

Risks

No response

[dotnet-policy-service]

Tagging subscribers to this area: @dotnet/area-system-collections
See info in area-owners.md if you want to be subscribed.

[hez2010]

Maybe a new method called AddOrUpdate is better?

[theodorzoulias]

@hez2010 do you mean the same method signature with a different name, or a different signature? In the second case, could you share the signature of the AddOrUpdate method?

[hez2010]

Yeah I mean the same method signature with a different name.
We already have ConcurrentDictionary.AddOrUpdate so this can be consistent with how we name things in BCL.

But I think the signature can also be changed to:

// returns a boolean indicating whether the value is replaced
bool AddOrUpdate(T value, out T? oldValue);

[theodorzoulias]

@hez2010 using this AddOrUpdate in my specific scenario, I would have to do:

void ICollection<TItem>.Add(TItem item) => _set.AddOrUpdate(item, _ => item);

...which would capture the item argument, resulting in an allocation of a closure object. I would prefer to avoid that.

Also could you share a scenario where invoking the updateValueFactory and returning a value different than the item, would make sense? The HashSet<T> is not typically used as a dictionary, and my specific scenario already deviates from the typical usage of this collection.

Regarding the other AddOrUpdate which returns a bool, it is essentially the same with my Add proposal, changing only how the replaced information is returned. I don't have a strong opinion about this. Both a return value and an out parameter are fine with me.

I wouldn't even mind if this information was omitted. In my specific scenario I don't care if there was already an equal item in the collection, neither I care what was this item.

[hez2010]

Sorry for the misleading. I found the updateValueFactory is problematic here so I deleted the comment just after I posted it.

[theodorzoulias]

@hez2010 no problem. I edited my previous comment accordingly.

[DaZombieKiller]

If we had CollectionsMarshal APIs for HashSet<T> like we do for Dictionary<TKey, TValue> it would be possible to implement this manually without multiple lookups:

public static partial class CollectionsMarshal
{
    public static ref T GetValueRefOrAdd<T>(HashSet<T> set, T value, out bool exists);
}

// ...

public static void AddOrReplace<T>(this HashSet<T> set, T value)
{
    CollectionsMarshal.GetValueRefOrAdd(set, value, out _) = value;
}

[stephentoub]

If we had CollectionsMarshal APIs for HashSet like we do for Dictionary<TKey, TValue>

There's a reason, though, that those APIs for dictionary don't give you a ref to the TKey: it'd be incredibly easy to accidentally change the key to one that hashes differently, at which point the dictionary would be corrupted. For a HashSet, the value is the key, so providing a ref to it incurs the same problems. It's why we haven't exposed such an API when it's been discussed before.

[eiriktsarpalis]

Seems like a potential duplicate of #21603? Sentiment at the time was it isn't common enough to create sets where reference equality of elements is significant -- wouldn't storing as a value in a dictionary be preferable in that case?

[theodorzoulias]

@eiriktsarpalis I chose the HashSet<T> over a Dictionary<K,V> because I want to avoid wasting memory by storing the key in two places (the same that @magol wanted here). My collections are stored in memory from the moment my program begins until it terminates, and the program already uses quite a lot of memory, so I want to minimize any wasteful usage of it.

The issue #21603 is about a HashSet<T>.GetOrAdd method, that either adds a value or returns the existing equal value. That functionality is distinct from what is asked here, which is a method that always adds a value, regardless of whether an equal value already exists.

I can see that this proposal could be rejected for the same reason that the other was rejected, because each new API in commonly used collections increases the static size of applications. My two cents are: AFAIK the HashSet<T> is not a commonly used collection, and it cannot be amended with a CollectionsMarshal API that would allow the developers to implement efficiently any additional APIs they need in a case-by-case basis (as Stephen Toub explained in a previous comment).

Personally I think that both the GetOrAdd and the replacing Add are fundamental operations, and in an ideal world they would be part of the public API of the HashSet<T> collection.

[theodorzoulias]

@eiriktsarpalis btw would you consider reopening the issue #21603? Developers can't comment or provide any feedback on closed issues, and the existence of a closed issue discourages developers from opening a new issue with the same proposal. The issue #21603 was closed partially on the anticipation of a future CollectionsMarshal API that would enable efficient GetOrAdd implementations, and we now know that such an API is not viable for the HashSet<T> collection.