0

Currently I have a solution where I keep track of objects I am interested in by getting their hashcode via Object.GetHashCode and then storing them in a HashSet<int>.

However, I have also been learning about bitmasks and bitwise operations and I am quite intrigued by them. Here is a great question that I found close to what I am looking to do. However, I cannot seem to make this work efficiently for hash codes.

There is also this question, but it seems to deal with 5-bit numbers, when hash codes are int's (32-bits).

I do get the BitArray solution (from the first referenced question) working, but it is not as fast as my current HashSet approach is. This is due to the sheer number of items in the BitArray that need to be created to account for all known hash codes (int.MaxValue).

Is there some a bitmask/bitwise operation I should consider in making this work with a BitArray? Or have I totally gone off the beaten path here and should simply stick with my HashSet<int> solution?

Community
  • 1
  • 1
Mike-E
  • 2,477
  • 3
  • 22
  • 34
  • fyi dont use gethashcode, collision can happen easily! http://stackoverflow.com/questions/7968753/probability-of-getting-a-duplicate-value-when-calling-gethashcode-on-strings – Fredou Jun 20 '16 at 18:35
  • You should be storing *the objects themselves* in the `HashSet`, not storing their `GetHashCode` values. By only storing the hashes you remove the ability of the `HashSet` to manage collisions. As far as the rest of the question, it's based on the premise that the hash is unique for every object, but that's a false assumption, so you can't do that. Just put the items in a `HashSet`. – Servy Jun 20 '16 at 18:35
  • @Servy that is a good point and you have made me reconsider my design here. I was hoping to store information without having to create a strong-reference in memory to the object and also making it as fast as possible. Sounds like I already found the solution (just making sure I did!). – Mike-E Jun 20 '16 at 18:43
  • @Mike-EEE You could create a weak reference to it, but to not reference it entirely you'd need to have it generate a value that's known to always be unique for that object, and that will never collide. `GetHashCode` doesn't do that; it'd need to provide some other, stronger, form of hashing. – Servy Jun 20 '16 at 18:45
  • @Servy correct. The problem (as I understand it) is that these objects can be structs as well, which don't apply for `WeakReference`, or at least with `WeakReference`. I will put more thought into this. – Mike-E Jun 20 '16 at 18:51
  • Thanky @Fredou and Servy (can't tag, sorry!) for your help! I have figured out a solution and posted it as an answer. Much appreciated. – Mike-E Jun 21 '16 at 10:15

1 Answers1

1

This was indeed an instance of going off the beaten path, paired with a misunderstanding of references/memory management. In my case I was using a Dictionary<TKey, TValue> object to store cached results from method calls on an instance. I couldn't use a ConditionalWeakTable because there are at least three parts to a key:

  1. The instance that contains the method where the results are being cached.
  2. Said method.
  3. Arguments being passed into the method.

If I used a ConditionalWeakTable I would have to create "yet another object" (class) that would require yet another allocation, but worse yet would not be referenced by anything (besides the ConditionalWeakTable) and would get garbage collected on the first pass (this is indeed related to another open -- but now also solved -- question of mine).

After much thought around this, I have realized that the answer does indeed lie in ConditionalWeakTable. Rather than use the 3 items above as a key, the answer is to use a Delegate made up from parts 1 and 2, and then pair a Dictionary to that.

Or to put as a field initialization:

readonly ConditionalWeakTable<Delegate, Dictionary<object[], object>> cache = new ConditionalWeakTable<Delegate, Dictionary<object[], object>>();

(Also of note is the use of a StructuralEqualityComparer with the above dictionary to make this work).

This of course does everything I want. It will keep track of objects until the referenced object which contains the method (and from which the Delegate is comprised) is cleaned from memory. At this point, the cached dictionary will also be released as well, clearing out all of its contents.

Community
  • 1
  • 1
Mike-E
  • 2,477
  • 3
  • 22
  • 34