Как это работает.
Хэш-таблицы — это эффективные структуры данных, предназначенные для более эффективного поиска реляционных данных. Данные, которые вы, возможно, захотите сохранить в хеш-таблице, похожи на базу данных, которую вы могли бы иметь в Excel.
При создании новой записи в хеш-таблице (в этом примере добавление нового контакта) хэш-таблица будет делать следующее:
— Вы, вероятно, будете использовать имя в качестве ключа для облегчения поиска.
— Хеш-таблица — это объект с массивом хранения внутри него, этот массив имеет ограничение по размеру или длине, ниже — 6.
— При вставке новой записи ключ («Джон») будет преобразован в случайный целое число между нулем и пределом длины-1 с использованием функции хэширования. Это целое число, которое будет служить его индексом в хранилище.
- Затем ключ («Джон») можно использовать для извлечения информации «Джона» путем преобразования ее в индекс и выполнения поиска в массиве хранения.
- Однако две записи могут быть отправлены в один и тот же индекс!
- Вот почему в каждом индексе хранилища есть массив, называемый ведром.
- Новая запись помещается в это ведро.
– Так как же найти нужного человека в ведре, если их несколько? мы перебираем массив корзин в поисках того, у которого есть ключ.
- Каждый массив записей называется кортежем.
Приведенные выше данные будут храниться в хэш-таблице в виде пары значений ключа, называемой кортежем, где ключом является «Джон», а значением является информация Джона, т.е. (массив ниже). Если бы мы хотели получить информацию о Джоне, мы бы передали ключ «Джон», хэш-функция преобразовала бы его в соответствующий индекс массива хранения, а затем мы бы перебрали ведро по этому индексу, чтобы найти кортеж с ключом = ' John' и вернуть соответствующее значение.
var personArray = ['John', ['[email protected]', 0442980098, '10 Howe st']];
По мере увеличения записей длина корзин увеличивается, и наоборот. Оптимальное соотношение длины кортежа и массива хранения составляет от 25% до 75% (причина объяснена ниже), поэтому мы уменьшаем или удваиваем длину хранилища, когда эти границы пересекаются путем удвоения или уменьшения вдвое аргумента «предел».
Зачем это делать.
Хранение информации о каждом человеке в объекте было бы неэффективным из-за нечисловых ключей, например, если вы использовали имя, вам пришлось бы просмотреть все ключи объекта, чтобы найти данного человека. Это подразумевает линейную временную сложность для поиска этого объекта. В хеш-таблицах это решается путем преобразования ключа (имя в данном примере) в числовой индекс для хранения информации в массиве. Это более эффективно, поскольку поиск в массиве имеет постоянную временную сложность O (1).
У нас есть гибкое ограничение на длину массива хранения, чтобы не использовать больше памяти, чем необходимо. Хотя поиск в массиве хранения экономичен по времени, цикл по массиву сегментов для поиска соответствующего ключа не является O (n) (линейным). Это происходит только тогда, когда у нас есть более одного кортежа в ведре. Вот почему мы удваиваем размер массива хранения, когда превышен оптимальный диапазон отношения кортежей к размеру массива хранения.