Правильно ли я понимаю Хэшсетс? (Python)

Question

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

Реализация: HashSet список [] или массив, где каждый индекс указывает на головке LinkedList

Таким образом, некоторые хэш (some_item) -> ключ, а затем список [ключ] и затем добавьте в голову LinkedList. Это происходит в O (1) раз

При удалении значения из связанного списка, в python мы заменяем его заполнителем, потому что хэшеты не могут иметь значения Null/None, правильно?

Когда список [] получает за определенный% от нагрузки/полноты, мы скопировать его в другой список

Что касается времени Сложность Путаница: Так один вопрос, почему Средний поиск/доступ O (1), если может быть список из N элементов в связанном списке по данному индексу?

Не будет ли средний случай быть поисковым элементом в середине его проиндексированного списка ссылок, поэтому он должен быть O (n/2) -> O (n)?

Кроме того, при удалении элемента, если мы заменяем его значением-заполнителем, разве это не считается потерей памяти, если местозаполнитель никогда не используется?

И, наконец, в чем разница между этим и HashMap, кроме HashMaps, может иметь нули? И HashMaps являются ключевыми/значениями, в то время как Hashsets - это просто ценность?

Answer 1

Для вашего первого вопроса - почему средняя временная сложность поиска O (1)? - это утверждение в общем случае верно только в том случае, если у вас хорошая хэш-функция. Идеальная хеш-функция - это та, которая вызывает приятное распространение на ее элементах. В частности, хеш-функции обычно выбираются так, что вероятность столкновения любых двух элементов низка. В этом предположении можно формально доказать, что ожидаемое количество проверяемых элементов равно O (1). Если вы ищете в Интернете «универсальное семейство хэш-функций», вы, вероятно, найдете некоторые хорошие доказательства этого результата.

Что касается использования заполнителей - существует несколько способов реализации хеш-таблицы. Подход, который вы используете, называется «закрытая адресация» или «хеширование с цепочкой», и в этом подходе нет оснований для использования заполнителей. Однако существуют и другие стратегии хэширования. Одно общее семейство подходов называется «открытая адресация» (наиболее известным из которых является линейное зондирование хэширования), и в этих настройках элементы-заполнители необходимы, чтобы избежать ложно-негативных поисков. Поиск в Интернете для более подробной информации об этом, скорее всего, даст вам хорошее объяснение причин.

Как это отличается от HashMap, HashMap - это всего лишь одна возможная реализация абстракции карты, поддерживаемой хеш-таблицей. Java HashMap поддерживает ноль, а другие - нет.

Answer 2

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

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

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

Answer 3

Здесь много написано об открытых хэш-таблицах, но некоторые основные моменты пропущены.

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

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

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

Реорганизация, то, O (n). Как можно вставить O (1), когда любой из них может понести эту стоимость? Секрет - это амортизация и сила власти. Когда таблица выращивается, она должна вырасти на фактор больше одного, два наиболее распространены. Если таблица начинается с 1 ведром и удваивает каждый раз, когда коэффициент нагрузки достигает F, то стоимость N реорганизаций является

F + 2F + 4F + 8F ... (2^(N-1))F = (2^N - 1)F 

В этой точке таблица содержит (2^(N-1))F элементов, число в таблице во время последней реорганизации. То есть мы сделали (2^(N-1))F вставки, а общая стоимость реорганизации указана справа. Интересная часть является средней стоимости элемента в таблице (или вставьте, сделайте ваш выбор):

(2^N - 1)F  2^N 
---------- ~= ------- = 2 
(2^(N-1))F 2^(N-1) 

Это где амортизируются O (1) приходит.

Еще один момент заключается в том, что для современных процессоров связанные списки не являются отличной идеей для списков ведра. С 8-байтовыми указателями накладные расходы имеют смысл. Что еще более важно, выделенные кучи узлы в одном списке почти никогда не будут смежными в памяти. Перемещение такого списка приводит к снижению производительности кеша, что может замедлить работу на порядок.

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

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