Как происходит хеширование в памяти уровни

Хэш — что это и как хэш-функция помогает решать вопросы безопасности

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

Мы будем очень благодарны

если под понравившемся материалом Вы нажмёте одну из кнопок социальных сетей и поделитесь с друзьями.

Хеширование

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

«IT-специалист с нуля» наш лучший курс для старта в IT

Что такое хеш

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

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

Профессия / 8 месяцев
IT-специалист с нуля

Попробуйте 9 профессий за 2 месяца и выберите подходящую вам

Кто работает с хешированием

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

Читайте также Кто такой «белый» хакер: чем занимается и сколько зарабатывает

Для чего нужно хеширование

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

Вот несколько примеров:

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

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

Как работает хеш-функция

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

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

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

Курс для новичков «IT-специалист
с нуля» – разберемся, какая профессия вам подходит, и поможем вам ее освоить

Свойства криптографических хеш-функций

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

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

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

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

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

Профессия / 13 месяцев
«Белый» хакер

Взламывайте ПО безнаказанно и за оплату

Безопасность криптографической хеш-функции

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

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

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

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

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

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

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

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

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

IT-специалист с нуля

Наш лучший курс для старта в IT. За 2 месяца вы пробуете себя в девяти разных профессиях: мобильной и веб-разработке, тестировании, аналитике и даже Data Science — выберите подходящую и сразу освойте ее.

Статьи по теме:

Хеш-функция: что это, для чего нужна и как работает

Мать всех блокчейнов, хранительница паролей и просто интересная технология.

Иллюстрация: Оля Ежак для Skillbox Media

Редакция «Код» Skillbox Media

Онлайн-журнал для тех, кто влюблён в код и информационные технологии. Пишем для айтишников и об айтишниках.

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

Сегодня вы узнаете:

• что такое хеш-функция;
• для чего она нужна;
• где используется;
• как она работает;
• насколько она безопасна.

Что такое хеш-функция

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

Исходным сообщением может быть что угодно: строчка из песни, код программы или, скажем, роман «Ловец снов» Стивена Кинга на китайском языке. Неважно, какой длины будет исходный текст, — на выходе всё равно получится битовый массив одного и того же размера. Например, для функции SHA-1 это 160 бит, или ровно 40 символов.

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

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

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

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

Для чего нужна хеш-функция

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

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

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

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

Чтобы избежать таких атак, каждому паролю при регистрации добавляют соль — то есть случайный набор символов. Когда вы вводите пароль, алгоритм добавляет к нему уникальную соль, потом всё это дело хешируется и получается совершенно новый хеш. Даже если ваш пароль — это банальный qwerty, parol или 12345, жулики об этом не узнают 🙂

Ещё один пример использования хешей — проверка целостности файлов. Например, когда вы запускаете игру из Steam, лаунчер следит, что всё установлено правильно и никакой предприимчивый пользователь не залез в файлы игры и не нашпиговал их под завязку разными модами и читами.

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

Где используется хеш-функция

Вот ещё несколько сфер, где используется хеширование:

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

• Цифровые подписи — чтобы дистанционно подписывать документы без поездок в офисы и встреч с курьерами.
• Хеш-таблицы — это своего рода базы данных, где все данные защищены от перезаписи.
• Антивирусы — хранят вирусы в виде так называемого нечёткого хеша , который позволяет искать новые модификации зловредных программ.
• Системы контроля версий (Git) — для проверки целостности объектов в репозитории: файлов, коммитов, деревьев и так далее.

Теперь подробнее: как работает криптографическая хеш-функция

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

Хешировать будем обычную программистскую «рыбу» — фразу «Hello, world!». Так как компьютер общается только на языке нулей и единиц, первым делом алгоритм переведёт текст в двоичный код:

01001000 01100101 01101100 01101100 01101111 00101100 00100000 01110111 01101111 01110010 01101100 01100100 00100001

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

01001000 01100101 01101100 01101100 01101111 00101100 00100000 01110111 01101111 01110010 01101100 01100100 00100001 10000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 0000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 01011000

После этого алгоритм подготовит основу для будущего хеша. По умолчанию это пять констант по восемь символов — на выходе как раз получится фраза длиной 40 символов и размером 160 бит.

Выглядят константы так:

