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