Блог

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

Я использовал их много раз, и рекомендуется использовать их для хранения уникальных значений и быстрого доступа к ним. Предположительно, в нотации Big-O его время и сложность равны O (1) при каждом обращении к Set . Как это возможно, если набор может содержать тысячи элементов? Даже если элементы уникальны.

Чтобы найти элемент в наборе, ему все равно нужно сканировать каждый уникальный элемент, который в Big-O равен O (n) по времени и сложности. Есть ли что-нибудь, чего мне здесь не хватает?

Заранее спасибо за вашу помощь! Самый подробный ответ получает право голоса!

A Set является примером более общего вида объектов, которые в совокупности называются HashedCollections . Они используют какой-то тип HashTable для фактического хранения и извлечения своих элементов.

Учитывая any element , эти таблицы вычисляют для него целочисленное значение с именем its hash . Существует несколько хорошо известных методов определения сопоставления между элементами и их hash значениями. Некоторые из них являются внутренними в том смысле, что hash не зависят от атрибутов element , которые могут измениться, и, следовательно hash , остаются неизменными на протяжении всего срока службы element . Другие являются внешними в том смысле, что они могут зависеть от атрибутов. Однако в последнем случае предполагается, что конкретные элементы не будут изменены, пока на них ссылаются из a HashedCollection (в противном HashedCollection случае они должны быть rehashed ).

Процедура сохранения element работает следующим образом:

1. Вычисляется hash для element .
2. Значение index для таблицы вычисляется как остаток от hash модуля length таблицы.
3. Если слот в index вычисленном so уже занят, применяется некоторая политика для разрешения коллизии.

Шаг 1 должен быть очень быстрым (например, hash у него нет cryptographic силы).

Шаг 2 предполагает (в большинстве случаев), что длина таблицы является простым числом ( 2 также используются степени)

Шаг 3 может быть решен в основном двумя различными способами:

• Таблица последовательно сканируется j до тех пор, пока слот at index j не освободится, или
• Элемент добавляется в коллекцию элементов, сталкивающихся в заданном index (сегменте)

Кроме того, если пустых слотов недостаточно (что увеличивает вероятность столкновения), таблица увеличивается и rehashed (из-за modulo изменения).

При достаточном количестве свободных слотов и довольно случайном распределении механизма индексации вероятность нахождения нужного слота в O(1) очень высока. Конечно, если слишком много элементов сталкиваются, средняя сложность больше не O(1) увеличивается, но это предположительно смягчается растущей политикой ( rehash ).

Извлечение аналогично. Чтобы проверить element , принадлежит ли an в коллекции, вычисляются его hash и modulo и element сравниваются с содержимым целевого слота. Если сравнение завершается неудачей, поиск продолжается линейно в корзине.

Удаление элементов несколько сложнее, когда их нет bucket , и вместо indexes этого они увеличиваются, но вы поняли идею.

Если вы действительно хотите увидеть все это в действии, продолжайте и отлаживайте основные операции HashedCollections на любом диалекте Smalltalk. Много веселья гарантировано.