Is there a way to keep unique lists in HashSet

Question

UPDATED

HashSet<List<int>> hs = new HashSet<List<int>>();
List<int> list = new List<int>() { 1, 2, 3 };

hs.Add(new List<int>(){1, 2, 3});
hs.Add(list);

If I do hs.Count I get Count as 2.

Is there a way I can stop duplicate lists from being added? Solution needs to have O(1) complexity. Or a similar behavior as HashSet.

you need to provide a comparer that will do your own == for list of int — pm100, Sep 04 '22 at 18:00
_"I do hs.Count I get Count as 2."_ - no, you [don't](https://sharplab.io/#v2:EYLgxg9gTgpgtADwGwBYA0AXEUCuA7NAExAGoAfAAQCYBGAWACgKAGAAgppQG5HeGBIfgAkAhgGcAFgGUYGADwAZAJZj5SvBgB8m1hLGsAvKzwwA7q1GSZ85arnqtmgBQBKHgP621GnQBsVGIbGZqxe9j6ujIIA3jRorFTxAMwAvu6CegB0AIKEhE7+qm5R/Fm5+YUYxR4cAJxOWQDCEPhVXEA==) . But that is because the same list is used. — Guru Stron, Sep 04 '22 at 18:02
`List<>` doesn't override `GetHashCode()` or `Equals()` so the `HashSet<>` doesn't know they're equal. Also, `hs.Count` is `1`, not `2` when your code completes because you add the same list instance twice; adding two `List<>`s with the same values in the same order results in a `Count` of `2`. Speaking of which, does the order of the `List<>` matter for equality? — Lance U. Matthews, Sep 04 '22 at 18:05
You try to add the same list **instance** to the HashSet. By default, list instances are equality-compared by their instance identity (i.e., whether two compared list _instances_ are actually the same list _instance_ or not). At the 2nd add, the HashSet will notice that there it contains aleady a list that is equal to the provided one (because the same list instance is equal to itself). Thus, with the code in your question you will not end up with a _hs.Count_ of 2. (Of course you could have be cheeky and created your onw List type that you are using and telling us about it. ;-) ) — , Sep 04 '22 at 18:05
Assuming you wanted to compare lists by contents and not by reference (as in the latter case this already works, as others have pointed out), doing this in `O(1)` is an impossibility, as lists could be arbitrary long. `O(n)` is a theoretical lower limit, as at the very least all elements of the new list would need to be considered (although you could fold this cost into construction). Depending on what you're doing with the lists and the set alternatives are possible, but that would need more details on your general algorithm rather than this specific implementation. — Jeroen Mostert, Sep 04 '22 at 18:17
@LanceU.Matthews Yes to sum up , I need a way to create a hashcode for `List` that creates the same hashcode for same elements so HashSet behavior is corrected for unique lists, Can this be done? — Shubham Tyagi, Sep 04 '22 at 18:27
@JeroenMostert Is there something I can do at list construction? create a hashCode for that list or something so that HashSet behavior can be corrected? — Shubham Tyagi, Sep 04 '22 at 18:28
You can have a custom `IList` implementation that updates a hash code in its `Add` method to use in the `.Equals()`, but the hash needs to be pretty sophisticated to avoid duplicates as much as possible (so you're looking at something like a cryptographic hash). Being a hash, it could not absolutely guarantee equality, since there is a small chance two lists with identical hash codes could still be different, but a crypto hash would make this chance as small as possible if the lists are of reasonable size and there is no chance of deliberate collisions through malicious input. — Jeroen Mostert, Sep 04 '22 at 18:36
"O(1) complexity" - I suppose you mean the `Add` operation, or? This will not be possible, as you at least have to inspect all the elements of the list to be added. Or will the list sizes be bounded and you only mean O(1) with regards of the number of lists added? — Klaus Gütter, Sep 05 '22 at 04:21

Dmitry Bychenko · Answer 1 · 2022-09-04T19:01:34.273

For keeping "unique" lists you should define what "equal" lists are. The typical way is to define IEqualityComparer<T>, e.g.

public class MyComparer : IEqualityComparer<List<int>> {
  public bool Equals(List<int> A, List<int> B) {
    if (ReferenceEquals(A, B))
      return true;
    if (A is null || B is null)
      return false;

    return A.SequenceEqual(B);
  }

  //TODO: easiest, but not the best hash function
  public int GetHashCode(List<int> list) => list is null
    ? -1
    : list.Count;
}

Then you should mention this comparer when creating HashSet:

var hs = new HashSet<List<int>>(new MyComparer());

List<int> list = new List<int>() { 1, 2, 3 };

hs.Add(new List<int>(){1, 2, 3});
hs.Add(list);

Console.WriteLine(hs.Count);

Output:

Please, fiddle yourself.

Is there a way to keep unique lists in HashSet

1 Answers1