0

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.

Community
  • 1
  • 1
GoCurry
  • 899
  • 11
  • 31
  • 1
    Could you not change that dicitonary key to a String and concat the key members separated by comma? – Gabriel Rainha Nov 10 '16 at 19:37
  • What's the question? – Ivan Stoev Nov 10 '16 at 19:41
  • 1
    Remember that hash codes don't have to be _unique_ - they just need to be the same for two equal objects. _Ideally_ you want as even a distribution as possible, but there's nothing wrong with having hash collisions, since `Equals` is going to get called either way. All that to say that `Dictionary` will limit the number of possible keys while `Dictionary, FooBar>` will not. – D Stanley Nov 10 '16 at 20:00
  • 1
    It can scale a bit, you could make a 128bit key out of two ulongs together in a struct (this may even be worth doing since it's still fairly simple and efficient), but after that it gets annoying very quickly and probably not worth it. So it depends on N. – harold Nov 10 '16 at 21:24

1 Answers1

1

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

Vinay Pandey
  • 8,589
  • 9
  • 36
  • 54