Ассоциативный хеш массив это
Обновлено: 07.07.2024
Для доступа к элементам индексного массива используются обычные целые числа, называемые индексами. У ассоциативного массива (словаря) эту функцию выполняют ключи. Они, в отличие от индексов, могут быть заданы не только числовым типом данных, но и, например строковым или булевым. Каждому элементу ассоциативного массива соответствует пара «ключ-значение» (key, value), и на нем определены четыре базовые операции:
- INSERT – операция добавления пары в массив;
- REASSIGN – операция изменения существующей пары;
- DELETE – операция удаления пары из массива;
- SEARCH – операция поиска пары в массиве.
В качестве примера объекта, организованного по принципу ассоциативного массива, можно привести тетрадь или базу данных, служащую для записи студентов, выписавших книги в университетской библиотеке, и пока не вернувших их. Ключами здесь будут названия книг, значениями – имена студентов. Так одно значение может соответствовать нескольким ключам (при этом ключи не повторяются), т. е. одну книгу может выписать только один студент, но этот же студент вправе выписать и другие книги.
Исходный код интерфейса ассоциативного массива, на тех языках программирования, в которых имеются встроенные средства (или подключаемые библиотеки) работы с этим типом данных, как правило, получается достаточно компактным и легко читаемым. Так реализация консольного приложения, обслуживающего университетскую библиотеку, на C++ сводится примерно к следующему варианту:
Предполагается, что ассоциативный массив не может хранить две пары с одинаковыми ключами.
В паре значение называется значением, ассоциированным с ключом . Семантика и названия вышеупомянутых операций в разных реализациях ассоциативного массива могут отличаться.
Операция FIND(ключ) возвращает значение, ассоциированное с заданным ключом, или некоторый специальный объект UNDEF, означающий, что значения, ассоциированного с заданным ключом, нет. Две другие операции ничего не возвращают (за исключением, возможно, информации о том, успешно ли была выполнена данная операция).
Поддержка ассоциативных массивов есть во многих интерпретируемых языках программирования высокого уровня, таких, как Perl, PHP, Python, Ruby, Tcl, JavaScript [1] и др. Для языков, которые не имеют встроенных средств работы с ассоциативными массивами, существует множество реализаций в виде библиотек.
Содержание
Примеры
Расширения ассоциативного массива
Указанные три операции часто дополняются другими. Наиболее популярные расширения включают следующие операции:
В последних двух случаях необходимо, чтобы на ключах была определена операция сравнения.
Реализации ассоциативного массива
Существует множество различных реализаций ассоциативного массива.
Самая простая реализация может быть основана на обычном массиве, элементами которого являются пары (ключ, значение). Для ускорения операции поиска можно упорядочить элементы этого массива по ключу и осуществлять нахождение методом бинарного поиска. Но это увеличит время выполнения операции добавления новой пары, так как необходимо будет «раздвигать» элементы массива, чтобы в образовавшуюся пустую ячейку поместить новую запись.
Наиболее популярны реализации, основанные на различных деревьях поиска. Так, например, в стандартной библиотеке STL языка С++ контейнер map реализован на основе красно-чёрного дерева. В языках Ruby, Tcl, Python используется один из вариантов хэш-таблицы. Есть и другие реализации.
В реализациях, основанных на хэш-таблицах, среднее время оценивается как , что лучше, чем в реализациях, основанных на деревьях поиска. Но при этом не гарантируется высокая скорость выполнения отдельной операции: время операции INSERT в худшем случае оценивается как . Операция INSERT выполняется долго, когда коэффициент заполнения становится высоким и необходимо перестроить индекс хэш-таблицы.
Хэш-таблицы плохи также тем, что на их основе нельзя реализовать быстро работающие дополнительные операции MIN, MAX и алгоритм обхода всех хранимых пар в порядке возрастания или убывания ключей.
Поддержка ассоциативных массивов в языках программирования
Библиотека STL языка C++
Здесь приведено простейшее консольное приложение, предоставляющее интерфейс телефонной книжки. Оно реализовано на основе контейнера map.
В языке Java ассоциативный массив именуется картой(map) и имеет соответствующий интерфейс в стандартном Java API: java.util.Map Стандартный Java SDK включает в себя ряд реализаций этого интерфейса: HashMap, LinkedHashMap, ConcurrentHashMap, EnumMap, TreeMap и другие.
Класс Hash из стандартной библиотеки Ruby поддерживает операции [] (find), []= (insert), delete, each, keys, values, а также множество других.
Ниже приведён код с примерами выполнения отдельных операций.
Ниже приведён код с реализацией консольного приложения «телефонная книжка».
Python
Встроенный в Python тип ассоциативного массива называется словарём, элементами которого являются пары ключей и соответствующих им значений.
Расширить свойства встроенного типа словаря (dict) можно путем наследования класса, см. пример.
Delphi
Delphi до 2007 версии не имело прямых средств работы с ассоциативными массивами. Однако, вы можете имитировать ассоциативные массивы, используя различного рода списковые классы для этого: TBucketList, TObjectBucketList, THashedStringList, TStringList (как и все другие потомки TStrings, а также Memo, ListBox и др.). Например:
PL/SQL
СУБД Oracle начиная с версии 9.2.0 позволяет использовать в качестве ключей помимо binary_integer и pls_integer также и строки varchar2 с длиной до 32767:
PureBasic
В PureBasic начиная с версии 4.40 появилась встроенная поддержка ассоциативных массивов. Его называют картой (map). Пример обычного ассоциативного массива.
Пример структурированного (каждым элементом является структура данных) ассоциативного массива.
JavaScript
В JavaScript понятие ассоциативного массива как такового отсутствует. Обычные массивы могут иметь только числовые индексы, потому для эмуляции ассоциативных массивов, ключами которых могут быть в том числе и строковые значения, используются объекты.
Конструкция вида myVar = < key1: value1, key2: value2, … >создает объект myVar с набором полей, каждое из которых имеет свой ключ и значение. В дальнейшем доступ к элементам этого объекта может выполняться как с использованием нотации объектов и полей (myVar.key1), так и в нотации массивов и ключей (myvar['key1']).
См. также
Ссылки
Классы или модули, реализующие ассоциативный массив или его расширение в различных языках программирования:
Примечания
Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена.Вы можете отредактировать эту статью, добавив ссылки на авторитетные источники.
Эта отметка установлена 12 мая 2011.
Ассоциативный массив • Multimap • Множество • Мультимножество • Хеш-таблица
Ассоциативный массив — абстрактный тип данных (АТД), с помощью которого хранятся пары ключ-значение. У него есть и другие названия: "словарь", "мап" (от слова map). В разных языках ему соответствуют разные типы данных. Например, в других языках это:
- Ruby — Hash
- Lua — Table
- Python — Dictionary
- JavaScript — Object
- Elixir/Java — Map
Для чего он нужен? Ассоциативные массивы крайне популярны в прикладном программировании. С их помощью удобно представлять составные данные, содержащие множество различных параметров.
Ассоциативный массив, в отличие от обычного массива (называемого индексированным, так как значения в нем расположены по индексам), нельзя положить в память "как есть". У них нет индексов, которые бы могли определить порядок и простой способ добраться до значений. Для реализации ассоциативных массивов часто используют специальную структуру данных — хеш-таблицу. Она позволяет организовать данные ассоциативного массива удобным для хранения способом. Для этого хеш-таблица использует две вещи: индексированный массив и функцию для хеширования ключей. Обратите внимание, что хеш-таблица это не просто способ размещать данные, она включает в себя логику.
Ниже пойдет речь про то, как ассоциативные массивы бывают устроены внутри, будет много терминов. Эта информация крайне важна для любых разработчиков. Она снимает магичность с происходящего, даёт понимание эффективности, ценой которой приходится платить за удобства.
Хеширование
Любая операция внутри хеш-таблицы начинается с того, что ключ каким-то образом преобразуется в индекс обычного массива. Для получения индекса из ключа нужно выполнить два действия: найти хеш (хешировать ключ) и привести его к индексу (например, через остаток от деления).
Хеширование — операция, которая преобразует любые входные данные в строку (реже число) фиксированной длины. Функция, реализующая алгоритм преобразования, называется "хеш-функцией", а результат называют "хешем" или "хеш-суммой". Наиболее известны CRC32, MD5 и SHA (много разновидностей).
Самый простой способ хешировать данные на PHP — использовать функцию crc32 :
С хешированием мы встречаемся в разработке часто. Например, идентификатор коммита в git 0481e0692e2501192d67d7da506c6e70ba41e913 не что иное, как хеш, полученный в результате хеширования данных коммита.
После того как хеш получен, его можно преобразовать в индекс массива, например, через получение остатка от деления:
Рассмотрим процесс добавления нового значения в ассоциативный массив. Программист пишет:
Такая простая, на первый взгляд, строчка, запускает целый процесс. Ниже его грубое описание, без деталей и с упрощениями:
Почему такая странная структура для хранения? Зачем там нужен ключ? Ответ на этот вопрос будет ниже — там, где мы поговорим про коллизии.
Теперь посмотрим на чтение:
- Интерпретатор хеширует ключ. Результатом хеширования становится число.
- Это число используется как индекс внутреннего массива для поиска значения.
- Если индекс существует, то извлекается значение, которое находилось внутри, и возвращается наружу.
Коллизии
Ключом в ассоциативном массиве может быть абсолютно любая строка (любой длины и содержания). Другими словами, множество всех возможных ключей — бесконечно. В свою очередь, результат любой хешируемой функции — строка фиксированной длины, а значит множество всех выходных значений — конечно.
Из этого факта следует, что не для всех входных данных найдётся уникальный хеш. На каком-то этапе возможно появление дублей (когда для разных значений получается один и тот же хеш). Такую ситуацию принято называть коллизией. Способов разрешения коллизий несколько, и каждому из них соответствует свой тип хеш-таблицы.
Метод цепочек
Суть этого способа заключается в том, что каждая ячейка хеш-таблицы является ссылкой на связный список. Каждый новый элемент добавляется в конец этого списка. Коллизии приводят к тому, что в таблице появляются списки, которые содержат несколько элементов.
Метод открытой адресации
Ещё один способ называется метод открытой адресации. В таблице хранятся непосредственно пары ключ-значение. При возникновении коллизии используется специальный алгоритм вставки элемента. Он проверяет ячейки таблицы в некотором порядке и добавляет новый элемент в первую свободную ячейку. Этот же алгоритм используется для поиска значений.
Открыть доступ
Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно.
В плане эффективности ассоциативные массивы превосходят другие структуры данных: все основные операции в них выполняются за константное время O(1). Например, чтобы добавить новый элемент в середину простого массива, вам придется его переиндексировать (мы говорили об этом в первой части). Сложность этой операции – O(n). В ассоциативном массиве вы просто добавляете новый ключ, с которым связано значение.
Больше полезной информации вы можете получить на наших телеграм-каналах «Библиотека программиста» и «Библиотека фронтендера».Хеш-таблицы
Однако у ассоциативных массивов есть своя слабость – их нельзя положить в память компьютера как есть, в отличие от обычного индексированного массива. Для хранения ассоциативных массивов используется специальная структура – хеш-таблица (hash map).
Грубо говоря, хеш-таблица – это способ превратить ассоциативный массив в индексированный. Она берет каждый ключ ассоциативного массива и по определенному алгоритму превращает его в индекс обычного массива. Такой алгоритм называется хеш-функцией.Ассоциативные массивы – это в некотором смысле синтаксический сахар, более удобная надстройка над хеш-таблицей.
Принципиальная схема работы хеш-таблицы
Хеширование
Чтобы превратить ключ ассоциативного массива в индекс обычного, нужно проделать 2 операции:
- Найти хеш (хешировать ключ);
- Привести найденный хеш к индексу результирующего массива.
То есть конечная задача – преобразовать ключ в числовой индекс, но она обычно выполняется в два этапа.
Вычисление хеша
Хеш-функция получает входные данные и преобразует их в хеш – строку или число фиксированной длины. Вы точно слышали о некоторых алгоритмах хеширования: CRC32 , MD5 и SHA . Ключ при этом может быть представлен любым типом данных, с которым умеет работать хеш-функция.
Пример хеша – идентификатор коммита в git. Когда вы сохраняете изменения, они хешируются и получается что-то вроде 0481e0692e2501192d67d7da506c6e70ba41e913 . Это хеш, вычисленный для ваших изменений.Реализация хеш-функции может быть самой разной. Например, можно использовать самую простую функцию идентичности, которая принимает входной параметр и возвращает его без изменений:
Если в качестве ключей выступают строки, можно вычислять сумму кодов всех символов:
Например, для ключа name хешем будет число 417, а для ключа age – число 301.
Все это не очень хорошие примеры хеш-функций, в реальной жизни они обычно сложнее, но нам важно понять общий принцип. Если вы знаете, с какими данными предстоит работать вашей хеш-таблице, можно подобрать более специфическую хеш-функцию, чем в общем случае.
Важно: для одного и того же входного значения хеш-функция всегда возвращает одинаковый результат.
Приведение к индексу
Обычно размер результирующего массива определяется сразу, следовательно, индекс должен находиться в установленных пределах. Хеш обычно больше индекса, так что его нужно дополнительно преобразовать.
Для вычисления индекса можно использовать остаток от деления хеша на размер массива:
Важно помнить, что чем больше длина массива, тем больше места он занимает в памяти.
Воспользуемся нашей хеш-функцией и преобразуем ассоциативный массив в обычный:
Ключу name соответствует индекс 2, а ключу age – 1.
Мы храним в результирующем массиве не только значения, но и исходные ключи. Зачем это нужно, узнаем очень скоро.
Если теперь мы захотим получить элемент массива с ключом name , то нужно вновь выполнить хеширование этого ключа, чтобы узнать, под каким индексом в массиве располагается связанный с ним элемент.
Коллизии
Вы уже видите слабое место подобных преобразований?
Ключом в ассоциативном массиве может быть абсолютно любая строка любой длины – количество вариантов бесконечно. А количество индексов в массиве ограничено. Другими словами, для всех ключей индексов не хватит, и для некоторых входных данных хеш-функция вернет один и тот же результат. Это называется коллизией.Есть два распространенных варианта решения коллизий.
Открытая адресация
Предположим, что мы передали хеш-функции какой-то ключ ассоциативного массива ( key1 ) и получили от нее 2 – индекс обычного массива, который соответствует этому ключу.
Затем мы передаем ей другой ключ – key2 – и вновь получаем 2 – произошла коллизия. Мы не можем записать новые данные под тем же индексом, поэтому мы просто начинаем искать первое свободное место в массиве. Это называется линейное пробирование. Следующий после 2 индекс – 3 – свободен, записываем новые данные в него:
Для третьего ключа key3 хеш-функция возвращает индекс 3 – но он уже занят ключом key2 , поэтому нам приходится снова искать свободное место.
С записью понятно, но как в такой хеш-таблице найти нужный ключ, например, key3 ? Точно так же, сначала прогоняем его через хеш-функцию и получаем 3. Проверяем элемент массива под этим индексом и видим, что это не тот ключ, который мы ищем. Потому мы и храним исходный ключ в хеш-таблице, чтобы можно было убедиться, что найденный элемент именно тот, который нам нужен. Мы просто начинаем двигаться дальше по массиву, перебирая каждый элемент и сравнивая его с искомым ключом.
Чем плотнее заполнена хеш-таблица, тем больше итераций нужно сделать, чтобы обнаружить ключ, который оказался не на своем месте.
Метод цепочек
В этом подходе значения, соответствующие одному индексу, хранятся в виде связного списка. каждому индексу массива соответствует не один элемент, а целый список элементов, для которых хеш-функция вычислила один индекс. При возникновении коллизии новый элемент просто добавляется в конец списка.
При поиске элемента с конкретным ключом в такой хеш-таблице мы сначала вычисляем его хеш, определяем нужный индекс массива, а затем просматриваем весь список, пока не найдем искомый ключ.
Такая реализация позволяет с легкостью удалять элементы из таблицы, ведь в связном списке операция удаления занимает константное время.
Реализация хеш-таблицы на JavaScript
Хеш-таблица должна реализовывать интерфейс ассоциативного массива, то есть предоставлять три основных метода:
- добавление новой пары ключ-значение;
- поиск значения по ключу;
- удаление пары по ключу.
Чем меньше размер хеш-таблицы (длина массива), тем чаще будут происходить коллизии. Мы возьмем для примера небольшое число – 32. На практике для размера хеш-таблицы часто используются простые числа (которые делятся только на единицу и на себя). Считается, что при этом возникает меньше коллизий.
Для разрешения коллизий будем использовать метод цепочек. Для этого нам потребуется класс связного списка LinkedList , который мы реализовывали во второй статье цикла.
Эффективность основных операций в хеш-таблице
Основные операции в хеш-таблице состоят из двух этапов:
- вычисление хеша для ключа и проверка элемента, соответствующего этому хешу в итоговом массиве.
- перебор других элементов, если нужный не нашелся сразу.
Первый этап всегда занимает константное время, второй – линейное, то есть зависит от количества элементов, которые нужно перебрать.
Эффективность хеш-таблицы зависит от трех основных факторов:
- Хеш-функция, которая вычисляет индексы для ключей. В идеале она должна распределять индексы равномерно по массиву;
- Размер самой таблицы – чем он больше, тем меньше коллизий;
- Метод разрешения коллизий. Например, метод цепочек позволяет свести операцию добавления нового элемента к константному времени.
В конечном итоге, чем меньше коллизий, тем эффективнее работает таблица, так как не требуется перебирать много элементов, если искомый не нашелся сразу по хешу. В целом, эффективность хеш-таблицы выше, чем у других структур данных.
Использование хеш-таблиц
Хеш-таблицы широко используются в программировании, например, для механизмов авторизации, индексации больших объемов информации (баз данных), кеширования или поиска. Еще один распространенный кейс – реализация неупорядоченных множеств, о которых мы поговорим в следующей части цикла.В JavaScript хеш-таблицы в чистом виде используются довольно редко. Обычно всю их работу успешно выполняют обычные объекты (ассоциативные массивы) или более сложные Map. При этом на более низком уровне(интерпретация программы) для представления объектов как раз используются хеш-таблицы.
Объекты и хеш-таблицы часто используются в качестве вспомогательных структур при оптимизации различных действий. Например, для подсчета количества вхождений разных символов в строку.
Хеширование, кодирование и шифрование
Хеширование – это алгоритм, работающий только в одну сторону. Из хеша невозможно получить исходное значение – да и практической необходимости в этом нет, ведь главная задача хеширования – различать входные данные, а не сохранять их. Вы преобразуете исходный текст в какую-то другую последовательность символов с помощью шифра. Такая последовательность либо абсолютно нечитаема (просто набор букв), либо имеет совершенно другой смысл. Если кто-нибудь перехватит это письмо, то просто не поймет, что вы хотели сказать. Ваш друг знает, что послание зашифровано, и знает, как его расшифровать. Таким образом, главная цель шифрования – скрыть информацию от посторонних лиц. Для этого используется секретный ключ или даже два ключа – один для шифрования, второй для расшифровки.Заключение
Разбираясь с хеш-таблицами, мы в очередной раз убедились, что практически все в программировании делается через… массивы. Вот и ассоциативные объекты под капотом тоже их используют, вычисляя индекс для каждого ключа с помощью хеш-функций.
В последней статье цикла мы разберем еще несколько полезных прикладных алгоритмов для веб-разработки.
Читайте также: