Pora na kolejną strukturę danych. Tym razem będzie to tablica z haszowaniem, zwana także mapą z haszowaniem. Podobnie jak słownik, jest to sposób na implementację tablicy asocjacyjnej (takiej, w której użytkownik ma dostęp do wartości dzięki kluczom). Atutem tablicy z haszowaniem jest to, że dostęp ten jest bardzo szybki.
Tajemnicą szybkiego dostępu do danych w tablicach haszujących są funkcje haszujące. Tłumaczą one wartość na klucz. Następnie pod tak uzyskany klucz przypisują wartość. Dzięki funkcjom haszującym, program od razu wie gdzie szukać danej wartości.
Rodzajów funkcji haszujących jest naprawdę sporo. Ja użyję bardzo prostej i popularnej wersji, wykorzystującej wartości ASCII (jeżeli nie wiesz czym są wartości ASCII, warto zgłębić temat. Zerknij na przykład na artykuł na wikipedii).
Metoda ta polega na pobraniu i zsumowaniu wartości ASCII wszystkich znaków, przekazanych danych. W ten sposób powstanie indeks, który wykorzystam jako klucz dodawanej wartości. Jako przykład, słowo Maja składa się z czterech znaków (w nawiasach ich wartości ASCII) M(77), a(97), j(106) oraz a(97). Suma wartości w nawiasach daje mi 377. To będzie indeks pod którym zamieszczę dane: „Maja”.
Ale 377 to trochę dużo, a „Maja” to tylko cztery litery. Tablice przechowujące informacje szybko staną się naprawdę duże. Rosnąca w nieskończoność tablica to nie jest dobra rzecz. Szczególnie w językach, niższego poziomu, w których aby dobrze zarządzać pamięcią, trzeba deklarować rozmiar tablicy już podczas jej tworzenia. Rozwiązaniem tego problemu jest stworzenie tablicy o rozmiarze równym liczbie pierwszej np 137. Wyniki haszowania, będę dzielił przez tę liczbę. Ostateczny indeks danych to reszta tego dzielenia. Dzięki temu będę zawsze otrzymywał wynik, z przedziału pomiędzy 0 a 136. Dokładnie takich indeksów potrzebuję.
Dzięki opisanej wyżej technice, mogę dodawać do tablicy haszującej dane tak samo jak do słownika. Podam klucz oraz wartość. Klucz będzie zahaszowany a wartość zostanie umieszczona pod odpowiednim indeksem. Dlaczego to podejście jest lepsze niż podejście słownikowe? Ponieważ, nie będę musiał przeszukiwać całego zbioru danych w poszukiwaniu klucza. Program od razu wie, gdzie dane się znajdują 🙂 .
Wszystko wygląda super, ale jest haczyk. Nie trzeba długo się zastanawiać, żeby dojść do wniosku, że coś jest nie tak z powyższymi założeniami. Problem polega na tym, że na pewno jest więcej niż jedna liczba, która po podzieleniu przez 137, da resztę, na przykład, 1. Co jeśli dwa podane przeze mnie klucza zahaszują się tak samo? W tej strukturze danych nazywa się to kolizją.
Tak jak z metodami haszowania, metod na obsługiwanie kolizji też jest kilka. Ja posłużę się metodą łańcuchową. Polega ona na tym, że elementy tablicy haszującej to też struktury danych. Jeżeli wystąpi kolizja, program umieszcza dane na kolejnym wolnym miejscu w strukturze wskazywanej przez klucz. Niestety podnosi to trochę złożoność obliczeniową, ale coś za coś. Przynajmniej w wyniku kolizji nie traci się danych.
Struktury danych w JavaScripcie – Tablica z haszowaniem – kod
Skoro teoria już za mną, czas na implementację tej struktury w JavaScripcie. Oto kod klasy HashTable:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
var HashTable = function(){ this.table = new Array(137); this.initHash = function() { for (var i = 0; i < this.table.length; ++i) { this.table[i] = []; } } this.hash = function(key){ var hash = 0; for (var i = 0; i < key.length; i++) { hash += key.charCodeAt(i); } return hash % 137; }; this.put = function(key, value){ var index = this.hash(key); var i = 0; if(this.table[index][0] === undefined){ this.table[index][0] = key; this.table[index][1] = value; } else { while(this.table[index][i] !== undefined) { i++; } this.table[index][i] = key; this.table[index][i+1] = value; } }; this.get = function(key) { var index = this.hash(key); var i = 0; if(this.table[index][0] !== undefined) { if(!this.table[index].length > 2) { return this.table.index[1]; } else { while(this.table[index][i] != key){ i+=2; } return this.table[index][i+1]; } } else { return 'no such entry' } }; this.displayTable = function(){ var n = 0; for (var i = 0; i < this.table.length; ++i) { if (this.table[i][0] !== undefined) { console.log(i + ": " + this.table[i]); } } }; }; |
Jedyne pole w klasie to table. Jest to tablica, którą inicjalizuję za pomocą operatora new. Dzięki temu, mogę podać jej początkowy rozmiar. Pozostałe elementy klasy to metody, służące do obsługi struktury danych.
Metody initHash oraz hash, to metody pomocnicze, nie będą bezpośrednio stosowane przez użytkownika. initHash służy do wypełnienia głównej tablicy pustymi tablicami. Musi ona być odpalona po stworzeniu nowej instancji struktury. Puste tablice będą potrzebne na wypadek kolizji danych.
Metoda hash przyjmuje jeden argument. Jest to klucz, który będzie wykorzystywany do wyszukania przypisanej mu wartości. Przy pomocy pętli for, przechodzę przez każdy znak przekazanego argumentu. Używam javascriptowej metody charCodeAt aby pobrać wartość ASCII aktualnego znaku. Wartości są sumowane. Na końcu zwracana jest reszta z dzielenia sumy wartości ASCII i liczby 137. Metoda hash jest wykorzystywana przez dwie kolejne metody: put oraz get
put służy do dodawania nowych elementów. Przyjmuje dwa argumenty: klucz, po którym użytkownik może szukać danych, oraz dane, do tego klucza przypisane. Pierwsza rzeczą, którą wykonuje metoda jest zahaszowanie wartości klucza. W ten sposób otrzymuje indeks, pod którym należy umieścić wartość. W metodzie tworzę też pomocniczą zmienną i, która będzie wykorzysta w razie kolizji. W tym miejscu, program ma dwa możliwe scenariusze. Albo dany indeks głównej tablicy jest pusty (pierwszy element tablicy tego indeksu wynosi undefined), albo nie (kolizja). W pierwszym przypadku, klucz i wartość są po prostu zapisywane w wewnętrznej tablicy (w tej kolejności). Jeżeli wewnętrzna tablica posiada już jakieś wartości, metoda szuka pierwszego wolnego indeksu i wpisuje w niego klucz a w kolejny wartość.
Kolejna metoda to get. Przyjmuje ona jeden argument. Jest to klucz, po którym metoda szuka przypisanej mu wartości. Na początku klucz jest haszowany za pomocą metody hash. Tutaj również tworzę zmienną pomocniczą na wypadek jakby program trafił na indeks, pod którym znajduje się więcej niż jedna wartość. Tutaj możliwości są trzy: metoda get trafia na tablice zawierającą tylko jedną parę klucz/wartość, metoda trafia na tablicę zawierającą więcej niż 2 elementy, lub metoda trafia na pustą tablicę. W pierwszym wypadku po prostu zwracana jest wartość, czyli element wewnętrznej tablicy pod indeksem 1. W drugim przypadku, metoda przechodzi przez parzyste elementy wewnętrznej tablicy. Jeżeli któryś z nich równy jest kluczowi, zwracany jest kolejny element. W trzecim wypadku, metoda zwraca wiadomość, że dana wartość nie znajduje się w strukturze danych.
Ostatnia metoda to printTable. Wypisuje ona całą zawartość tablicy haszującej. Ta prosta metoda, po prostu przechodzi przez całą główną tablicę i wypisuje w konsoli jej elementy, jeśli nie są puste.
To cała struktura danych. Nie jest ona zbyt skomplikowana, chociaż tak jak zaznaczyłem na początku. Metod haszowania i obsługi kolizji jest bardzo wiele. Ja wykorzystałem dość proste rozwiązania, chociaż nie znaczy to, że mało efektywne. Zachęcam do poczytania na ten temat, niektóre algorytmy haszowania są naprawdę sprytne i można się wiele nauczyć studiując je.
Jeżeli coś jest nie jasne, zachęcam do zadawania pytań w komentarzach poniżej. Świetnym miejscem na kontakt ze mną jest też moja strona na facebooku. Zachęcam przy okazji do polubienia jej. Zawsze umieszczam tam informacje o nowych wpisach i nie tylko 🙂