Руководство по структуре данных хэш-таблицы

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

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

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

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

Здесь проблема: в правом столбце есть дубликаты. То есть одно и то же название напитка встречается не раз. Другими словами, разные участники пьют один и тот же сладкий напиток или один и тот же алкогольный напиток, в то время как другие участники пьют разные сладкие или алкогольные напитки. Бармен решает решить эту проблему, вставив между двумя столбцами узкую колонку. В этом среднем столбце, начиная сверху, он нумерует строки, начиная с нуля (т. Е. 0, 1, 2, 3, 4 и т. Д.) Вниз, по одному индексу на строку. Тем самым его проблема решена, поскольку имя участника теперь отображается на индекс, а не на название напитка.. Таким образом, поскольку напиток идентифицируется индексом, имя клиента сопоставляется с соответствующим индексом.

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

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

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

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

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

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

Содержание
  1. Значение хеш-функции и хеш-таблицы
  2. Массив
  3. Хеш-функция
  4. Хеш-таблица
  5. Почему именно массив, а не связанный список для хеш-таблицы
  6. Столкновение
  7. Почему возникает коллизия
  8. Основы разрешения коллизий
  9. Separate Chaining
  10. Открытая адресация
  11. Методы разрешения конфликтов для раздельной цепочки и открытой адресации
  12. Методы разрешения отдельных конфликтов цепочки
  13. Разделение цепочек с помощью связанных списков
  14. Отдельная цепочка с ячейками заголовка списка
  15. Разделить цепочку с другими структурами
  16. Методы разрешения открытых конфликтов адресации
  17. Линейное зондирование
  18. Квадратичное зондирование
  19. Двойное хеширование
  20. Идеальная хеш-функция
  21. Хеширование от целых к целочисленным индексам
  22. Функция хеширования деления по модулю
  23. Хеширование ключей переменной длины
  24. Хеширование с преобразованием по основанию
  25. Ключи и значения
  26. Ассоциативный массив
  27. Операции с ассоциативным массивом
  28. insert or add
  29. переназначить
  30. delete or remove
  31. lookup
  32. Заключение

Значение хеш-функции и хеш-таблицы

Массив

Массив — это набор последовательных ячеек памяти. Все локации одинакового размера. Доступ к значению в первом месте осуществляется с помощью индекса 0; доступ к значению во втором месте осуществляется с помощью индекса 1; доступ к третьему значению осуществляется с помощью индекса 2; четвертый с индексом 3; и так далее. Обычно массив не может увеличиваться или уменьшаться. Чтобы изменить размер (длину) массива, необходимо создать новый массив и скопировать соответствующие значения в новый массив. Значения массива всегда имеют один и тот же тип.

Хеш-функция

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

Хеш-таблица

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

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

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

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

Почему именно массив, а не связанный список для хеш-таблицы

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

Столкновение

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

Почему возникает коллизия

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

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

Основы разрешения коллизий

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

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

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

Separate Chaining

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

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

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

Для конфликтующих ключей критерием вставки значения является тот же критерий, который использовался для поиска (и чтения) значения.

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

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

Следующая диаграмма иллюстрирует разрешение конфликта с открытой адресацией:

Хеш-функция берет ключ Питера Джонса, хеширует индекс 152 и сохраняет его номер телефона в соответствующей корзине. Через некоторое время хеш-функция хеширует тот же индекс, 152 из ключа Сьюзан Ли, сталкиваясь с индексом Питера Джонса. Чтобы решить эту проблему, значение Suzan Lee сохраняется в ведре следующего индекса, 153, которое было пустым. Хеш-функция хеширует индекс 153 для ключа Робин Гуда, но этот индекс уже использовался для разрешения конфликта для предыдущего ключа. Таким образом, значение Робин Гуда помещается в следующую пустую корзину, которая соответствует индексу 154.

Методы разрешения конфликтов для раздельной цепочки и открытой адресации

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

Методы разрешения отдельных конфликтов цепочки

Методы для разделения цепочки хешей Теперь кратко поясняются таблицы:

Разделение цепочек с помощью связанных списков

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

Отдельная цепочка с ячейками заголовка списка

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

Разделить цепочку с другими структурами

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

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

Метод разрешения конфликта при открытой адресации называется тестовой последовательностью. Теперь кратко объясняются три хорошо известные последовательности зондов:

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

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

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

Предположим, что конфликт возникает в индексе H. Следующий пустой используется слот (корзина) с индексом H + 1 2 ; если он уже занят, то используется следующий пустой в H + 2 2 , если он уже занят, то следующий пустой в H + 3 2 и так далее. Есть варианты.

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

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

Идеальная хеш-функция

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

В наборе символов ASCII символы верхнего регистра могут быть сопоставлены с соответствующими им нижним регистром. буквы с использованием хеш-функции. Буквы представлены в памяти компьютера в виде чисел. В наборе символов ASCII A — 65, B — 66, C — 67 и т. Д., A — 97, b — 98, c — 99 и т. Д. Чтобы сопоставить A с a, добавьте 32 к 65; чтобы отобразить от B до b, добавьте 32 к 66; чтобы отобразить от C до c, добавьте 32 к 67; и так далее. Здесь заглавные буквы — это клавиши, а строчные — значения. Хеш-таблица для этого может быть массивом, значения которого являются связанными индексами. Помните, что сегменты массива могут быть пустыми. Таким образом, корзины в массиве от 64 до 0 могут быть пустыми. Хеш-функция просто добавляет 32 к верхнему регистру кода, чтобы получить индекс, и, следовательно, к строчной букве. Такая функция представляет собой идеальную хеш-функцию.

Хеширование от целых к целочисленным индексам

Существуют разные методы хеширования целых чисел. Один из них называется методом (функцией) деления по модулю.

Функция хеширования деления по модулю

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

В инструкции

20/6 = 3R2

20 — это дивиденд , 6 — делитель, а остаток 3 — частное. Остаток 2 также называется по модулю. Примечание: возможно иметь модуль 0.

Для этого хеширования размер таблицы обычно равен степени 2, например 64 = 2 6 или 256 = 2 8 и т. Д. Делитель для этой хеш-функции — простое число, близкое к размеру массива. Эта функция делит ключ на делитель и возвращает по модулю. По модулю — это индекс массива корзин. Связанное значение в сегменте — это значение по вашему выбору (значение для ключа).

Хеширование ключей переменной длины

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

Хеширование с преобразованием по основанию

В строке каждый символ в компьютере представляет собой число. В этом методе

хэш-код (индекс) = x 0 a k − 1 + x 1 a k − 2 +… + x k − 2 a 1 + x k − 1 a 0

Где (x0, x1,…, xk − 1) — символы входной строки, а является основанием системы счисления, например 29 (см. Позже). k — количество символов в строке. Это еще не все — см. Ниже.

Ключи и значения

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

Ассоциативный массив

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

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

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

Поскольку ассоциативный массив является структурой данных, он имеет как минимум следующие операции:

Операции с ассоциативным массивом

insert or add

Это вставляет новую пару ключ/значение в коллекцию, сопоставляя ключ с ее значением.

переназначить

Эта операция заменяет значение определенного ключа новым значением.

delete or remove

Это удаляет ключ и его соответствующее значение.

lookup

Эта операция ищет значение определенного ключа и возвращает значение (не удаляя его).

Заключение

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

Оцените статью
nanomode.ru
Добавить комментарий