1

As per this solution (https://stackoverflow.com/a/18923091/529618) I am using a ConcurrentDictionary<T,byte> as a workaround for the lack of ConcurrentHashSet<T>. However, I'm struggling to see how I can get the original T Key back out of the dictionary in O(1) time.

var cache = new ConcurrentDictionary<MyEquatableClass, byte>());
//...
if(!cache.TryAdd(classInstance, Byte.MinValue))
    return /* Existing cache entry */;
return classInstance;

Is there any way to get the KeyValuePair<K,V> (or even just the key) for a ConcurrentDictionary<K,V> entry by giving it an equivalent (IEquatable) key, without enumerating through it in O(n) time?

My problem arises because the objects I'm using as Keys are IEquatable<K> to one another, but not ReferenceEqual to one-another. If myDict.ContainsKey(someEquatable), I want to get the original key instance in the dictionary (as well as the value stored with it), and throw away my current (duplicate) instance.

Alain
  • 26,663
  • 20
  • 114
  • 184
  • Have you looked at the [`ConcurrentDictionary.GetOrAdd`](https://learn.microsoft.com/en-us/dotnet/api/system.collections.concurrent.concurrentdictionary-2.getoradd) method? Also is it an option to use a custom [`IEqualityComparer`](https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.iequalitycomparer-1) instead of relying on the equatability of the type? – Theodor Zoulias Apr 07 '20 at 17:14
  • @TheodorZoulias `GetOrAdd` still just returns the existing "value" (a byte in this case) not the key that is currently stored in the Dictionary. I'm not sure how a custom `IEqualityComparer` would help here - unless you're suggesting I 'hijack' the comparison operation to also copy the reference to the key used in the comparison operation, and some how get that back to this method. – Alain Apr 07 '20 at 17:18
  • 1
    Trying to retrieve the actual object you used as a key is kind of a wonky idea. `HashSet` doesn't really let you do that, either. The solution, as you discovered, is to store the key object as the value. If the value is a reference type, then the memory footprint won't be any larger than if you used a `byte`. – Jim Mischel Apr 07 '20 at 17:21
  • 1
    Alain you are right, I have misunderstood your question. Regarding hijacking the `Equals` method of a custom equality comparer, no, I don't think I would suggest that. It sounds too hackish. :-) – Theodor Zoulias Apr 07 '20 at 17:23
  • 1
    @JimMischel isn't the `sizeof(byte)` (1) smaller than the `IntPtr.Size` (4-8)? Also take a look at the [`HashSet.TryGetValue`](https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.hashset-1.trygetvalue) method: *Searches the set for a given value and returns the equal value it finds, if any.* – Theodor Zoulias Apr 07 '20 at 17:44
  • @TheodorZoulias Interesting. I don't recall ever seeing `HashSet.TryGetValue` before. But then, it's been a few years since I worked with C#. As I recall, the minimum allocation for an entry in a Dictionary or HashSet is `IntPtr.Size`. – Jim Mischel Apr 07 '20 at 17:58
  • @JimMischel the internal storage of the `Dictionary` is an array of [`Entry`](https://referencesource.microsoft.com/mscorlib/system/collections/generic/dictionary.cs.html#6d8e35702d74cf71) structs: `private struct Entry {public int hashCode; public int next; public TKey key; public TValue value;}` I guess that the size of this struct depends on the size of the generic `TValue`. – Theodor Zoulias Apr 07 '20 at 18:29
  • @TheodorZoulias Yes, but as I recall the fields are 4- or 8-byte aligned. – Jim Mischel Apr 07 '20 at 21:22
  • 1
    @JimMischel you are right! I just tested it, and a `Dictionary` has the same memory footprint with a `Dictionary` (having the same number of items). – Theodor Zoulias Apr 08 '20 at 00:13

2 Answers2

1

I just realized I could just switch from using a ConcurrentDictionary<TKey, byte> to a ConcurrentDictionary<TKey, TKey>. It may have a bit of a heavier footprint than the byte value (unconfirmed), but if the value and key are the same, I can easily get the key from the value.

To extend this to those finding this question and who are actually using the "value", you can opt to change your dictionary to a ConcurrentDictionary<TKey, Tuple<TKey, TValue>, and get both the original key and the value that way.

var cache = new ConcurrentDictionary<MyEquatableClass, MyEquatableClass>());
//...
if(!cache.TryAdd(classInstance, classInstance))
    return cache[classInstance];
return classInstance;
Alain
  • 26,663
  • 20
  • 114
  • 184
1

Here is an extension method for adding values to a ConcurrentDictionary<T, T> that is used as a ConcurrentHashSet<T> (having the values equal to the keys):

/// <summary>
/// Adds a value to a <see cref="ConcurrentDictionary{T,T}"/>
/// used as a concurrent <see cref="HashSet{T}"/>, if it does not already exist.<br/>
/// Returns the new value, or the existing value if the value exists.
/// </summary>
/// <param name="value">The value to be added, if it does not already exist.</param>
public static T GetOrAdd<T>(this ConcurrentDictionary<T, T> source, T value)
{
    return source.GetOrAdd(value, value);
}

Usage example:

var dict = new ConcurrentDictionary<string, string>(StringComparer.OrdinalIgnoreCase);
Console.WriteLine($"dict.GetOrAdd(\"abc\"): {dict.GetOrAdd("abc")}");
Console.WriteLine($"dict.GetOrAdd(\"ABC\"): {dict.GetOrAdd("ABC")}");
Console.WriteLine($"dict.Count: {dict.Count}");

Output:

dict.GetOrAdd("abc"): abc
dict.GetOrAdd("ABC"): abc
dict.Count: 1
Theodor Zoulias
  • 34,835
  • 7
  • 69
  • 104