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

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

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

Содержание

Что такое хеш-таблица?
Хеш-таблицы состоят из двух частей:
Использование хеш-таблиц
Хеш-таблицы против деревьев
Что такое хеш-функция?
Общие хеш-функции
Коллизии хеш-таблиц
Как реализовать хеш-таблицу
Реализация с помощью Bucket Chaining
Подведение итогов и вопросы интервью

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 фактически реализуются с помощью самих хэш-таблиц! Многие языки программирования также предоставляют поддержку хеш-таблиц либо в виде встроенных ассоциативных массивов, либо в виде стандартных библиотечных модулей.

Реализация с помощью Bucket Chaining

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

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

Начнем с создания простого 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);

Теперь мы создадим 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());

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

//Hash Function

getIndex(key){

let index = key % this.slots;

return index;

}

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

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

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

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