хеш-таблица
Хеш-таблица (также называемая хеш-таблицей) — это структура данных, которая напрямую обращается к ячейке памяти в соответствии с ключом. То есть он обращается к записям, вычисляя функцию значения ключа, которая сопоставляет запрашиваемые данные с местоположением в таблице, что ускоряет поиск. Эта функция отображения называется хеш-функцией, а массив записей называется хеш-таблицей.
хэш-функция
Хеш-функция, как следует из названия, является функцией. Если он определен какhash(key), где ключ представляет ключевое значение элемента, тогдаhash(key)Значение представляет собой хеш-значение, вычисленное хеш-функцией.
Он имеет хэш-функцию:
1. Уверенность
Если два хеш-значения не совпадают (согласно одной и той же функции), то исходные входы двух хеш-значений тоже не совпадают.
2. Хэш столкновение (столкновение)
Вход и выход хеш-функции не являются однозначно соответствующими.Если два хеш-значения одинаковы, два входных значения, вероятно, будут одинаковыми, но они также могут быть разными.
3. Необратимость
Хэш-значение соответствует бесконечному количеству открытых текстов, и теоретически вы не знаете, какой именно.
«Капитан, если вы знаете, где что-то есть, это не потеряно».
«Это не считается».
— Хорошо, тогда ты не потерял свой кувшин.
4. Особенности обфускации
Введите некоторые данные для вычисления хеш-значения, а затем частично измените входное значение, хэш-функция с сильными свойствами обфускации даст совершенно другое хэш-значение.
Общие хеш-функции
1. MD5
MD5То есть Message-Digest Algorithm 5 (Алгоритм Message-Digest 5), который используется для обеспечения полной и согласованной передачи информации. Это один из алгоритмов хеширования, широко используемых в компьютерах, а основные языки программирования обычно имеютMD5выполнить.
Преобразование данных (например, китайских иероглифов) в другое значение фиксированной длины является основным принципом алгоритма хеширования.MD5Предшественниками являются MD2, MD3 и MD4.
MD5Это алгоритм, который вводит информацию переменной длины и выводит 128-битную информацию фиксированной длины. После выполнения программы генерируются четыре 32-битных данных, которые, наконец, объединяются в 128-битный хэш.
Основной метод состоит в том, чтобы вычислить остаток, взять остаток, отрегулировать длину и выполнить операцию цикла с переменной ссылки для получения результата.
MD5Вычисления широко используются для проверки ошибок. В некоторых загрузках BitTorrent программное обеспечение проверяет целостность загруженных фрагментов, вычисляя MD5.
2. SHA-1
SHA-1 (англ. Secure Hash Algorithm 1, китайское название: Secure Hash Algorithm 1) — это криптографическая хэш-функция, SHA-1 может генерировать 160-битное (20-байтовое) хеш-значение, называемое дайджестом сообщения, хеш-значение обычно представляется как 40 шестнадцатеричных цифр.
Когда-то SHA-1 широко использовался во многих протоколах безопасности, включая TLS и SSL, PGP, SSH, S/MIME и IPsec, и считался преемником MD5.
хэш-коллизия
В идеале хэш-функция, надеющаяся достичь
Если ключ1 ≠ ключ2, то хеш(ключ1) ≠ хэш(ключ2)
Этот эффект, однако, в реальной ситуации найти хэш-функцию с разными значениями хэша, соответствующими разным ключам, практически невозможно.MD5или разработан АНБSHA-1Алгоритмы тоже невозможны.
На самом деле никакая хорошая хэш-функция не может избежать коллизий хэшей.
Зачем?
Это связано с хорошо известным математическим принципом: принципом ящика.
Принцип ящика: На столе десять яблок. Положите эти десять яблок в девять ящиков. Как бы вы их ни положили, мы обнаружим, что по крайней мере в одном ящике будет как минимум два яблока. Это явление мы называем «принципом ящика».
Для хеш-таблицы, независимо от того, насколько велика заданная область хранения (n), когда данные, которые нужно сохранить, больше, чем n, должна быть ситуация, когда значение хеш-функции одинаково. Это называетсяхэш-коллизия.
Как мы должны решить проблему коллизии хэшей?
Существует два широко используемых метода разрешения конфликтов хэшей: открытая адресация и цепочка.
открытая адресация
Определение: Расширение хеш-функции определяется как тестовая последовательность, то есть каждое ключевое слово имеет тестовую последовательность h(k,0), h(k,1), ..., h(k,m-1), это probe Последовательность должна быть компоновкой 0....m-1 (должна содержать все индексы хеш-таблицы, иначе может случиться, что хотя хэш-таблица не заполнена, элементы не могут быть вставлены), если ключевое слово задано k, сначала проверьте, пусто ли h(k, 0), если оно пусто, вставьте его, если оно не пусто, проверьте, пусто ли h(k, 1), и так далее.
Метод открытой адресации — это метод разрешения коллизий.Для методов разрешения конфликтов открытой адресации существуют более классические методы, такие как линейное зондирование, квадратичное зондирование и двойное хэширование.
Линейный метод обнаружения
Когда мы вставляем данные в хэш-таблицу, если определенные данные хешируются хеш-функцией, а место хранения уже занято, мы начинаем с текущего местоположения и поиск в обратном направлении, чтобы увидеть, есть ли свободное место, пока мы не найдем это.,
В качестве примера вышеизложенного, размер хеш-таблица составляет 8, желтая площадь представляет собой опору ожидания, а оранжевая область указывает, что данные хранятся. 4 элемента хранятся в текущем хэш-таблице. В это время элемент 7777777 хешируется в положение 7 в положении 7 после хеша алгоритма, но это место было данных, поэтому есть конфликт.
Так что ищите один за другим, чтобы увидеть, есть ли свободная позиция.В это время, к счастью, есть свободная позиция в следующей позиции, вставьте ее и завершите хранение данных.
Большим недостатком линейного метода детектирования является то, что когда в хэш-таблицу вставляется все больше и больше данных, вероятность хеш-коллизий будет возрастать, количество свободных позиций будет становиться все меньше, а время линейного детектирования будет короче. , дольше и дольше. В крайнем случае необходимо проверить всю хеш-таблицу от начала до конца, поэтому временная сложность в наихудшем случае составляет O(n).
Вторичный метод обнаружения
Квадратичное обнаружение является сокращением от квадратичного обнаружения. Как следует из названия, размер шага использования квадратичного обнаружения становится исходным «квадратичным», то есть обнаруживаемая им последовательность индексов равнаhash(key)+0,hash(key)+1^2или[hash(key)-1^2],hash(key)+2^2или[hash(key)-2^2].
Возьмите приведенный выше рисунок в качестве примера, размер хеш-таблицы равен 8, желтая область указывает на свободное место, а оранжевая область указывает на то, что данные были сохранены. В настоящее время в хеш-таблице хранится 7 элементов. В это время после алгоритма Hash элемент 7777777 хэшируется в позицию с индексом 7, но в этой позиции уже есть данные, поэтому возникает конфликт.
в соответствии сВторичный метод обнаруженияоперация, если есть конфликт, сначала + 1^2, 8 эта позиция имеет значение, конфликт; становится - 1^2, 6 эта позиция имеет значение или есть конфликт; поэтому - 2^2, 3 эта позиция свободна , вставить.
метод двойного хеширования
Так называемое двойное хэш, означающее, что не только хочет использовать хеш-функцию, но использование набора хэш-функцийhash1(key),hash2(key),hash3(key). . . . . . Сначала используем первую хеш-функцию, если рассчитанное место хранения уже занято, то используем вторую хеш-функцию и так далее, пока не будет найдено свободное место хранения.
Возьмите приведенный выше рисунок в качестве примера, размер хеш-таблицы равен 8, желтая область указывает на свободное место, а оранжевая область указывает на то, что данные были сохранены. В настоящее время в хеш-таблице хранится 7 элементов. В это время после алгоритма Hash элемент 7777777 хэшируется в позицию с индексом 7, но в этой позиции уже есть данные, поэтому возникает конфликт.
В это время данные снова обрабатываются хэш-алгоритмом, и после другого хеш-алгоритма они хешируются до позиции с индексом 3 для завершения операции.
На самом деле, независимо от того, какой метод обнаружения используется, пока в хеш-таблице не так много свободных позиций, вероятность хеш-коллизии будет сильно увеличена. Для того, чтобы максимально обеспечить эффективность работы хеш-таблицы, в общем случае необходимо обеспечить, чтобы в хеш-таблице была как можно больше определенной доли свободных слотов.
Общее использованиекоэффициент загрузки(коэффициент загрузки) для указания количества вакансий.
коэффициент загрузки- степень заполнения элементов в таблице Hsah. Чем больше коэффициент загрузки, тем больше элементов заполняется. Преимущество этого в том, что коэффициент использования пространства высок, но вероятность конфликта увеличивается. И наоборот, чем меньше коэффициент загрузки, тем меньше элементов заполняется, преимущество в том, что снижается вероятность конфликта, но больше теряется пространство.
метод связанного списка
Метод связанного списка является более распространенным решением для хэш-коллизий и намного проще, чем метод открытой адресации. Как показано на следующей анимации, в хеш-таблице каждая позиция соответствует связанному списку, и все элементы с одинаковым значением хеш-функции помещаются в связанный список, соответствующий той же позиции.
вопрос дня
В чем заключается преобразование метода цепной таблицы для получения более эффективного списка органов?
Добро пожаловать, чтобы обратить внимание на этого программиста, который умеет делать анимацию 👆