Как работает HashSet?

Вы наверняка использовали эту структуру данных для хранения уникальных данных, но скорее всего вы слышали, что поиск в этой структуре занимает O(1), поэтому вы ее и используете.

Давайте разебермся откуда берется этот загадочный O(1) и каким образом он вообще получается.
Реализаций HashSet может быть много, но смысл остается примерно таким:
У вас есть значение, которое вы хотите положить в коллекцию, допустим оно равно 12. Чтобы получить поиск элемента за O(1), самое простое - это завести массив bool, где индекс будет равен этому числу, а значение true или false. Таким образом мы получаем супер-быстрое добавление элементов и супер-быструю проверку на существование.

Но что если значение будет 1_000_000 или вообще отрицательным? Получается, что использовать массив таким образом мы уже не можем. Для этого давайте вызовем метод GetHashCode(), который нам вернет hash от элемента (т.к. далеко не факт, что мы будет добавлять в коллекцию только числа, там же могут быть и структуры и классы). Таким образом получим некое число в любом случае. Но снова число может быть любым.

Для того, чтобы решить эту задачу, давайте заведем массив "вёдер" или проще говоря "массив списков" (это для простоты понимания). Мы будем хранить элемент в одном из этих ведер (или buckets). Количество ведер изначально зададим, например, 10. Таким образом, чтобы засунуть число 12 в одно из этих бакетов, нам нужно найти остаток от деления 12 % 10 = 2. Вот и наше ведёрко найдено. А дальше мы выполняем операцию buckets[index].Add(value), т.е. добавляем наш элемент в список.
Получается, что добавление элемента будет действительно O(1).

Но что же с поиском элемента?
Нетрудно догадаться, что если мы таким образом добавили элемент в ведро, то и найти его нужно таким же образом. Ищем остаток от деления, находим ведро, а потом ...ой. А потом нам нужно перебрать все элементы в ведре, чтобы найти нужный 🙂 И получается, что никаким O(1) тут и не пахнет. Но мы же знаем, мы же слышали. Мозг скорее всего уловил O(1), но не уловил слова типа "среднее" или "условное", что подразумевает, что в лучшем случае O(1), а в худшем O(n), что понятно, если мы будем добавлять разные истансы одного объекта в HashSet, но при этом метод GetHashCode будет возвращать нам всегда одно и то же число, например.

#datastructures #algorithms

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

В QuadTree каждая нода может иметь до четырех потомков, которые представляют собой разделенную ячейку.

Для добавления объектов в QuadTree необходимо сперва знать, какой ячейке они принадлежат. Каждый объект добавляется в самую мелкую ячейку, которая полностью охватывает его. Если ячейка становится слишком заполненной, то она разбивается на более мелкие. Проще говоря, нужно делать rect.Contains() несколько раз, чтобы понять куда отнести элемент.

Поиск объектов в QuadTree осуществляется путем перебора узлов дерева. Начиная с корня, мы проверяем, находится ли ячейка, в которой мы ищем объект, в пределах текущей ячейки узла. Если да, то мы переходим к следующему уровню дерева и продолжаем поиск в ячейках потомков. Если нет, то мы переходим к следующему соседнему узлу.

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

На практике мы такое используем для поиска целей для атаки.

Существует еще и Octree для 3D, алгоритм работы по сути ничем не отличается.

#datastructures #algorithms