FastDictionary.Add allows adding duplicate keys

[Al-Dyachkov]

Steps to reproduce : 1) Use following comparer to introduce hash collision

struct TestComparer : IEqualityComparer<string>
  {
    public bool Equals(string x, string y)   {  x == y;  }
    public int GetHashCode(string obj)  { obj.Length;   }
  }

2) The test itself is simple

 var  test_dictionary = new FastDictionary<string, int, TestComparer>(default(TestComparer));
   test_dictionary.Add("a",1);
   test_dictionary.Add("b", 1);
   test_dictionary.Remove("a");
   test_dictionary.Add("b",1);

Problem is Add is checking hash for unused and deleted to skip to setting, and deleted check gives false positive if item was removed, but there is valid item in the next bucket.

PS: I've really enjoyed your DotNext lecture.

[redknightlois]

Known issue. In fact, we discontinued the use of this version late in the development process for this very same reason, we only had one place where removes took place. And it was too risky to not being able to solve it completely at that stage --- in case we didn't fix it properly --- so we decided to take the performance hit instead.

I am currently implementing a replacement which is faster because it is also cache-aware; so I would accept a PR for the fix if you are so inclined, but the development effort to create a faster dictionary is put into the new memory layout which current tests show it is even faster.

Probably will talk about it at Saint Petersburg ;)

EDIT: https://github.com/redknightlois/fastdictionary/blob/cache-aware/src/FastDictionary.cs EDIT2: For reference http://issues.hibernatingrhinos.com/issue/RavenDB-8222

[Al-Dyachkov]

We are using collections derived from FastDictionary (with AddOrUpdate extensions etc.) , and just removing these checks worked for us. ( Crude, but overall gains were still worth it )

I can make this fix and PR, but since whole code will be replaced don't really know whether it will be useful to anybody, it's up to you.

Thanks for the information about new version.

[redknightlois]

If you already have the fix, send it over. I will merge it.