Что такое ассоциативный массив?

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

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

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

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

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

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