Как да внедрите проста хеш таблица в JavaScript

Програмиране

Колко е красиво {}?

Той ви позволява да съхранявате стойности по ключ и да ги извличате по много рентабилен начин ( O(1), повече за това по-късно).

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

Проблемът

Представете си, че изграждате нов език за програмиране: започвате с доста прости типове (низове, цели числа, плувки, ...) и след това продължавате да прилагате много основни структури от данни. Първо измисляте масива ( []), след това идва хеш таблицата (иначе известна като речник, асоциативен масив, hashmap, map и ... списъкът продължава).

Чудили ли сте се как работят? Как са толкова адски бързи?

Е, да кажем, че 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): ако nе 2, ще стартираме 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

W - O - W. За това говоря!

Не е нужно да преглеждаме всички елементи в списъка и извличането на елементи от тях DumbMapе супер бързо!

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

Разходите за избор на правилната хешираща функция

Разбира се, избирането на функция за бързо хеширане е много важно. Ако нашите hash(key)работи за няколко секунди, нашата функция ще бъде доста бавна, независимо от сложността си.

В същото време е много важно да се уверите, че нашата хешираща функция не води до много сблъсъци , тъй като те биха били в ущърб на сложността на нашата хеш таблица.

Объркан? Нека разгледаме по-отблизо сблъсъците.

Сблъсъци

Може да си помислите „ А, добрата функция на хеширане никога не генерира сблъсъци! ”: Добре, върнете се в реалния свят и помислете отново. Google успя да създаде сблъсъци за алгоритъма за хеширане SHA-1 и е просто въпрос на време или изчислителна мощност, преди функцията за хеширане да се счупи и да върне същия хеш за 2 различни входа. Винаги приемайте, че вашата хешираща функция генерира сблъсъци и прилагайте правилната защита срещу такива случаи.

В конкретен случай, нека се опитаме да използваме hash()функция, която генерира много сблъсъци:

Тази функция използва масив от 10 елемента за съхраняване на стойности, което означава, че е вероятно елементите да бъдат заменени - неприятна грешка в нашата DumbMap:

За да разрешим проблема, можем просто да съхраняваме множество двойки ключ-стойност в един и същ индекс. Така че нека изменим нашата хеш таблица:

Както може да забележите, тук се връщаме към първоначалната ни реализация: съхраняваме списък от двойки ключ-стойност и прелистваме през всяка от тях. Това ще бъде доста бавно, когато има много сблъсъци за определен индекс на списъка.

Нека сравним това с помощта на нашата собствена hash()функция, която генерира индекси от 1 до 10:

with lots of records in the map: 11.919ms

и с помощта на хеш функцията от 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).

Ето защо, като цяло, изчислителната сложност има три мерки: най-добрия, средния и най-лошия сценарий. Hashtables имат 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. Всички те споделят едни и същи концепции и прекрасно работят, за да ни позволят да съхраняваме и извличаме елемент чрез идентификатор, при (най-вероятно) постоянна цена.

Надявам се, че тази статия ви е харесала и не се колебайте да споделите с мен отзивите си.

Специална благодарност отива на Джо, който ми помогна, като разгледах тази статия.

Адиос!