В самом простом смысле - «ключ» - это просто инструкция для компьютера, как найти требуемое значение в массиве.Таким образом, ключ похож на адрес ячейки значения.И вы не найдете дома в городе без адреса - так что вы, скорее всего, не найдете значения в массиве и без ключа.Большинство языков программирования поддерживают простые массивы, где ключ - это просто целое число - 0,1,2,3, ... Рассмотрим расположение элементов этого массива в памяти:
Element index/key: 0 1 2 3 4
Value: A B C D E
А когда вы запрашиваете компьютер -дай мне элемент array[3]
- он знает, что ему нужно взглянуть на ячейку памяти array_byte_offset_in_ram + size_in_bytes_of(array_element) * 3
Та же самая инструкция, выраженная на человеческом языке, будет "найти, где первый элемент массива хранится в памяти, и прыгнуть с него вперед в памяти в 3 раза".объем памяти, необходимый для хранения 1 элемента массива ".Делая это, алгоритм находит вашу ячейку и выбирает ваше значение D.
Для массивов произвольных ключей, когда ключом может быть любая строка - это другая история.Но идея остается прежней - из ключа компьютера следует вывести, как найти искомый элемент ячейки в памяти.Обычно это делается путем перевода произвольных строковых ключей в целочисленные хеш-значения.Затем сортировка этих хешей и выполнение алгоритма бинарного поиска, чтобы найти целочисленный индекс требуемого хеш-значения.Последний шаг - передать найденный индекс в другой простой массив, где хранятся ваши реальные значения.
Рассмотрим этот массив:
Element key: 'ABC' 'EFG' 'CDE'
Value: a b c
Существует много способов вычисления хэшей, но для простоты считаю глупымхеш-функция
hash(string) = sum(ascii_values_of_chars_in_string)
Итак, у нас есть следующая хеш-таблица:
hash('ABC') = ord('A')+ord('B')+ord('C')
hash('EFG') = ord('E')+ord('F')+ord('G')
hash('CDE') = ord('C')+ord('D')+ord('E')
После сортировки хешей мы генерируем и сохраняем такой хеш-массив:
hash[0] = 198
hash[1] = 204
hash[2] = 210
Теперь мы можем сохранить значения массива в другом простом массиве, где целочисленный индекс должен совпадать с индексом хеш-массива выходных данных сохраненной хеш-функции (ключа) =>
value[0] = 'a'
value[1] = 'c'
value[2] = 'b'
Теперь, когда вы запросите - дайте мнеarray['EFG']
значение - компьютер вычисляет хэш ключа 'EFG', равный 210. Затем, используя двоичный поиск, алгоритм находит значение 210 в хеш-таблице и определяет, что его индекс в хеш-таблице равен 2
.Таким образом, он переходит к таблице значений по индексу 2 с помощью описанной выше техники простых массивов и извлекает полученное значение 'b'
, которое будет вам возвращено.
Это основные принципы ключей массива.Конечно, под капотом есть намного больше вещей - таких как коллизия хешей и т. Д. Но в данный момент вам не нужно больше сложностей, как сейчас.Просто имейте в виду, что на большинстве компьютерных архитектур - на них действуют только простые числа и математика - нет таких причудливых вещей, как «строки» / «объекты» и другой космос: -)