Структура данных 101: реализация хеш-таблиц в JavaScript

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

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

Сегодня мы рассмотрим:

  • Что такое хеш-таблица?
  • Что такое хеш-функция?
  • Коллизии хеш-таблиц
  • Как реализовать хеш-таблицу
  • Заключение и вопросы интервью

Основные структуры данных для кодирования интервью с практической практикой

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

Структуры данных для собеседований по программированию на JavaScript

Что такое хеш-таблица?

хеш-таблица (часто называется хэш-картой ) — это структура данных, которая сопоставляет ключи со значениями. Хеш-таблицы эффективно сочетают операции lookup , insert и delete . Ключ отправляется в хеш-функцию, которая выполняет с ним арифметические операции. Результат (называемый хеш-значением или хешем) является индексом пары «ключ-значение».

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

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

Производительность хеш-таблицы зависит от трех фундаментальных факторов: хеш-функции, размера хеш-таблицы и метода обработки конфликтов.

Хеш-таблицы состоят из двух частей:

  • Объект: Объект с таблицей, в которой хранятся данные. В массиве хранятся все записи «ключ-значение» в таблице. Размер массива должен быть установлен в соответствии с ожидаемым объемом данных.
  • Хеш-функция (или функция сопоставления): Эта функция определяет индекс нашего ключа -значная пара. Это должна быть односторонняя функция и создавать разные хеш-коды для каждого ключа.

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

Использование хеш-таблицы

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

С точки зрения временной сложности операция выглядит так: 0 ( 1 ) 0 (1) 0 (1). В среднем поиск по хеш-таблице более эффективен, чем другие структуры данных по поиску по таблице. Некоторые распространенные применения хэш-таблиц:

  • Индексирование базы данных
  • Кеши
  • Уникальное представление данных
  • Поиск в несортированном массиве
  • Поиск в отсортированном массиве с помощью двоичного поиска

Хеш-таблицы и деревья

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

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

Хеш-таблицы могут работать в постоянное время, в то время как деревья обычно работают с семантикой O ( l o g n ) O (log n) математика> O (вход). В худшем случае производительность хеш-таблиц может быть ниже O ( n ) O (n) O (n ). Однако дерево AVL будет поддерживать O ( l o g n ) O (log n) O (logn) в худшем случае.

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

Что такое хеш-функция?

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

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

Общие хэш-функции

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

Арифметическая модульная: В этом подходе мы берем модульную структуру ключа с размер списка/массива: index = key MOD tableSize . Таким образом, index всегда будет находиться между 0 и tableSize - 1 .

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

Folding: Этот подход включает в себя разделение ключа на маленькие фрагментов и применяя разные арифметические стратегии к каждому фрагменту.

Коллизии хэш-таблиц

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

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

  1. Линейное зондирование: Линейное зондирование работает, пропуская индекс, который уже заполнен. Этого можно добиться, добавив значение смещения к уже вычисленному индексу. Если этот индекс также заполнен, добавьте его снова и так далее.

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

  1. Цепочка: В стратегии цепочки каждый слот нашей хеш-таблицы содержит указатель на другую структуру данных, такую ​​как связанный список или дерево. Каждая запись в этом индексе будет вставлена ​​в связанный список для этого индекса.

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

  1. Изменение размера массива или списка: Другой способ уменьшить коллизии — изменить размер списка или массива. Мы можем установить порог, и как только он будет превышен, мы можем создать новую таблицу, которая будет вдвое больше оригинальной. Все, что нам нужно сделать, это скопировать элементы из предыдущей таблицы.

    Изменение размера списка или массива значительно снижает коллизии, но сама функция требует больших затрат. Следовательно, мы должны быть осторожны с порогом, который мы устанавливаем. Типичным соглашением является установка порога на 0,6, что означает, что при заполнении 60% таблицы необходимо выполнить операцию изменения размера.

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

    Следующая функция является примером двойного хеширования:

  (firstHash (ключ) + i * secondHash (ключ))% tableSize 

Основные структуры данных для кодирования интервью.

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

Структуры данных для собеседований по программированию на JavaScript

Как реализовать хеш-таблицу