• h0 = 0×67452301
• h1 = 0xEFCDAB89
• h2 = 0×98BADCFE
• h3 = 0×10325476
• h4 = 0xC3D2E1F0

А дальше начинается магия. Алгоритм дробит исходное сообщение на 80 кусочков и перемешивает с каждой из констант. Каждая итерация цикла обновляет значения h0–h4 до тех пор, пока не закончится исходное сообщение. Постепенно хеш будет выглядеть всё более и более случайным.

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

for i from 0 to 79 if 0 ≤ i ≤ 19 then f = (b and c) or ((not b) and d) k = 0x5A827999 else if 20 ≤ i ≤ 39 then f = b xor c xor d k = 0x6ED9EBA1 else if 40 ≤ i ≤ 59 then f = (b and c) or (b and d) or (c and d) k = 0x8F1BBCDC else if 60 ≤ i ≤ 79 then f = b xor c xor d k = 0xCA62C1D6 temp = (a leftrotate 5) + f + e + k + w[i] e = d d = c c = b leftrotate 30 b = a a = temp

Выполняется функция в несколько раундов: один блок длиной 512 бит — одна итерация. Так как во фразе «Hello, world!» меньше 512 бит, алгоритм обработает её в один заход. Но даже если бы мы подали на вход все четыре тома «Войны и мира», хеширование всё равно заняло бы всего пару секунд.

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

digest = hash = h0 append h1 append h2 append h3 append h4

На выходе получаем готовый хеш:

943a702d06f34599aee1f8da8ef9f7296031d699

Насколько безопасны хеш-функции

В идеале хеш-функция должна обладать следующими свойствами:

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

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

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

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

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

Если, конечно, у вас нет под рукой квантового компьютера (но даже и это, по словам экспертов, не гарантия успешного взлома ��).

Коротко о главном

Подытожим основные тезисы статьи:

• Криптографическая хеш-функция — это алгоритм, который принимает на вход сообщение и превращает его в хеш, то есть битовый массив фиксированного размера. Например, для SHA-1 это 160 бит, а для SHA-256 — 256 бит.
• Для каждого сообщения создаётся свой уникальный хеш. Если поменять во входных данных хотя бы один символ, хеш изменится до неузнаваемости.
• Хеш можно присвоить любому файлу: тексту, песне или компьютерной игре. Ключевой смысл — убедиться, что данные нельзя изменить или подделать.
• Результат работы хеш-функции необратимый — алгоритм нельзя запустить в обратную сторону и получить исходное сообщение. Этим хеширование отличается от шифрования, где, как правило, есть ключ дешифровки.
• Хеширование используется для разных задач: для безопасного хранения паролей на сайте, создания цифровых подписей, защиты игровых данных, подтверждения транзакций в блокчейне и многого другого.

Больше интересного про код — в нашем телеграм-канале. Подписывайтесь!

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

Хеширование в структуре данных: функции, методы [с примерами]

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

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

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

Что такое хеширование в структуре данных?

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

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

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

Хеширование в структуре данных — это двухэтапный процесс.

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

Примеры хеширования в структуре данных

Ниже приведены реальные примеры хеширования в структуре данных :

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

Оформление заказа: сортировка в структуре данных

Хэш-функция

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

hash = hashfunc(ключ)

индекс = хеш% размер_массива

Функция has должна удовлетворять следующим требованиям:

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

Хеш-таблица

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

Как работает хеширование в структуре данных?

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

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

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

Значения: (3,21) (1,72) (40,36) (5,30) (11,44) (15,33) (18,12) (16,80) (38,99)

Хэш-таблица будет выглядеть следующим образом:

Серийный номер	Ключ	Хэш	Индекс массива
1	3	3%30 = 3	3
2	1	1%30 = 1	1
3	40	40%30 = 10	10
4	5	5%30 = 5	5
5	11	11%30 = 11	11
6	15	15%30 = 15	15
7	18	18%30 = 18	18
8	16	16%30 = 16	16
9	38	38%30 = 8	8

Читайте также: Типы структур данных в Python

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

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

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

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

Пример линейного измерения

Представьте, что вас попросили сохранить некоторые элементы в хэш-таблице размером 30. Элементы уже отсортированы в формате пары ключ-значение. Приведены следующие значения: (3,21) (1,72) (63,36) (5,30) (11,44) (15,33) (18,12) (16,80) (46,99) .

