Объясните, почему, по вашему мнению, дизайнеры выбрали эту реализацию, а затем почему вы считаете, что от нее отказались в пользу той, что использовалась в предыдущем упражнении.

Веб-упражнения

1. Предположим, мы хотим повторно выполнить поиск в связанном списке из элементов длины N, каждый из которых содержит очень длинный строковый ключ. Как мы можем использовать хеш-значение при поиске в списке элемента с заданным ключом? Решение: предварительно вычислить хеш-значение каждой строки в списке. При поиске ключа t сравнивайте его хеш-значение с хеш-значением строки s. Сравнивайте строки s и t только в том случае, если их хэш-значения равны.
2. Реализуйте hashCode() и equals() для следующего типа данных. Будьте осторожны, так как вполне вероятно, что многие точки будут иметь небольшие целые числа для x, y и z.

Он напечатает false, false, false. Дата 21.07.1969 вставляется в хеш-таблицу, но впоследствии изменяется на 12.04.1961, пока значение находится в хеш-таблице. Таким образом, хотя дата 12.04.1961 есть в хеш-таблице, при поиске x или y мы будем искать не в том ведре и не найдем. Мы также не найдем z, так как там дата 21.07.1969 больше не является ключом в хеш-таблице.

Последнее изменение: 26 августа 2016 г.

Авторское право © 2000–2019 Роберт Седжвик и Кевин Уэйн. Все права защищены.

Привет, ребята, вы когда-нибудь задумывались, как словари Python могут быть такими быстрыми и надежными? Ответ заключается в том, что они построены на основе другой технологии: хеш-таблиц.

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

Хеш-функции

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

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

Хэш-функции имеют три основные характеристики:

1. Они быстро вычисляются: вычисление хэша фрагмента данных должно быть быстрой операцией.
2. Они детерминированы: одна и та же строка всегда будет давать один и тот же хэш.
3. Они выдают значения фиксированной длины: неважно, сколько байт вы ввели: один, десять или десять тысяч байт, результирующий хэш всегда будет фиксированной, заданной длины.

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

Некоторые популярные алгоритмы хеширования: MD5, SHA-1, SHA-2, NTLM.

Распространенное использование хэшей

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

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

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

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

Функция hash() Python

В Python есть встроенная функция для генерации хэша объекта — функция hash(). Эта функция принимает объект в качестве входных данных и возвращает хэш в виде целого числа.

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

Теперь попробуйте запустить интерпретатор Python и немного поиграть с функцией hash().Для первого эксперимента попробуйте хэшировать некоторые числовые значения:

Если вам интересно, почему эти хэши имеют разную длину, помните, что функция Python hash() возвращает целые объекты, которые всегда представлены 24 байтами в стандартном 64-битном интерпретаторе Python 3.

Как видите, по умолчанию хеш-значение целочисленного значения является самим значением. Обратите внимание, что это работает независимо от типа хешируемого значения, поэтому целое число 1 и число с плавающей запятой 1.0 имеют один и тот же хэш: 1 .

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

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

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

Хеширование строки мало чем отличается от хеширования числового значения. Запустите интерпретатор Python и попробуйте хешировать строку:

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

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

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

Начиная с Python 3.3, интерпретатор по умолчанию солирует каждую строку и байтовый объект перед его хэшированием, предотвращая возможные DOS-атаки, как продемонстрировали Скотт Кросби и Дэн Уоллах в этой статье 2003 года.

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

Хешируемые типы Python

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

При попытке получить хеш нераспаковываемого типа в Python вы получите ошибку TypeError от интерпретатора, как показано в следующем примере:

Однако каждый пользовательский объект можно хешировать в Python, и по умолчанию его хеш получается из его идентификатора. Это означает, что два разных экземпляра одного и того же класса по умолчанию имеют разные хэши, как показано в следующем примере:

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

Хеш-таблицы

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

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

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

В приведенном ниже примере вы можете найти реализацию базовой хэш-таблицы в Python. Это всего лишь реализация, дающая вам представление о том, как может работать хеш-таблица, потому что, как вы узнаете позже, в Python нет необходимости создавать собственную реализацию хеш-таблиц, поскольку они реализованы в виде словарей. Давайте посмотрим, как работает эта реализация:

