Представьте, что у вас есть куча информации, которую вы хотите отслеживать, например, имя клиента. Вы можете записать всю эту информацию на листе бумаги и сложить листы в большую стопку. Если вы хотите найти какую-то конкретную информацию, вы должны просмотреть всю стопку только для того, чтобы найти ее. Это займет много времени.
Хеш-таблица похожа на картотеку 🗄️с кучей ящиков и отделений. Каждая часть информации записывается на отдельном листе бумаги и помещается в определенный ящик.
Чтобы найти информацию об этой части, вам нужно просто перейти к этому конкретному ящику.
Давайте углубимся 😁
В компьютерной системе 🖥️ хэш-таблица похожа на виртуальный картотечный шкаф 🗄️. Она использует специальную функцию, называемую хеш-функцией🧠, чтобы выяснить, в какой ящик поместить каждую часть информации.
Применение хеш-функций в реальном мире:
Поиск🔎: хеш-таблицы можно использовать для эффективного поиска элементов в большом наборе данных путем сопоставления элементов с определенными индексами в массиве с помощью хеш-функции. Это позволяет выполнять операции поиска с постоянным временем, что намного быстрее, чем последовательный поиск по всему набору данных.
Кэширование📁. Хэш-таблицы можно использовать для хранения недавно использованных данных в кеше для повышения производительности приложения. Когда запрашивается часть данных, приложение может сначала проверить кэш, чтобы увидеть, хранятся ли там данные, что может быть намного быстрее, чем доступ к данным из их исходного источника.
Индексирование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
извлекает значение для заданного ключа путем хеширования ключа и поиска пары ключ-значение в результирующем индексе.