Як реалізувати просту хеш-таблицю в JavaScript

Наскільки це красиво {}?

Це дозволяє вам зберігати значення за ключем та отримувати їх дуже економічно ( O(1)докладно про це далі).

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

Проблема

Уявіть, що ви створюєте нову мову програмування: ви починаєте з досить простих типів (рядків, цілих чисел, плаваючих знаків ...), а потім переходите до реалізації дуже базових структур даних. Спочатку ви придумуєте масив ( []), потім - хеш-таблицю (інакше відому як словник, асоціативний масив, хеш-карту, карту і… список можна продовжувати).

Ви коли-небудь задавались питанням, як вони працюють? Як вони такі чортові швидкі?

Ну, припустимо, що JavaScript не мав {}або new Map(), і давайте реалізуємо наш власний DumbMap!

Примітка про складність

Перш ніж ми почнемо котити м'яч, нам слід зрозуміти, як працює складність функції: Вікіпедія має гарне оновлення обчислювальної складності, але я додаю коротке пояснення для ледачих.

Складність вимірює, скільки кроків вимагає наша функція - чим менше кроків, тим швидше виконання (також відоме як "час роботи").

Давайте подивимось на наступний фрагмент:

function fn(n, m) { return n * m}

Обчислювальна складність (відтепер просто “складність”) fnє O(1), це означає, що вона є постійною (її можна прочитати O(1)як “ вартість одна ”): незалежно від того, які аргументи ви передаєте , платформа, яка запускає цей код, повинна виконати лише одну операцію (помножити nна m). Знову ж таки, оскільки це одна операція, вартість називається O(1).

Складність вимірюється припускаючи, що аргументи вашої функції можуть мати дуже великі значення. Давайте розглянемо цей приклад:

function fn(n, m) { let s = 0
 for (i = 0; i < 3; i++) { s += n * m }
 return s}

Можна подумати, що його складність O(3), правда?

Знову ж таки, оскільки складність вимірюється в контексті дуже великих аргументів, ми схильні «скидати» константи і розглядати O(3)те саме, що O(1). Отже, навіть у цьому випадку ми сказали б, що складність fnє O(1). Незалежно від того, в чому цінність nі значення m, ви в кінцевому підсумку завжди робите три операції - що, знову ж таки, є постійною вартістю (отже O(1)).

Зараз цей приклад трохи інший:

function fn(n, m) { let s = []
 for (i = 0; i < n; i++) { s.push(m) }
 return s}

Як бачите, ми повторюємо стільки разів, скільки значення n, яке може складати мільйони. У цьому випадку ми визначаємо складність цієї функції як O(n), оскільки вам потрібно буде виконати стільки операцій, скільки значення одного з ваших аргументів.

Інші приклади?

function fn(n, m) { let s = []
 for (i = 0; i < 2 * n; i++) { s.push(m) }
 return s}

Цей приклад циклічно 2 * nповторює, що означає складність O(2n). Оскільки ми вже згадували, що константи «ігноруються» під час обчислення складності функції, цей приклад також класифікується як O(n).

Ще один?

function fn(n, m) { let s = []
 for (i = 0; i < n; i++) { for (i = 0; i < n; i++) { s.push(m) } }
 return s}

Тут ми зациклюємось nі знову зациклюємося всередині основного циклу, тобто складність “квадрат” ( n * n): якщо n2, ми будемо запускати s.push(m)4 рази, якщо 3 ми будемо запускати його 9 разів, і так далі.

У цьому випадку складність функції називається O(n²).

Останній приклад?

function fn(n, m) { let s = []
 for (i = 0; i < n; i++) { s.push(n) }
 for (i = 0; i < m; i++) { s.push(m) }
 return s}

У цьому випадку ми не маємо вкладених циклів, але ми два рази перебираємо два різних аргументи: складність визначається як O(n+m). Кристально чистий.

Тепер, коли ви щойно отримали короткий вступ (або оновлення) про складність, дуже легко зрозуміти, що функція зі складністю O(1)виконується набагато краще, ніж та, з якою O(n).

Хеш-таблиці мають O(1)складність: якщо говорити неспеціалістично, вони надшвидкі . Йдемо далі.

(Я начебто лежав на хеш-таблицях, завжди маючи O(1)складність, але просто читаючи далі;))

