Как проверить, есть ли коллизии в словаре С# с пользовательской хэш-функцией?

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

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

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


person phuclv    schedule 14.07.2020    source источник
comment
Я думаю, что это деталь реализации. Почему вы должны знать это?   -  person Sweeper    schedule 14.07.2020
comment
Вы спрашиваете, как получить хэш-код (GetHashCode())?   -  person mjwills    schedule 14.07.2020
comment
Вам не все равно, встроен ли он в библиотеку? Хэш первой проверки ключа для выполнения поиска за время log2(N). После использования хэша выполняется вторая проверка на наличие повторяющихся хеш-значений путем сравнения ключа словаря с ключом has, чтобы получить уникальное значение ключа.   -  person jdweng    schedule 14.07.2020
comment
@Sweeper просто любопытно, а также полезно быстро проверить некоторые пользовательские функции хеширования.   -  person phuclv    schedule 14.07.2020
comment
@mjwills, конечно, я знаю, как использовать GetHashCode(), потому что я сам реализую его для своего класса. Однако разные хэши не означают, что коллизии не произошло, потому что внутри словаря может использоваться некоторая операция по модулю, которая сопоставляет разные хэши с одним и тем же сегментом.   -  person phuclv    schedule 16.07.2020
comment
Справедливо. Когда люди говорят о коллизиях, они часто говорят о одинаковых хэш-кодах, поэтому просто хотели подтвердить, что вы на самом деле искали.   -  person mjwills    schedule 16.07.2020


Ответы (2)


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

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
person Cihan Yakar    schedule 14.07.2020
comment
dictionary.GetType().GetField("_buckets", BindingFlags.NonPublic | BindingFlags.Instance) возвращает null - person Phate01; 14.07.2020
comment
Я использую .net ядро. Для .NET 4.x вы должны изменить _buckets на ведра. - person Cihan Yakar; 14.07.2020
comment
@CihanYakar, хотя технически это отвечает на вопрос ОП, это не очень хорошая практика. Вы намеренно нарушаете инкапсуляцию. Если по какой-либо причине детали внутренней реализации изменятся, ваша программа перестанет работать. - person just.another.programmer; 14.07.2020
comment
Да! @just.another.programmer; любые изменения могут сделать это. Я с тобой согласен. Но для проверки чего-то, кажется, все в порядке. Но это, конечно, ненадежный код. Внутренняя реализация может измениться в следующей версии. - person Cihan Yakar; 14.07.2020
comment
@CihanYakar, вы сами уже указали на то, что реализация изменилась таким образом, что это сломало бы этот код между .NET 4.x и .NET Core. Есть причина, по которой мы используем модификаторы доступа для принудительной инкапсуляции! Посмотрите мой ответ, чтобы узнать, как решить проблему, не нарушая инкапсуляцию. - person just.another.programmer; 14.07.2020
comment
Да, в самом деле! Я просто хотел показать, как получить доступ к внутренним элементам. - person Cihan Yakar; 14.07.2020

Вероятно, вам лучше создать пользовательскую реализацию Dictionary, которая изменяет методы Add и Remove для проверки конфликтов хэшей на основе компьютера 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();
    }
}
person just.another.programmer    schedule 14.07.2020
comment
Вы также можете написать эту методологию следующим образом: var hasCollision = dictionary.Keys.GroupBy(k => k.GetHashCode()).Any(g => g.Count() > 1); - person Cihan Yakar; 14.07.2020
comment
@CihanYakar да, но это компромисс эффективности. Это требует вычисления хэш-кода всего содержимого словаря каждый раз, когда вы добавляете элемент. Для большого словаря это приведет к снижению производительности. В моей реализации при удалении происходит снижение производительности. Как я уже сказал, в зависимости от ожидаемого использования словаря будет зависеть, как вы кодируете реализацию. - person just.another.programmer; 14.07.2020
comment
Конечно, это зависит от цели. Я спрашиваю только для уточнения и развлечения :). Если он будет проверять только после заполнения словаря, решение LINQ будет лучше (для простоты), но если пользователь хочет получить немедленный ответ, ваше решение хорошо. И оба решения не будут работать с пользовательским компаратором. - person Cihan Yakar; 14.07.2020