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

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

Чтобы найти информацию об этой части, вам нужно просто перейти к этому конкретному ящику.

Давайте углубимся 😁

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

Применение хеш-функций в реальном мире:

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

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

Индексирование0️⃣1️⃣2️⃣… . Хэш-таблицы можно использовать для индексации больших наборов данных, например, найденных в базах данных или поисковых системах. Сопоставляя элементы данных с определенными индексами в массиве, становится намного быстрее извлекать определенные элементы данных или выполнять поиск.

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

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

Время приготовления…

Давайте реализуем хеш-функцию:

class HashTable {
  constructor(size) {
    this.size = size;
    this.table = new Array(size);
  }

  hash(key) {
    let sum = 0;
    for (let i = 0; i < key.length; i++) {
      sum += key.charCodeAt(i);
    }
    return sum % this.size;
  }

  insert(key, value) {
    let index = this.hash(key);
    if (!this.table[index]) {
      this.table[index] = [];
    }
    this.table[index].push([key, value]);
  }

  search(key) {
    let index = this.hash(key);
    if (!this.table[index]) {
      return null;
    }
    for (let i = 0; i < this.table[index].length; i++) {
      if (this.table[index][i][0] === key) {
        return this.table[index][i][1];
      }
    }
    return null;
  }
}


const hashTable = new HashTable(10);
hashTable.insert("🐈", "meow");
hashTable.insert("🐶", "bark");
hashTable.insert("🐦", "tweet");

console.log(hashTable.search("🐈")); // "meow"
console.log(hashTable.search("🐶")); // "bark"
console.log(hashTable.search("🐦")); // "tweet"
console.log(hashTable.search("🐸")); // null

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