Посмотрите на цикл for, начинающийся со строки 9. Для каждого элемента хеш-таблицы этот код вычисляет хэш ключа (строка 10), он вычисляет положение элемента в корзине в зависимости от хеша (строка 11). и добавьте кортеж в ведро (строка 12).

Попробуйте запустить приведенный выше пример, установив для переменной среды PYTHONHASHSEED значение 46, и вы получите следующий вывод, где два сегмента пусты, а два других сегмента содержат по две пары "ключ-значение":

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

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

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

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

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

Запустив этот пример, я получил лучшее распределение входных данных, но столкнулся с коллизией и пятью неиспользованными сегментами:

Как видите, два хэша столкнулись и были вставлены в одно и то же ведро.

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

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

Как видите, перед назначением для всех сегментов установлено значение None по умолчанию, а цикл while продолжает поиск пустого сегмента для хранения данных.

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

Во время поиска в методе get_value() вы используете значение None, чтобы проверить, когда вам нужно прекратить поиск ключа, а затем вы проверяете ключ данных, чтобы убедиться, что вы возвращаете правильное значение.

В приведенном выше примере ключ для Италии столкнулся с ранее вставленным элементом ( Франция ) и по этой причине был перемещен в первую доступную свободную корзину. Однако поиск Италии сработал, как и ожидалось:

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

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

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

Словари: реализация хэш-таблиц Python

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

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

Здесь вы создали словарь с именем chess_players, который содержит пять лучших шахматистов мира и их фактический рейтинг.

Чтобы получить определенное значение, вам просто нужно указать ключ с помощью квадратных скобок:

Если вы попытаетесь получить доступ к несуществующему элементу, интерпретатор Python выдаст исключение Key Error:

Чтобы перебрать весь словарь, вы можете использовать метод .items(), который возвращает итерируемые объекты всех пар ключ-значение в кортежах:

Для перебора ключей или значений словаря Python вы также можете использовать методы .keys() или .values():

Чтобы вставить другой элемент в словарь, вам просто нужно присвоить значение новому ключу:

Чтобы обновить значение существующего ключа, просто присвойте другое значение ранее вставленному ключу.

Обратите внимание: поскольку словари строятся на основе хэш-таблиц, вы можете вставить элемент только в том случае, если его ключ можно хэшировать. Если ключ вашего элемента не хэшируется (например, список), интерпретатор выдает исключение TypeError:

Чтобы удалить элемент, вам нужно использовать оператор del, указав ключ, который вы хотите удалить:

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

Питоническая реализация хеш-таблиц Python

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

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

Попробуйте создать пустой словарь Python и проверьте его размер, и вы обнаружите, что пустой словарь Python занимает 240 байт памяти:

Запустив этот пример, вы увидите, что основной размер словаря Python составляет 240 байт. Но что произойдет, если вы решите добавить значение? Что ж, это может показаться странным, но размер не меняется:

Итак, почему размер словаря не изменился? Потому что, начиная с Python 3.6, значения хранятся в другой структуре данных, а словарь содержит только указатель на то, где хранится фактическое значение. Более того, когда вы создаете пустой словарь, он начинает создавать хеш-таблицу Python с 8 сегментами длиной всего 240 байт, поэтому размер первого элемента в нашем словаре вообще не изменился.

Теперь попробуйте добавить еще несколько элементов и посмотрите, как ведет себя ваш словарь, вы увидите, что словарь растет:

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

Теперь попробуйте удалить все элементы в вашем словаре, по одному, и когда вы закончите, снова проверьте размер, вы обнаружите, что даже если словарь пуст, место не было освобождено:< /p>

Это происходит потому, что, поскольку словари занимают очень мало памяти, а удаление при работе со словарями происходит нечасто, интерпретатор предпочитает тратить немного места впустую, чем динамически изменять размер словаря после каждого удаления. Однако, если вы очистите свой словарь, вызвав метод .clear(), так как это массовое удаление, пространство освобождается и становится минимальным в 72 байта:

Как вы понимаете, первая вставка в этот словарь заставит интерпретатор зарезервировать место для 8 сегментов, возвращаясь к исходной ситуации.

Выводы

В этой статье вы узнали, что такое хеш-таблицы и как они реализованы в Python.

Большая часть этой статьи основана на выступлении Рэймонда Хеттингера на Pycon 2017.

Рэймонд Хеттингер — основной разработчик Python, и его вклад в разработку Python до сих пор был неоценим.

