CODEWITHSUNDEEP
c#algorithmdictionary
GoCurry
GoCurry

Reputation: 989

C# set of preknown integers as Dictionary custom key

I want to create a dictionary that is conceptually Dictionary<HashSet<int>, FooBar> where the HashSet<int> in the key has the following restriction:

  1. The members can only be chosen from 0 to N

I think with the restriction, there should be a more performant way to do this than writing a custom IEqualityComparer (as described in this post C# List as Dictionary key). For example, when N<64, each of such hash sets can be mapped to a unique Int64. Say the list contains 1,3,18,29, then (1 << 1) + (1 << 3) + (1 << 18) + (1 << 29)which is 537133066 can represent this combination, so I could implement a Dictionary<Int64, FooBar> to achieve my goal. However apparently this approach doesn't scale beyond 64.

------11/11/2016 Update------

Thanks those who commented below. Now I have better understanding on how hash works, and I think trying to create a collision-free hash for the HashSet<int> as I described with unbounded N is either impossible or too hard and thus not worthwhile.

Also I found a good solution under this question: How do I use HashSet<T> as a dictionary key?. I am not sure about how its performance is, but at least it is very easy to implement.

Upvotes: 0

Views: 97

Answers (1)

Vinay Pandey
Vinay Pandey

Reputation: 8923

Better would be to generate hash of your values in list and use dictionary with int or long as key.

Upvotes: 1

Related Questions