Всем привет!

Забыл в субботу отписаться о том, что успел сделать за 7 дней помимо работы.

Исправляюсь)

Изучил следующие структуры данных:

9) ассоциативный массив (словарь) ;
10) множества;
11) фильтр Блюма;

Написал тестов на 480 строк.

Все эти структуры данных в своей реализации используют хэш-функции и хэш-таблицы. Это позволяет получить сложность операций поиска до О(1).

Очень интересной показалась структура "фильтр Блюма".
Фильтр даёт возможность проверки элементов со скоростью O(1). Но фильтр даёт вероятностный ответ. То есть фильтр может вернуть ложноположительный ответ. Это ситуация, когда мы не включали в фильтр строку, но фильтр нам пишет, что данная строка в фильтре есть.

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

Вероятность срабатывания ложноположительного ответа находится в обратной зависимости от количества бит выделяемых под сам фильтр. Чем больше битовый массив, тем меньше вероятность ложноположительного ответа.