Побудуємо (німу) хеш-таблицю

Наша хеш-таблиця має 2 простих методи - set(x, y)і get(x). Почнемо писати код:

І давайте реалізуємо дуже простий, неефективний спосіб зберігати ці пари ключ-значення та отримувати їх пізніше. Спочатку ми зберігаємо їх у внутрішньому масиві (пам’ятайте, ми не можемо використовувати, {}оскільки впроваджуємо {}- розум!):

Тоді справа лише в тому, щоб отримати потрібний елемент зі списку:

Наш повний приклад:

Наш DumbMap дивовижний! Це працює прямо з коробки, але як буде діяти, коли ми додамо велику кількість пар ключ-значення?

Спробуємо простий орієнтир. Спочатку ми спробуємо знайти неіснуючий елемент у хеш-таблиці з дуже малою кількістю елементів, а потім спробуємо те ж саме в одному з великою кількістю елементів:

Результати? Не так обнадійливо:

with very few records in the map: 0.118mswith lots of records in the map: 14.412ms

У нашій реалізації нам потрібно прокрутити всі елементи всередині this.list, щоб знайти один із відповідним ключем. Вартість є O(n), і це досить жахливо.

Зробіть це швидко (е)

Нам потрібно знайти спосіб уникнути перегляду нашого списку: час повернути хеш у хеш-таблицю .

Ви коли-небудь задавались питанням, чому ця структура даних називається хеш- таблицею? Це тому, що функція хешування використовується на клавішах, які ви встановлюєте та отримуєте. Ми використаємо цю функцію, щоб перетворити наш ключ на ціле число iі зберегти наше значення в індексі iнашого внутрішнього списку. Оскільки доступ до елемента за його індексом зі списку має постійну вартість ( O(1)), тоді хеш-таблиця також матиме вартість O(1).

Давайте спробуємо це:

Тут ми використовуємо рядок-хеш-модуль, який просто перетворює рядок у числовий хеш. Ми використовуємо його для зберігання та отримання елементів за індексом hash(key)нашого списку. Результати?

with lots of records in the map: 0.013ms

Ш - О - Ш. Про це я говорю!

Нам не потрібно циклічно перебирати всі елементи у списку, а отримання елементів із них DumbMapвідбувається дуже швидко!

Дозвольте сказати це якомога прямолінійніше: хешування робить хеш-таблиці надзвичайно ефективними . Ніякої магії. Нічого більше. Нада. Просто проста, розумна, геніальна ідея.

Вартість вибору правильної функції хешування

Звичайно, вибір функції швидкого хешування дуже важливий. Якщо наша робота hash(key)пробіжить за кілька секунд, наша функція буде досить повільною, незалежно від її складності.

У той же час дуже важливо переконатись, що наша функція хешування не спричиняє багато зіткнень , оскільки вони можуть згубно вплинути на складність нашої хеш-таблиці.

Розгублений? Давайте детальніше розглянемо зіткнення.

Зіткнення

Ви можете подумати: « А, хороша хеш-функція ніколи не породжує зіткнень! ”: Ну, поверніться до реального світу і подумай ще раз. Google зміг створити зіткнення для алгоритму хешування SHA-1, і це лише питання часу чи обчислювальної потужності, перш ніж хеш-функція зламається і поверне той самий хеш для 2 різних входів. Завжди вважайте, що ваша функція хешування породжує зіткнення, і застосовуйте правильний захист від таких випадків.

На прикладі, спробуємо використати hash()функцію, яка генерує багато зіткнень:

Ця функція використовує масив з 10 елементів для зберігання значень, що означає, що елементи, ймовірно, будуть замінені - неприємна помилка в нашому DumbMap:

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

Як ви могли помітити, тут ми повертаємось до нашої початкової реалізації: зберігаємо список пар ключ-значення і прокручуємо кожну з них. Це буде досить повільно, коли для певного індексу списку буде багато зіткнень.

Давайте порівняємо це за допомогою власної hash()функції, яка генерує індекси від 1 до 10:

with lots of records in the map: 11.919ms

та за допомогою хеш-функції from string-hash, яка генерує випадкові індекси:

with lots of records in the map: 0.014ms

Вау! Існує вартість вибору правильної хеш-функції - досить швидкої, щоб вона не сповільнювала наше виконання сама по собі, і досить хорошої, щоб не спричиняти багато зіткнень.

