Обновлено: 22.11.2024

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

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

В обоих этих примерах студенты и книги были хэшированы в уникальный номер.

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

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

Хеширование выполняется в два этапа:

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

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

хеш = hashfunc(key)
index = hash % array_size

В этом методе хэш не зависит от размера массива, а затем сводится к индексу (числу от 0 до array_size — 1) с помощью оператора по модулю (%).

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

Для создания хорошего механизма хеширования важно иметь хорошую хеш-функцию, отвечающую следующим основным требованиям:

Простота вычислений. Это должно быть легко вычислимо, и оно не должно становиться алгоритмом само по себе.

Равномерное распределение. Оно должно обеспечивать равномерное распределение по хеш-таблице и не должно приводить к кластеризации.

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

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

Нужна хорошая хеш-функция

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

Чтобы вычислить индекс для хранения строк, используйте хеш-функцию, которая указывает следующее:

Индекс для конкретной строки будет равен сумме значений ASCII символов по модулю 599.

Поскольку 599 является простым числом, это уменьшит вероятность индексации разных строк (коллизий). Рекомендуется использовать простые числа в случае модуля. Значения ASCII для a, b, c, d, e и f равны 97, 98, 99, 100, 101 и 102 соответственно. Поскольку все строки содержат одни и те же символы с разными сочетаниями, сумма будет 599.

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

Здесь для доступа к определенной строке потребуется время O(n) (где n – количество строк). Это показывает, что хеш-функция не является хорошей хеш-функцией.

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

String Индекс хэш-функции
abcdef (971 + 982 + 993 + 1004 + 1015 + 102 6)%2069 38
bcdefa (981 + 992 + 1003 + 1014 + 1025 + 976) %2069 23
cdefab (991 + 1002 + 1013 + 1024 + 975 + 986)%2069 14
дефабк (1001 + 1012 + 1023 + 974 + 985 + 996)%2069 11< /p>

Хеш-таблица
Хеш-таблица — это структура данных, используемая для хранения пар ключ/значение. Он использует хеш-функцию для вычисления индекса в массиве, в который элемент будет вставляться или искаться. Используя хорошую хеш-функцию, хеширование может работать хорошо. При разумных предположениях среднее время, необходимое для поиска элемента в хеш-таблице, составляет O(1).

Давайте рассмотрим строку S. Вам необходимо подсчитать частоту встречаемости всех символов в этой строке.

Самый простой способ сделать это — перебрать все возможные символы и подсчитать их частоту один за другим. Временная сложность этого подхода составляет O(26*N), где N – размер строки и 26 возможных символов.

Вывод

Давайте применим к этой задаче хеширование. Возьмите частоту массива размером 26 и хешируйте 26 символов с индексами массива с помощью хеш-функции. Затем выполните итерацию по строке и увеличьте значение частоты в соответствующем индексе для каждого символа. Сложность этого подхода составляет O(N), где N — размер строки.

Вывод

Методы разрешения конфликтов

Отдельное связывание (открытое хеширование)

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

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

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

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

Реализация хэш-таблиц с раздельным связыванием (открытое хеширование)

Хэш-функция вернет целое число от 0 до 19.

Линейное зондирование (открытая адресация или закрытое хеширование)

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

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

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

Линейное зондирование — это фиксированный интервал между последовательными зондированиями (обычно равный 1). Предположим, что хешированный индекс для конкретной записи — это index. Последовательность зондирования для линейного зондирования будет следующей:

index = index % hashTableSize
index = (index + 1) % hashTableSize
index = (index + 2) % hashTableSize
index = (index + 3) % hashTableSize

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

Реализация хеш-таблицы с линейным зондированием

• В наборе данных не более 20 элементов.
• Хэш-функция вернет целое число от 0 до 19.
• Набор данных должен содержать уникальные элементы.

Квадратичный зонд

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

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

