🖥 Для чего существует GetHashCode()

Данный метод позволяет возвратить некоторое числовое значение, соответствующее объекту или, как ещё говорят, его хэш-код. По этому числу можно, например, сравнивать объекты между собой, сортировать их и т.д. Мы можем определять различные алгоритмы генерации хэш-кода или же взять реализацию из базового типа.

Реализованными .NET типами метод используется для ускорения сравнения двух объектов. Если требуется узнать, одинаковы ли какие-то два объекта, то сначала сравниваются их хэш-коды. Если они различаются, то значит и объекты разные. Если же совпадают, то тогда начинается дорогостоящее сравнение через Equals().

➡️ Интересный момент со значимыми типами
У CLR есть две версии реализации метода для значимых типов, и какая версия будет использована — это зависит исключительно от самого типа. Рассмотрим ситуацию с примером ниже.

var k1 = new KeyValuePair<int, int>(10, 29);
var k2 = new KeyValuePair<int, int>(10, 31);
Console.WriteLine("k1 - {0}, k2 - {1}", k1.GetHashCode(), k2.GetHashCode());

var v1 = new KeyValuePair<int, string>(10, "abc");
var v2 = new KeyValuePair<int, string>(10, "def");
Console.WriteLine("v1 - {0}, v2 - {1}", v1.GetHashCode(), v2.GetHashCode());

В первом случае, у структуры нет ссылочных полей и нет свободного расстояния между полями, поскольку поле int занимает 4 байта. Поэтому здесь используется быстрая версия CLR для вычисления хэш-кода. Таким образом, будет выведено на консоль:

k1 - -1813067730, k2 - -1813067732

Во втором же случае, у структуры есть ссылочное поле string, поэтому используется медленная версия. CLR в качестве поля для генерации хэш-кода выбирает поле с типом int, а поле string просто игнорируется, в результате чего на консоль будет выведено следующее:

v1 - 1008467045, v2 - 1008467045

Разработчики CLR рекомендуют всем пользовательским типам данных переопределять метод GetHashCode(). Во-первых, он может работать не очень быстро. Во-вторых, чтобы избежать непонимания того, почему хэш-коды разных объектов равны, как во втором случае примера.

Если не переопределить метод, то можно получить большой удар по производительности при использовании значимого типа в качестве ключа в хеш-таблице.

#Полезно #GetHashCode

🖥 Фильтр Блума

Представим, что мы крупный сайт — какой-нибудь маркетплейс — и нам нужно определять количество уникальных посетителей. Как мы это сделаем? Вполне логичным решением будет сохранение нового IP-адреса из потока сетевого трафика в список, а общее количество элементов такого списка и будет сообщать нам количество уникальных посетителей.

Вопреки такому решению, хранение всех этих данных (IP`шки) для нас может быть лишним. Мы не будем их использовать в дальнейшем, но каждый хранимый объект в памяти будет непременно "раздувать" его общее заполнение. В оптимизации такой задачи нам и поможет фильтр Блума, который мы сегодня рассмотрим на примере поставленной задачи.

➡️ Что это и как он работает
Фильтр Блума проверяет принадлежность конкретного элемента к множеству данных без необходимости его хранения. Он использует массив битов (0 — false, 1 — true), а также несколько хеш-функций. Когда новый объект попадает в базу, его хеш-коды вычисляются, заполняя соответствующие биты массива в значении 1. Например, если хеш-функция возвращает число 50, то 50 бит (он же индекс) массива устанавливается в 1. Так происходит добавление IP-адреса в фильтр.

Если при получении нового IP-адреса все нужные биты уже установлены в значение 1, то это значит, что он уже встречался ранее. Но важно помнить, что фильтр Блума не даёт 100% гарантии, что IP-адрес был уже замечен. Всегда есть небольшой риск ложноположительного результата. Эта вероятность зависит от размера массива битов, количества хеш-функций и количества уникальных IP-адресов.

Фильтр Блума экономит память системы, особенно при работе с большими множествами, ускоряя операции добавления/проверки. Он подходит для задач проверки принадлежности, особенно когда требуется скорость при работе системы в условиях ограниченной памяти. Несмотря на небольшой процент ложноположительных результатов, он широко используется в разных приложениях.

➡️ Снижение вероятности коллизий
Коллизии возникают, когда несколько различных элементов имеют одинаковые хеш-коды, что может привести к ложноположительным результатам при проверке.

Стратегии снижения вероятности коллизий:
⏺Увеличение размера массива битов;
⏺Увеличение количества хеш-функций;
⏺Выбор качественных хеш-функций.

➡️ Простая реализация

public class BloomFilter<T>
{
    public BloomFilter(int capacity, int hashFunctionCount)
    {
        if (capacity < 1) throw new ArgumentOutOfRangeException(nameof(capacity), "Размер должен быть положительным");
        if (hashFunctionCount < 1) throw new ArgumentOutOfRangeException(nameof(hashFunctionCount), "Количество хеш-функций должно быть положительным");

        bitArray = new(capacity);
        hashCount = hashFunctionCount;
    }

    private readonly BitArray bitArray;
    private readonly int hashCount;

    public void Add(T item)
    {
        foreach (int hash in GetHashValues(item))
        {
            bitArray[hash] = true;
        }
    }

    public bool Contains(T item)
    {
        foreach (int hash in GetHashValues(item))
        {
            if (!bitArray[hash]) return false;
        }

        return true;
    }

    public void Clear() => bitArray.SetAll(false);

    private IEnumerable<int> GetHashValues(T item)
    {
        for (int i = 0; i < hashCount; i++)
        {
            int seed = i * 31;
            int hash = (item?.GetHashCode() ?? 0) ^ seed;
            yield return Math.Abs(hash) % bitArray.Length;
        }
    }
}

Проверим:

var filter = new BloomFilter<string>(1000, 5);
var apple = "apple";
var banana = "banana";

filter.Add(apple);
filter.Add(banana);
Check(apple);
Check(banana);
Check("date");
Check("grape");

filter.Clear();
Check(apple);
Check(banana);

void Check(string item) => Console.WriteLine(filter.Contains(item));

Вывод:

True
True
False
False
False
False

Отмечу, что реализация сильно простая. Рекомендую заменять GetHashCode на хеш-функцию MurmurHash2, MD5 или др. Ставьте реакции на пост, если хотите посмотреть на лучшую реализацию — напишу в комментариях.

#Полезно #Хеширование #GetHashCode #Array