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

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

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

Хеш-таблица

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

Двигаясь вперед, мы рассмотрим базовую анатомию хеш-таблицы, ее эффективность и способы ее реализации в JavaScript.

Хеш-функции

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

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

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

Разрешение столкновений

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

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

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

Динамическое изменение размера

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

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

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

Эффективность

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

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

В хорошо размеренной хэш-таблице средняя временная сложность каждого поиска, вставки и удаления не зависит от количества элементов, хранящихся в таблице. В терминах Big O это будет считаться O(1) или постоянной временной сложностью. Это то, что делает хеш-таблицы такими мощными, но ключевым здесь является термин «правильное измерение». Это означает, что хеш-таблица имеет адекватный размер, поэтому изменение размера происходит редко. Когда изменение размера действительно происходит, оно может занять драгоценное время выполнения. Однако можно считать, что эти дополнительные затраты амортизируются для всех вставок и удалений, и поэтому ими можно пренебречь.

Реализация в JavaScript

Хеш-функция

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

Не критично понимать, как работают операторы «сдвиг влево» или «побитовое и» и почему они здесь используются, но полезно знать, что происходит на высоком уровне.

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

Общая структура

Мы могли бы использовать здесь тип class, но от этого мало что выиграешь. Вместо этого мы будем использовать функцию и добавим три свойства к ее привязке this. Взглянем:

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

Если вам интересно, мы не можем просто использовать свойство length в массиве _storage для измерения количества свойств, потому что мы будем вставлять элементы в индексы, сгенерированные функцией хеширования. Эти индексы вряд ли будут последовательными, поэтому в массиве будут пробелы, которые не будут отражены в свойстве length. Попробуйте это в консоли вашего браузера. Назначьте пустой массив переменной, вставьте значение в индекс 5 или любой другой ненулевой индекс, а затем прочитайте свойство length в массиве. Вы увидите, что свойство длины равно 6, хотя мы вставили только один элемент.

Вставить метод

Далее мы определим метод вставки и присоединим его к прототипу HashTable, чтобы мы могли его использовать.

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

Чтобы добавить свойство в нашу структуру данных, мы сначала вычисляем index, используя нашу хеш-функцию, описанную ранее. Это даст нам значение между 0 и пределом хранения, который мы определили ранее, _limit. Оттуда мы проверяем наш массив _storage, чтобы увидеть, существует ли уже что-то по этому индексу. Если там ничего нет, мы создадим кортеж из нашей пары key и value и поместим его в массив. В противном случае, если что-то уже существует по этому индексу, мы пройдемся по существующему массиву и сравним ключи. Если этот ключ уже существует, обновите значение, связанное с этим ключом. Если нет, мы добавим его в конец массива. Наконец, мы обновим это свойство в _storage array и увеличим наше значение _count, чтобы правильно отслеживать текущее количество свойств.

Теперь, когда наше значение _count обновлено, нам нужно проверить правильность размера нашей хэш-таблицы. Решение о том, когда изменять размер вашей хеш-таблицы, зависит главным образом от соображений пространства и времени, но ради демонстрации мы решили удвоить размер, когда коэффициент загрузки или процент используемой в настоящее время емкости превышает 75. % порог. Для этого мы сбросим наши переменные _storage и _count, удвоим наши _limit и, самое главное, перефразируем весь наш перечень свойств. Чтобы выполнить повторное хеширование, мы пройдемся по нашей вложенной структуре хранения, соберем все пары в плоский массив, а затем рекурсивно вызовем наш метод insert для каждой пары.

Получить метод

Метод retrieve значительно проще нашего метода insert, но не менее важен. Чтобы получить значение, связанное с конкретным key, нам нужно вычислить index, используя точно такую ​​же хэш-функцию (помните, что наша хеш-функция повторяема). Затем мы выполняем поиск в нашем массиве _storage в этом index и перебираем результирующий массив, чтобы найти соответствующий key. Посмотрите ниже, чтобы увидеть, как это реализовано в JavaScript.

Удалить метод

Метод remove полностью аналогичен нашему методу insert, описанному ранее. Мы вычисляем index, находим соответствующее key, если оно существует, удаляем это значение из вложенного массива и уменьшаем наше _count. Затем, если результат меньшего количества свойств приводит к тому, что коэффициент загрузки становится ниже нашего нижнего предела (в данном случае 25%), мы уменьшаем размер хранилища вдвое, используя аналогичный рекурсивный алгоритм из нашего метода insert. Вы можете увидеть реализацию JavaScript ниже.

Заключение

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

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

Первоначально опубликовано на https://codingbootcampguides.com автором Dylan Feldman.

Дополнительные материалы на PlainEnglish.io. Подпишитесь на нашу бесплатную еженедельную рассылку новостей. Подпишитесь на нас в Twitter, LinkedIn, YouTube,и Discord. Заинтересованы в Взлом роста? Ознакомьтесь с разделом Схема.