index = index % hashTableSize
index = (index + 1 2 ) % hashTableSize
index = (index + 2 2 ) % hashTableSize
index = (index + 3 2 ) % hashTableSize

Реализация хеш-таблицы с квадратичным зондированием

• В наборе данных не более 20 элементов.
• Хэш-функция вернет целое число от 0 до 19.
• Набор данных должен содержать уникальные элементы.

Вставить

Поиск

Двойное хеширование

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

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

index = (index + 1 * indexH) % hashTableSize;
индекс = (индекс + 2 * индексH) % hashTableSize;

Здесь indexH — это хеш-значение, вычисленное другой хеш-функцией.

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

Структура данных хеш-таблицы хранит элементы в парах ключ-значение, где

Хеширование (хэш-функция)

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

Пусть k — ключ, а h(x) — хеш-функция.

Здесь h(k) даст нам новый индекс для хранения элемента, связанного с k .

Представление хеш-таблицы

Чтобы узнать больше, посетите страницу Хэширование.

Конфликт хэшей

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

Мы можем разрешить конфликт хэшей, используя один из следующих методов.

• Разрешение конфликтов с помощью цепочки
• Открытая адресация: линейное/квадратичное зондирование и двойное хэширование

1. Разрешение конфликтов с помощью цепочки

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

Если j является слотом для нескольких элементов, он содержит указатель на начало списка элементов. Если элемент отсутствует, j содержит NIL .

Разрешение конфликтов с помощью цепочки

Псевдокод операций

2. Открытая адресация

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

я. Линейное зондирование

При линейном зондировании конфликт разрешается путем проверки следующего слота.

h(k, i) = (h′(k) + i) по модулю m

Если столкновение происходит в точке h(k, 0), то проверяется h(k, 1). Таким образом, значение i увеличивается линейно.

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

ii. Квадратичное зондирование

Он работает аналогично линейному зондированию, но расстояние между слотами увеличивается (больше одного) с помощью следующего соотношения.

h(k, i) = (h′(k) + c ₁ i + c ₂ i 2 ) mod m

• c ₁ и c ₂ — положительные вспомогательные константы,
• я =

iii. Двойное хеширование

Если после применения хеш-функции h(k) возникает коллизия, то для поиска следующего слота вычисляется другая хэш-функция.

Хорошие хеш-функции

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

Здесь мы рассмотрим различные методы поиска хорошей хэш-функции

1. Метод деления

Если k — ключ, а m — размер хеш-таблицы, хеш-функция h() вычисляется следующим образом:

Например, если размер хеш-таблицы равен 10 и k = 112, то h(k) = 112 mod 10 = 2 . Значение m не должно быть степенью числа 2. Это потому, что степени числа 2 в двоичном формате равны 10, 100, 1000, … . Когда мы найдем k mod m , мы всегда будем получать p-биты младшего порядка.

2. Метод умножения

• kA mod 1 дает дробную часть kA ,
• ⌊ ⌋ дает минимальное значение
• A — любая константа. Значение A лежит между 0 и 1. Но оптимальным выбором будет ≈ (√5-1)/2, предложенный Кнутом.

3. Универсальное хеширование

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

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

Хеш-таблица – это неупорядоченный набор пар "ключ-значение", где каждый ключ уникален.

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

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

Хеширование с цепочкой (упрощенный пример)

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

Операции с хэш-таблицей выполняются в два этапа:

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

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

Начнем с несколько упрощенного примера: структура данных, которая может хранить до 1000 записей со случайными целочисленными ключами.

Для равномерного распределения данных мы используем несколько коротких списков. Все записи с ключами, оканчивающимися на 000, относятся к одному списку, с ключами, оканчивающимися на 001, — к другому и так далее. Всего таких списков 1000. Эту структуру можно представить в виде массива списков:

где LinkedList — связанный список пар "ключ-значение".

• мы извлекаем три последние цифры ключа, hash = key % 1000,
• а затем вставьте ключ и его значение в список, расположенный по адресу table[hash] .