Хэш(n) — это индекс, вычисленный с помощью хеш-функции, а T — размер таблицы. Если индекс слота = (hash(n) % T) заполнен, то мы ищем следующий индекс слота, добавляя 1 ((hash(n) + 1) % T). Если (хэш(n) + 1) % T также заполнен, то мы пробуем (хеш(n) + 2) % T. Если (хэш(n) + 2) % T также заполнен, то мы пробуем (хеш( п) + 3) % Т.

Хэш-таблица будет выглядеть следующим образом:

Серийный номер	Ключ	Хэш	Индекс массива	Индекс массива после линейного зондирования
1	3	3%30 = 3	3	3
2	1	1%30 = 1	1	1
3	63	63%30 = 3	3	4
4	5	5%30 = 5	5	5
5	11	11%30 = 11	11	11
6	15	15%30 = 15	15	15
7	18	18%30 = 18	18	18
8	16	16%30 = 16	16	16
9	46	46%30 = 8	16	17

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

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

Формула метода двойного хэширования выглядит следующим образом:

(firstHash(ключ) + i * secondHash(ключ)) % sizeOfTable

Где я — значение смещения. Это значение смещения увеличивается до тех пор, пока не будет найден пустой слот.

Например, у вас есть две хеш-функции: h1 и h2. Чтобы найти свободный слот, необходимо выполнить следующие шаги:

1. Убедитесь, что hash1(key) пуст. Если да, то сохраните значение в этом слоте.
2. Если хэш1(ключ) не пуст, то найти другой слот, используя хеш2(ключ).
3. Убедитесь, что хэш1 (ключ) + хеш2 (ключ) пуст. Если да, то сохраните значение в этом слоте.
4. Продолжайте увеличивать счетчик и повторяйте с hash1(ключ)+2hash2(ключ), hash1(ключ)+3hash2(ключ) и так далее, пока не будет найден пустой слот.

Пример двойного хеширования

Представьте, что вам нужно хранить некоторые элементы в хеш-таблице размером 20. Даны следующие значения: (16, 8, 63, 9, 27, 37, 48, 5, 69, 34, 1).

nh(n, i) = (h1 (n) + ih2(n)) по модулю 20

н	h(n,i) = (h'(n) + i 2 ) %20
16	I = 0, h(n,0) = 16
8	I = 0, h(n,0) = 8
63	I = 0, h(n,0) = 3
9	I = 0, h(n,0) = 9
27	I = 0, h(n,0) = 7
37	I = 0, h(n,0) = 17
48	I = 0, h(n,0) = 8

Изучайте онлайн -курсы по разработке программного обеспечения в лучших университетах мира. Участвуйте в программах Executive PG, Advanced Certificate Programs или Master Programs, чтобы ускорить свою карьеру.

Заключение

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

Вы можете попробовать этот пример, чтобы укрепить свои знания о структуре данных. Если вам интересно узнать больше о структуре данных , ознакомьтесь с программой upGrad Executive PG в курсе Full Stack Development. Этот курс предназначен для работающих профессионалов и предлагает тщательное обучение и трудоустройство в ведущих компаниях.

Что такое хеш-таблица?

Хеш-таблица — это реализация ассоциативного массива, структуры, используемой в компьютерном программировании для реализации абстрактного типа данных (ADT). В абстрактном типе данных программисту не нужно знать о деталях реализации типа данных (например, о том, как данные хранятся в памяти), а только об операциях, которые могут быть выполнены с этим типом данных. Хеш-таблица использует хеш-функцию для вычисления индекса в массиве сегментов или слотов, из которого можно найти желаемое значение. Хеш-таблицы используются для реализации карт, подобных структурам данных. Хеш-таблицы очень часто используются в современных компьютерах для реализации таких вещей, как словари (как в python), ассоциативные массивы (как в php), хэш-таблицы Java и т. д. Хеш-таблицы обычно реализуются в языках как массив значений, отсортированных по их ключам. . Это делает операции поиска и вставки/удаления очень быстрыми, поскольку данные систематически хранятся в памяти.

Каковы приложения хеш-функций?

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

Каковы методы разрешения коллизий при хешировании?

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