Как проверить, есть ли коллизии в C# Словаре?

Question

Можно получить размер ведра в C ++ , чтобы проверить статус столкновения, но я не смог найти способ сделать это в C#. Как я могу узнать, произошло ли столкновение со словарем?

Я хочу протестировать свою пользовательскую функцию хеширования, потому что, хотя функция возвращает разные значения для моих тестовых значений, некоторые из них могут отображаться в одном и том же сегменте из-за операция по модулю. Это не go в производство, поэтому не беспокойтесь об изменениях во внутренней реализации в других версиях

Answer 1

Вы можете получить внутренние корзины следующим образом:

var dictionary = new Dictionary<string, int>();
dictionary.Add("a", 8);
dictionary.Add("b", 1);
var buckets = dictionary.GetType().GetField("_buckets", BindingFlags.NonPublic | BindingFlags.Instance)
              .GetValue(dictionary); // use "buckets" for 4.x

Answer 2

Вероятно, вам лучше создать собственную реализацию Dictionary, которая изменяет методы Add и Remove для проверки на sh коллизий на основе компьютера GetHashCode элементов. Вы можете составить "настоящий" Dictionary внутри, чтобы сделать реальную работу по хранению элементов.

Вот пример версии. Вы можете оптимизировать методы Add и Remove в зависимости от типа ожидаемых хэшей.

public class CollisionDetectingDictionary<TKey, TValue> : IDictionary<TKey, TValue>
{
    private readonly Dictionary<TKey, TValue> InternalDictionary = new Dictionary<TKey, TValue>();
    private readonly List<int> HashCodesInDictionary = new List<int>();

    public event Action<int, TKey, IEnumerable<TKey>> HashCollision; 

    public TValue this[TKey key] { get => InternalDictionary[key]; set => InternalDictionary[key] = value; }
    public ICollection<TKey> Keys => InternalDictionary.Keys;
    public ICollection<TValue> Values => InternalDictionary.Values;
    public int Count => InternalDictionary.Count;
    public bool IsReadOnly => false;

    public void Add(TKey key, TValue value)
    {
        Add(new KeyValuePair<TKey, TValue>(key, value));
    }

    public void Add(KeyValuePair<TKey, TValue> item)
    {
        var hashCode = item.Key.GetHashCode();
        if (HashCodesInDictionary.Contains(hashCode))
        {
            var collisions = GetKeysByHashCode(hashCode);
            HashCollision?.Invoke(hashCode, item.Key, collisions);
        }

        Add(item);
    }

    private IEnumerable<TKey> GetKeysByHashCode(int hashCode)
    {
        foreach (var key in Keys)
        {
            if(key.GetHashCode() == hashCode)
            {
                yield return key;
            }
        }
    }

    public void Clear()
    {
        InternalDictionary.Clear();
    }

    public bool Contains(KeyValuePair<TKey, TValue> item)
    {
        return InternalDictionary.Contains(item);
    }

    public bool ContainsKey(TKey key)
    {
        return InternalDictionary.ContainsKey(key);
    }

    public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
    {
        ((IDictionary<TKey,TValue>)InternalDictionary).CopyTo(array, arrayIndex);
    }

    public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
    {
        return InternalDictionary.GetEnumerator();
    }

    public bool Remove(TKey key)
    {
        var hashCode = key.GetHashCode();
        if(GetKeysByHashCode(hashCode).Count() == 1)
        {
            HashCodesInDictionary.Remove(hashCode);
        }

        return InternalDictionary.Remove(key);
    }

    public bool Remove(KeyValuePair<TKey, TValue> item)
    {
        return Remove(item.Key);
    }

    public bool TryGetValue(TKey key, out TValue value)
    {
        return InternalDictionary.TryGetValue(key, out value);
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return InternalDictionary.GetEnumerator();
    }
}