Это операция с постоянным временем.

Поиск осуществляется

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

Средняя временная сложность операций поиска и вставки составляет O(1). Используя тот же метод, удаление также может быть реализовано за постоянное среднее время.

Реалистичный пример хеш-функции

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

Хэш-функция в приведенном выше примере имеет вид hash = key % 1000 . Он принимает ключ (целое положительное число) в качестве входных данных и выдает число в интервале 0..999 .

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

Хорошим примером является реализация хеш-функций для строк в Java. Метод hashCode в классе String вычисляет значение

s[0]·31 n-1 + s[1]·31 n-2 + … + s[n-1]

с использованием целочисленной арифметики, где s[i] — это i:й символ строки, а n — длина строки.

Этот метод можно использовать как хэш-функцию следующим образом:

где размер — это количество точек входа в хэш-таблицу.

Обратите внимание, что эта функция

• зависит от всех символов в строке,
• и что значение меняется, когда мы меняем порядок символов.

Два свойства, которые должны быть у хорошей хеш-функции.

Изменение размера с постоянным амортизированным временем

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

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

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

Подробнее об эффективности этой стратегии см. в разделе Амортизированная временная сложность.

Поделиться этой страницей:

Связанные

Анализ временной сложности оценивает время выполнения алгоритма. Он рассчитывается путем подсчета элементарных операций.

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

3.4 Хэш-таблицы

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

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

Хеш-функции.

• Типичный пример. Предположим, у нас есть приложение, в котором ключами являются номера социального страхования США. Номер социального страхования, такой как 123-45-6789, представляет собой 9-значный номер, разделенный на три поля. Первое поле идентифицирует географическую область, в которой был выдан номер (например, номер, первое поле которого равно 035, относится к Род-Айленду, а номера, первое поле которого равно 214, относится к Мэриленду), а два других поля идентифицируют человека. Существует миллиард различных номеров социального страхования, но предположим, что нашему приложению потребуется обработать всего несколько сотен ключей, чтобы мы могли использовать хеш-таблицу размером M = 1000. Один из возможных подходов к реализации хеш-функции — использовать три цифры с ключа. Использование трех цифр из поля справа, вероятно, будет предпочтительнее, чем использование трех цифр из поля слева (поскольку клиенты могут быть неравномерно распределены по географическим регионам), но лучше использовать все девять цифр для значение int, затем рассмотрим хэш-функции для целых чисел, описанные далее.

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

Предположение J (предположение о равномерном хешировании).

Хеширование с отдельной цепочкой.

Хеш-функция преобразует ключи в индексы массива. Вторым компонентом алгоритма хеширования является разрешение коллизий: стратегия обработки случая, когда два или более ключа должны быть вставлены в один и тот же индекс. Прямой подход к разрешению коллизий состоит в том, чтобы построить для каждого из M индексов массива связанный список пар ключ-значение, чьи ключи хэшируют этот индекс. Основная идея состоит в том, чтобы выбрать M достаточно большим, чтобы списки были достаточно короткими, чтобы обеспечить эффективный поиск с помощью двухэтапного процесса: хеширование для поиска списка, который может содержать ключ, затем последовательный поиск ключа в этом списке.< /p>

Запрограммируйте SectionChainingHashST.java реализует таблицу символов с отдельной цепочкой хеш-таблиц. Он поддерживает массив объектов SequentialSearchST и реализует get() и put(), вычисляя хеш-функцию, чтобы выбрать, какой SequentialSearchST может содержать ключ а затем с помощью get() и put() из SequentialSearchST для завершения любого задания. Программа SectioneChainingLiteHashST.java аналогична, но использует явный вложенный класс Node.

Предложение K. В хеш-таблице с раздельной цепочкой, состоящей из M списков и N ключей, вероятность (согласно предположению J) того, что количество ключей в списке находится в пределах небольшого постоянного коэффициента N/M, чрезвычайно близка к 1. . из N/M очень близко к 1. (Предполагается идеалистическая хэш-функция.)

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