Чтобы реализовать хеш-таблицу с помощью JavaScript, мы сделаем три вещи: создадим класс хеш-таблицы, добавим хеш-функцию и реализовать метод добавления пар ключ/значение в нашу таблицу.

Сначала давайте создадим класс HashTable .

 class HashTable {constructor () {this.values ​​= {  };  this.length = 0;  this.size = 0;  }} 

Конструктор содержит объект, в котором мы собираемся хранить значения, длину значений, и весь размер хеш-таблицы: это означает, сколько сегментов содержит хеш-таблица. Мы будем хранить наши данные в этих бакетах.

Затем нам нужно реализовать простую функцию хеширования.

 calculateHash (key) {return key.toString (). length% this. size;} 

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

Наконец, нам нужен метод для вставки пар ключ/значение. Взгляните на код и убедитесь в этом в действии:

 add (ключ, значение) {const hash = this.calculateHash (key);  если (! this.values.hasOwnProperty (хэш)) {this.values ​​[хэш] = {};  } если (! this.values ​​[хэш] .hasOwnProperty (ключ)) {this.length ++;  } this.values ​​[hash] [key] = value;} 

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

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

 class HashTable {constructor () {this.values ​​= {};  this.length = 0;  this.size = 0;  } calculateHash (ключ) {return key.toString (). length% this.size;  } добавить (ключ, значение) {const hash = this.calculateHash (ключ);  Если (! This.values.hasOwnProperty (hash)) {this.values ​​[hash] = {};  } если (! this.values ​​[хэш] .hasOwnProperty (ключ)) {this.length ++;  } this.values ​​[хэш] [ключ] = значение;  } поиск (ключ) {const hash = this.calculateHash (ключ);  if (this.values.hasOwnProperty (hash) && this.values ​​[hash] .hasOwnProperty (key)) {вернуть this.values ​​[hash] [key];  } else {return null;  }}}//создаем объект типа hash tableconst ht = new HashTable ();//добавляем данные в хеш-таблицу htht.add ("Канада", "300"); ht.add ("Германия", "100"  ); ht.add ("Италия", "50");//searchconsole.log (ht.search ("Италия")); 

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

Реализация с Bucket Chaining

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

Все элементы с одним и тем же хеш-ключом будут сохранены в массиве по этому индексу. В структурах данных эти массивы называются корзинами. Размер хеш-таблицы установлен как n ∗ m n*m n ∗ m, где n n n — количество ключей, которое он может удерживать, а mm m — количество слотов в каждой корзине.

Мы начнем с создания простого HashEntry код> класс. Как обсуждалось ранее, типичная запись хэша состоит из трех элементов данных: ключа, значения и ссылки на новую запись.

 class HashEntry {конструктор (ключ, данные) {this.key = key; //данные для хранения this.value = data; //ссылка на новую запись this.next = null;  }} let entry = new HashEntry (3, "Educative"); console.log (String (entry.key) + "," + entry.value); 

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

 class HashTable {//Конструктор конструктора () {//Размер HashTable this.slots = 10; //Текущие записи в таблице//Используется при изменении размера таблицы, когда половина таблицы заполняется this.size = 0; //Массив объектов HashEntry (по умолчанию все None) this.bucket = [];  для (var я = 0; я  

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

//Хеш-функция getIndex (key) {let index = key% this.slots; return index;} 

Итак, мы идем! Следующими шагами будет последовательное выполнение операций поиска, вставки и удаления.

Подведение итогов и вопросы интервью

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

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

  • Реализовать вставку, удаление и поиск
  • Проверить, не пересекаются ли массивы.
  • Найти симметричная пара в массиве
  • Найдите две пары, такие что a + b = c + d a + b = c + d a + b = c + d
  • Найдите два числа, которые в сумме составляют «значение»
  • Удаление дубликатов из связанного списка с помощью хэш-таблиц
  • Как вставить новое значение в хэш-ключ, который уже занят
  • и многое другое

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

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

Удачного обучения!

Читать далее о JavaScript

  • Повысьте свои навыки JavaScript с помощью 10 задач по программированию
  • 15 советов по JavaScript: лучшие практики по упрощению кода
  • Лучшие шаблоны проектирования JavaScript для собеседований по программированию
Оцените статью
nanomode.ru
Добавить комментарий