В этой задаче вы создадите словарь, используя хеш-таблицу. Идея хэш-таблицы очень проста и явно хакерская.

Мы собираемся написать хеш-таблицу для хранения строк, но ту же идею можно применить и к любому другому типу данных. Мы пишем функцию (хеш-функцию), которая берет строку и "хэширует" ее, т.е. возвращает целое число (возможно, большое), полученное путем манипулирования байтами входной строки. Для хорошей хеш-функции все байты входной строки должны влиять на вывод, а зависимость вывода от строк должна быть неочевидной. Вот пример хорошей хеш-функции (фактический библиотечный код), в которой используется тот факт, что символ интерпретируется как небольшое целое число: Для строк класса C++ эта же функция будет выглядеть так:

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

1. Примените хеш-функцию к str, возьмите мод на N. Это индекс в хэш-массиве.
2. Проверить каждый элемент связанного списка (сегмента) по этому индексу. Если str еще нет, добавьте его в связанный список.
1. Примените хеш-функцию к str, возьмите мод на N. Это индекс в хэш-массиве.
2. Проверить каждый элемент связанного списка (сегмента) по этому индексу. Если str найдено, вернуть true, иначе вернуть false.

Зачем использовать хэш-таблицы?

Представьте себе словарь, реализованный в виде одного длинного связанного списка (строк). Для поиска в нем слова может потребоваться пройти весь список до конца, проверяя каждый элемент на равенство с искомой строкой. Это очень неэффективно и медленно.

Теперь посмотрите на тот же процесс для хеш-таблицы. Хэширование строки не занимает много времени (см. hash_string), и тогда мы сразу знаем правильный сегмент. Конечно, ведро — это связанный список, и его нужно искать, сравнивая каждый элемент в нем со строкой поиска, но если индекс, полученный путем хеширования, примерно равномерно распределен по массиву ведер, то ведра не должны быть длинными (на среднем, сегмент будет содержать TOTAL_WORDS_STORED / N элементов).

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

Упражнение (задача D)

В системах UNIX существует файл, содержащий все часто используемые слова английского языка, обычно /usr/dict/words. Вот один из них, заархивированный:words.zip. Напишите свою хеш-таблицу для строк и заполните ее, прочитав этот файл. Подойдет что-то вроде этого: В моем файле 45402 слова, поэтому разумный выбор размера хэш-таблицы: 12289, 24593 и 49157. Вы можете заставить свой класс хранить статистику наибольшего и среднего количества коллизий (т.е. ).

Затем, таким же образом, как описано выше, прочитайте текстовый файл и распечатайте все слова, в которых могут быть орфографические ошибки. Напишите функцию-член bool HashTable::Contains(const string & ). Существует программа Unix ispell, которая делает что-то подобное.

Досадные технические проблемы

Обратите внимание, что с точки зрения приведенной выше программы любая последовательность непробельных символов является словом. Пробельные символы (пробел, перевод строки и табуляция) рассматриваются как разделители слов и пропускаются. Таким образом, вам необходимо удалить все знаки препинания (кроме апострофов) из вашего файла, который проверяется на орфографию, прежде чем вы сможете запустить программу для своего текста, так что «конец». , "конец!", "конец?" и "конец" - не разные слова. Это можно сделать с помощью другой небольшой программы или с помощью поиска и замены в любом хорошем текстовом редакторе. Существует также проблема заглавных и строчных букв: «И» и «и» должны быть одним и тем же словом. Эту проблему, к сожалению, нельзя решить ни в одном известном мне текстовом редакторе (кроме Emacs). Я могу предварительно обработать для вас любой текстовый файл следующим образом:

Обе эти подготовительные задачи можно выполнить с помощью двух команд операционной системы UNIX: первая команда изменяет любой символ, который не является буквой в диапазонах AZ или az, или символ новой строки \ н в пробел. Вторая команда изменяет каждую заглавную букву на соответствующую строчную. Для получения дополнительной информации см. man tr в вашей системе UNIX. Ничего подобного в MS Windows или MacOS.

Читайте также:

  
• Объясните, почему с какого-то момента при повторном сжатии файла его размер увеличивается
  
• Как отключить самозащиту в касперском 2021
  
• Файл task5 был сохранен в каком-то каталоге после того, как в этом каталоге был создан подкаталог
  
• Какую роль в моей жизни играет компьютер?
  
• Как включить субтитры в vlc media player