Свойство L. В хеш-таблице с отдельной цепочкой, содержащей M списков и N ключей, количество сравнений (проверок равенства) для поиска и вставки пропорционально N/M.

Хеширование с линейным зондированием.

• ключ, равный ключу поиска: результат поиска
• пустая позиция (нулевой ключ в проиндексированной позиции): промах поиска
• ключ не совпадает с ключом поиска: попробуйте следующую запись

Программа LinearProbingHashST.java представляет собой реализацию АТД таблицы символов, использующую этот метод.

Как и в случае с отдельными цепочками, производительность методов открытой адресации зависит от отношения α = N/M, но мы интерпретируем его по-разному. Для раздельной цепочки α представляет собой среднее количество элементов в списке и обычно больше 1. Для открытой адресации α представляет собой процент занятых позиций в таблице; оно должно быть меньше 1. Мы называем α коэффициентом загрузки хеш-таблицы.

Предложение M. В линейном зондировании есть таблица размера M с N = α M ключей, среднее число зондирований (при допущении J) составляет ~ 1/2 (1 + 1 / (1 - α)) для совпадений при поиске и ~ 1/2 (1 + 1 / (1 – α)^2) для промахов или вставок при поиске.

1. Почему Java использует 31 в hashCode() для String?
2. Это простое число, поэтому, когда пользователь изменяет число на другое, у них нет общих делителей (если только оно не кратно 31). 31 также является простым числом Мерсенна (например, 127 или 8191), которое является простым числом, которое на единицу меньше степени двойки. Это означает, что мод можно выполнить с одним сдвигом и одним вычитанием, если машинная инструкция умножения медленная.< /li>
3. Как извлечь биты из переменной типа double для использования в хешировании?
4. Double.doubleToLongBits(x) возвращает 64-разрядное целое число long, битовое представление которого совпадает с представлением double с плавающей точкой. tt> значение x.
5. Что не так с использованием (s.hashCode() % M) или Math.abs(s.hashCode()) % M для хеширования значения между 0 и М-1?
6. Операция % возвращает неположительное целое число, если его первый аргумент отрицательный, и это приведет к ошибке выхода за границы индекса массива. Удивительно, но функция абсолютного значения может возвращать даже отрицательное целое число. Это происходит, если его аргумент равен Integer.MIN_VALUE, потому что результирующее положительное целое число не может быть представлено с использованием 32-битного целого числа в дополнении до двух. Такую ошибку было бы мучительно трудно отследить, потому что она возникает только один раз на 4 миллиарда! [ Строковый хэш-код «полигенных смазок» равен -2^31. ]

Упражнения

Решение. Да, но это приведет к тому, что все ключи будут хешироваться в одном месте, что приведет к снижению производительности.

Обратите внимание, что версии книжного сайта используют дополнительные 8 байтов на объект SequentialSearch (4 для N и 4 для заполнения).

Творческие упражнения

1. Хеш-атака. Найдите 2^N строк, каждая из которых имеет длину N, которые имеют одинаковое значение hashCode(), предположив, что реализация hashCode() для String ( как указано в стандарте Java) выглядит следующим образом:

Решение. Легко проверить, что хэш "Aa" и "BB" соответствует одному и тому же hashCode()< /tt> значение (2112). Теперь любая строка длины 2N, образованная объединением этих двух строк в любом порядке (например, BBBBBB, AaAaAa, BBAaBB, AaBBBB), будет хешироваться до одного и того же значения. Вот список из 10 000 строк с одинаковым хеш-значением.

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

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

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 Роберт Седжвик и Кевин Уэйн. Все права защищены.

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

  
• Xbox, сколько стоят игры
  
• Как обновить блокнот до последней версии
  
• Zet Gaming Blackout, как включить микрофон
  
• B460 pro4 asrock не запускается
  
• Локальная сеть Ethernet, что это по телевизору