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

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

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

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

Что такое хеш-таблица?
Что такое хэш-функция?
Коллизии хеш-таблиц
Как реализовать хэш-таблицу
Подведение итогов и вопросы интервью

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

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

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

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

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

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

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

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

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

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

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

Индексация базы данных
Тайники
Уникальное представление данных
Поиск в несортированном массиве
Поиск в отсортированном массиве с использованием бинарного поиска

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(firstHash(key) + i * secondHash(key)) % tableSize

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

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

Во-первых, давайте создадим класс HashTable.

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

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

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

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

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

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

add(key, value) {
  const hash = this.calculateHash(key);
  if (!this.values.hasOwnProperty(hash)) {
     this.values[hash] = {};
  }
  if (!this.values[hash].hasOwnProperty(key)) {
     this.length++;
  }
  this.values[hash][key] = value;
}

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

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

class HashTable {
  constructor() {
    this.values = {};
    this.length =  0;
    this.size =  0;
  }
  calculateHash(key) {
    return key.toString().length % this.size;
  }
  add(key, value) {
    const hash = this.calculateHash(key);
    If (!this.values.hasOwnProperty(hash)) {
      this.values[hash] = {};
    }
    if (!this.values[hash].hasOwnProperty(key)) {
       this.length++;
    }
    this.values[hash][key] = value;
  }
  search(key) {
     const hash = this.calculateHash(key);
     if (this.values.hasOwnProperty(hash) && this.values[hash].hasOwnProperty(key)) {
       return this.values[hash][key];
     } else {
       return null;
     }
  }
}
//create object of type hash table
const ht = new HashTable();
//add data to the hash table ht
ht.add("Canada", "300");
ht.add("Germany", "100");
ht.add("Italy", "50");
//search
console.log(ht.search("Italy"));

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

Реализация с цепочкой корзин

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

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

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

class HashEntry{
    constructor(key, data){
        this.key = key;
        // data to be stored
        this.value = data;
        // reference to new entry
        this.next = null;
    }
}
let entry = new HashEntry(3, "Educative");
console.log (String(entry.key) + ", " + entry.value);
-->
3, Educative

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

class HashTable{
  //Constructor
  constructor(){
    //Size of the HashTable
    this.slots = 10;
    //Current entries in the table
    //Used while resizing the table when half of the table gets filled
    this.size = 0;
    //Array of HashEntry objects (by deafult all None)
    this.bucket = [];
    for (var i=0; i<this.slots; i++){
      this.bucket[i]=null;
    }
  }
  //Helper Functions  
  get_size(){
    return this.size;
  }
  isEmpty(){
    return this.get_size() == 0;
  }
}
let ht = new HashTable();
console.log(ht.isEmpty());
-->
true

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

//Hash Function
getIndex(key){
    let index = key % this.slots;
    return index;
}

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

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

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

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

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

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

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

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

Продолжить чтение о JavaScript на Educative

Начать обсуждение

Какой учебник по JavaScript вы хотели бы прочитать следующим? Была ли эта статья полезна? Дайте нам знать в комментариях ниже!