Как Set на самом деле работает внутренне при проверке значений? - PullRequest
Новая
       48

Как Set на самом деле работает внутренне при проверке значений?

1 голос
/ 18 апреля 2019

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

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

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

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

1 Ответ

1 голос
/ 19 апреля 2019

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

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

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

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

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

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

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

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

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

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

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

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

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

...