Загалом O (1)

Пам'ятаєте мої слова?

Hashtables мають O(1)складність

Ну, я збрехав: складність хеш-таблиці залежить від вибраної вами функції хешування. Чим більше зіткнень ви створюєте, тим більше тяжіє складність O(n).

Така функція хешування, як:

function hash(key) { return 0}

означало б, що наша хеш-таблиця має складність O(n).

Ось чому, загалом, обчислювальна складність має три міри: найкращий, середній та найгірший сценарії. Хеш-таблиці мають O(1)складність у найкращому та середньому сценаріях, але підпадають O(n)під найгірший сценарій.

Пам'ятайте: хороша хеш-функція є ключем до ефективної хеш-таблиці - ні більше, ні менше.

Більше про зіткнення ...

Техніка, яку ми використовували для виправлення DumbMapвипадків зіткнень, називається окремим ланцюжком: ми зберігаємо всі пари ключів, що генерують зіткнення, у списку та перебираємо їх.

Інший популярний прийом - це відкрита адресація:

  • у кожному індексі нашого списку ми зберігаємо одну і одну єдину пару ключ-значення
  • при спробі зберегти пару в індексі x, якщо вже є пара ключ-значення, спробуйте зберегти нашу нову пару за адресоюx + 1
  • якщо x + 1взяли, спробуйте x + 2і так далі ...
  • при отриманні елемента, хеш ключ і подивіться, чи відповідає елемент у цій позиції ( x) нашому ключу
  • якщо ні, спробуйте отримати доступ до елемента в позиції x + 1
  • промийте і повторюйте, поки не дійдете до кінця списку, або коли знайдете порожній індекс - це означає, що наш елемент відсутній у хеш-таблиці

Розумний, простий, елегантний і зазвичай дуже ефективний!

Поширені запитання (або TL; DR)

Чи хеш-таблиця хешує значення, які ми зберігаємо?

Ні, ключі хешуються, щоб їх можна було перетворити на ціле число i, і ключі, і значення зберігаються на місці iу списку.

Чи генерують функції хешування, що використовуються хеш-таблицями, зіткнення?

Абсолютно - тому хеш-таблиці реалізовані із стратегіями захисту, щоб уникнути неприємних помилок.

Чи використовують хеш-таблиці внутрішній список чи пов'язаний список?

Це залежить, обидва можуть працювати. У наших прикладах ми використовуємо масив JavaScript ( []), який можна динамічно змінювати:

> a = []
> a[3] = 1
> a[ , 1 ]

Чому ви вибрали JavaScript для прикладів? Масиви JS - ХЕШ-таблиці!

Наприклад:

> a = [][]
> a["some"] = "thing"'thing'
> a[ some: 'thing' ]
> typeof a'object'

Я знаю, проклятий JavaScript.

JavaScript є «універсальним» і, мабуть, найпростішою для розуміння мовою при перегляді зразка коду. JS може бути не найкращою мовою, але я сподіваюся, що ці приклади досить зрозумілі.

Ваш приклад - справді хороша реалізація хеш-таблиці? Це насправді ТАК просто?

Ні, зовсім ні.

Погляньте на «впровадження хеш-таблиці в JavaScript» від Метта Цунерта, оскільки це дасть вам трохи більше контексту. Існує ще багато чого для вивчення, тому я б також запропонував вам перевірити:

  • Курс Пола Кубе з хеш-таблиць
  • Реалізація нашої власної хеш-таблиці з окремим ланцюжком на Java
  • Алгоритми, 4-е видання - Хеш-таблиці
  • Створення швидкої хеш-таблиці

Наприкінці…

Хеш-таблиці - це дуже розумна ідея, яку ми використовуємо регулярно: незалежно від того, створюєте ви словник на Python, асоціативний масив у PHP або карту в JavaScript. Всі вони поділяють однакові концепції і чудово працюють, щоб дозволити нам зберігати та отримувати елемент за допомогою ідентифікатора за (найімовірніше) постійної вартості.

Сподіваюся, вам сподобалась ця стаття, і не соромтеся поділитися зі мною своїми відгуками.

Особлива подяка Джо, який допоміг мені, переглянувши цю статтю.

Адіос!