Jak używać kluczy, czyli haszujemy wokoło i wesoło

Jakiś czas temu wspomniałem o chęci napisania miniartykułu dotyczącego haszowania. Z góry mówię, że moim celem nie jest przedstawienie wszystkich możliwości rozwiązania problemu transformacji kluczowej, tylko przybliżenie samej idei i korzyści, jakie mogą z tego płynąć. Nie będę również próbował udawać, że rozumiem wszystkie matematyczne zależności wyprowadzone we Wprowadzeniu do Algorytmów Cormena (i nie tylko), bo musiałbym wznieść się na wyżyny aktorstwa.

Z góry też przepraszam, jeśli kogoś będzie raził niezbyt formalny ton w jakim będę pisał – to nie ma być rozprawa naukowa na którą człowiek patrzy i modli się, aby to samo było na wikipedii albo w jakimś tutorialu (i to najlepiej przed sesją). Ten artykuł to swoisty pamiętnik początkującego dla początkujących, zawierający potrzebną teorię oraz przykład implementacji.

Haszowanie (lub transformacja kluczowa – nie tak często spotykana nazwa, ale moim zdaniem odpowiednia) może być równeż przetłumaczone jako mieszanie, rozpraszanie. Dość dobrze oddaje to charakterystykę całego mechanizmu – tablica haszująca to struktura, w której przechowujemy dane na takiej samej zasadzie jak w normalnej tablicy (czy innym kontenerze). Różnica jest taka, iż wkładając dany element, opisujemy go określonym kluczem, który jest łańcuchem znaków. Aby odczytać element z tablicy haszującej, należy ponownie podać ten klucz. Nie operujemy na indeksach liczbowych – od tego jest cały mechanizm haszowania, aby obliczać sobie gdzie trzyma dane. Wprowadza to oczywiście wygodę w obsługiwaniu takiej tablicy. O ile dla struktury 10-elementowej można zapamiętać co jest pod każdym indeksem, tak np. w grze cRPG, gdzie wartości, parametrów, atrybutów jest od groma i ciut ciut… Oczywiście, dzięki obiektowości można to jakoś porozrzucać po klasach. Jednakże często w wielu miejscach kodu musimy odwoływać się do tych samych zmiennych. Jako że osobiście uważam nadmierne “includowanie” plików nagłówkowych za dosyć męczące, warto mieć jedną sporą strukturę, gdzie mamy wszystkie wartości.

Z takim rozwiązaniem wiąże się również inna rzecz – ilość permutacji kluczy nie musi się równać wielkości tablicy. Nie sposób bowiem przewidzieć wszystkich możliwych łańcuchów. Z tego też powodu haszowanie umożliwia reprezentowanie większej struktury za pomocą mniejszej. Z tym (i nie tylko) wiąże się problem kolizji – ale do tego dojdziemy później.

Rysunek poglądowy – po lewej mamy klucze, którymi się posługujemy operując na danych, a po prawej tablicę haszującą:

Dobrze widać tutaj, dlaczego haszowanie jest nazywane rozpraszaniem – nie możemy się spodziewać, że pierwsza wartość wpisana do tablicy będzie pod pierwszym indeksem. W gruncie rzeczy nie jest to nam do niczego potrzebne – i tak się odwołujemy korzystając jedynie z kluczy. Tak czy inaczej, wypadałoby jednak zająć się algorytmów rozmieszczającym wartości w tablicy właśnie na podstawie klucza-identyfikatora. Czynimy to poprzez funkcję haszującą, którą umownie sobie oznaczymy h(k), gdzie k jest kluczem, a wartością zwracaną – numer indeksu. Właśnie ta funkcja jest pierwszym krytycznym punktem całego mechanizmu. Oczywiście, z tej racji nie poświęciłem jej zbyt wiele uwagi przy implementacji – zgodnie z prawem Murphy’ego (paragraf 1., ustęp 7.) im więcej czasu poświęcimy na dopracowanie elementu krytycznego algorytmu, tym błąd w programie będzie bardziej spektakularny.

Szukanie odpowiedniej funkcji haszującej to zajęcie, któremu oddawali się najwybitniejsi z najwybitniejszych. Cała zasada opiera się na nadaniu znakom wartości liczbowych – najczęściej w oparciu o tablicę ASCII. Założenie jest takie, że dobra funkcja h(k) musi rozkładać elementy w taki sposób, aby chociaż w przybliżeniu było spełnione założenie prostego równomiernego haszowania, czyli “rozkładanie” danych niezależnie od siebie nawzajem.

Praktykowanych jest parę różnych wariantów funkcji haszującej. Dla poniższych przykładów przyjmijmy, że K oznacza sumę wartości ASCII kolejnych znaków klucza (np. “kot” to 107 + 111 + 116 = 334), a N to wielkość tablicy haszującej. Oczywiście, zliczanie sumy łańcucha może się odbywać różnymi sposobami – parę pomysłów (wraz z implementacjami) zostało przedstawione na stronie [5] (w ogóle pod koniec notki umieszczę parę pozycji książkowych i internetowych, gdzie można szukać informacji znacznie dokładniejszych niż tutaj).

• Haszowanie modularne – chyba najprostsza możliwość. Dzielimy K przez N i bierzemy resztę z dzielenia. Zatem h(k) = K mod N.
• Haszowanie przez mnożenie – równie proste rozwiązanie, ale bardziej wyrafinowane (trudno o mniej wyrafinowane od haszowania modularnego – cóż, zawsze można wszystko układać po kolei, a potem przeszukiwać każdą przegródkę słowami “Przepraszam, czy jest tu jakiś portfel?”). Wykorzystujemy stałą A zawierającą się w przedziale (0, 1). Mnożymy K i A, bierzemy z tego część ułamkową i mnożymy razy N, zaokrąglając cały wynik w dół. Wynika zatem, iż h(k) = floor(N * (K * A mod 1)). Od Donalda Knutha dodatkowo mamy optymalne wartości stałej A – wynoszą one 0,6180339887 oraz 0,3819660113.
• Haszowanie uniwersalne – ta kategoria została wymyślona po to, aby zapobiec dosyć przykremu przypadkowi, który może mieć miejsce przy wyborze standardowych (ustalonych) funkcji haszujących – odwzorowanie wszystkich kluczy na jedną pozycję w tablicy, w wyniku czego czas wyszukiwania elementu wynosi O(m), gdzie m to ilość dotychczas wykorzystanych kluczy. Nieprawdopodobne, ale może się zdarzyć. Dlatego też, posiadając pewny skończony zbiór funkcji haszujących H, dokonowywane jest losowe wybranie funkcji h(k), którą potraktujemy nasz klucz. Przyznam, że nie wgłębiałem się w tą metodę, ale podaję ją po to, abyście mieli pełny obraz, że haszowanie ma wiele twarzy.

To są te najbardziej znane rodzaje funkcji haszujących. Oczywiście, nie jest powiedziane, że jedyne – na pewno wielu osobom przychodzą do głowy różne pomysły na ten algorytm (na przykład “weź K, podziel go przez N, zróżniczkuj, spierwiastkuj, scałkuj w granicach e i pi, a następnie wyznacz miejsca zerowe takiej funkcji i losowo wybierz jeden indeks, a potem płacz, że nie wiesz gdzie co jest”). Trzeba jednak przyznać, iż wyżej wymienione sprawdzają się bardzo dobrze i dla naszych zastosowań nie ma sensu wymyślać czegoś niezwykłego.

Przy haszowaniu uniwersalnym wspomniałem o możliwej niedogodności, iż jakimś cudem wszystkie klucze zostaną odwzorowane na ten sam indeks. W praktyce często się zdarza, że w tablicy haszującej w tej samej pozycji trzymana jest informacja o dwóch lub więcej wartościach – tego raczej nie unikniemy, warto zatem przyswoić sobie sposoby radzenia sobie z kolizjami. To drugi krytyczny punkt naszego algorytmu i moim zdaniem wymagający więcej zaangażowania (ale też nie ponad siły – patrz prawa Murphy’ego, paragraf 1., ustęp 7.).

• Metoda łańcuchowa (ang. chaining) – chyba najprostsze rozwiązanie, z którego zresztą skorzystałem (tak, właśnie dlatego, że jest najprostsze). Polega na stworzeniu listy jednokierunkowej na każdej pozycji w tablicy i w momencie, kiedy dwie wartości zostaną odwzorowane na ten sam indeks, umieszczane są na tej liście. Metoda nieskomplikowana, aczkolwiek wydaje mi się mało efektywna, co akurat nie szkodzi przy naszych potrzebach.
• Dwie strefy tablicy – jest to metoda polegająca na dzieleniu całej tablicy na dwie podtablice – właściwą i przepełnioną. Uzyskanie od funkcji haszującej dla danego klucza k1 indeksu w tablicy, który został już przydzielony kluczowi k2 powoduje, że wartość opisana kluczem k1 jest wpisywana na pierwszą wolną pozycję w strefie przepełnienia. Niezbyt jednak wiadomo, co zrobić, gdy przepełni się strefę przepełnienia. Prawdę mówiąc – nie zajmowałem się tym długo (ok. 2 minuty).
• Adresowanie otwarte – jest bardzo podobne do poprzedniej metody i też opiera się na zapisywaniu wszystkiego w jednej tablicy bez użycia jakichkolwiek list. W przypadku adresowania otwartego, jeżeli dany indeks już jest zajęty, wartość nowego klucza jest umieszczana w następnej (jednej z następnych) wolnej pozycji, która wynika z tzw. funkcji przyrostu p(i), której wartość jest dodawana do funkcji h(k). I tutaj mamy trzy możliwości (jako c, c1,… będę oznaczał jakiś współczynnik, który w szczególności wynosi 1 (lub 0)):

1. Adresowanie liniowe – p(i) = c * i, czyli po prostu następny wolny indeks. Występuje tutaj silna tendencja do grupowania się kluczy i tworzeniu sobie obozu w pobliżu zajętego indeksu. Pewnie chcą mu coś zrobić. Tak czy inaczej – może wystąpić sytuacja, że jedna część tablicy będzie wypełniona po brzegi, a druga zupełnie pusta.
2. Adresowanie kwadratowe – p(i) = c1 * i² + c2 * i, czyli funkcja kwadratowa. Znacznie redukuje problem grupowania kluczy, ale nie eliminuje go całkowicie.
3. Haszowanie dwukrotne – p(i) = i * h1(k) lub p(i) = i * h1(k) + h2(k), czyli dodanie do pierwotnego rezultatu h(k) wyniku funkcji h1(k) i ewentualnie h2(k). Zapewnia najmniejsze prawdopodobieństwo zgrupowania się wyrazów, ale może lekko utrudnić “dojście” dla właściwego klucza.

Więcej grzechów nie pamiętam. Przyznam uczciwie, że nie badałem dokładniej adresowania otwartego, które się wydaje rozsądną propozycją, kiedy uczynimy tablicę haszującą dość dużą – najlepiej przewidywane N pomnożyć jeszcze przez jakąś liczbę.

Jak widać, czeka nas troszkę problemów przy implementacji haszowania. Do tego wypada wiedzieć jedno – trzeba z góry wiedzieć ile mniej więcej elementów będziemy chcieli przechować, gdyż wypełnienie całej tablicy i jeszcze jej “nadpisywanie” w przypadku metody łańcuchowej całkowicie gubi sens stosowania transformacji kluczowej. Rzekomo, granicą, po przekroczeniu której haszowanie staje się bezużyteczne, jest tablica wypełniona w ok. 70%, zatem, jeżeli wiemy, że będziemy przechowywać około 70 elementów, warto zadeklarować tablicę 100-elementową.

Warto jednak znać takie struktury – może nam się kiedyś przydać przy tworzeniu gier, ale także w bazach danych, kryptografii. W dodatku, część języków posiada już wbudowane tablice haszujące (lub też asocjacyjne) – PHP, Ruby, Perl, Python i inne. No i warto się z tym zaznajomić wcześniej, jeżeli w przyszłości czeka nas przedmiot Algorytmy i Struktury Danych.

Zatem przejdziemy teraz do mięsa, czyli implemetancji. Z góry mówię, że (jak zwykle) pomysł nie jest mój – tutaj wielkie dzięki składam Wyszowi, Toxicowi i nie-pamiętam-komu oraz całemu zespołowi SystemSzok, który tworzył grę Shadow Clones (a teraz kreuje Wielkiego Mistrza).

Ogólne założenie jest takie – stosujemy haszowanie modularne, a w przypadku kolizji – metodę łańcuchową. W dodatku, ciekawe jest tutaj to, że w jednej tablicy możemy zapamiętać zarówno liczby całkowite jak i rzeczywiste (w wersji zespołu SystemSzok można było jeszcze przechowywać łańcuchy, ale z tego zrezygnowałem). A wszystko zostało oczywiście opakowane w klasę i przyjęte do frameworka jako “zatwierdzone”.

Ze względu na pewne problemy z pluginem Code Snipper, wszystkie kody źródłowe wyjątkowo podam w sposób standardowy. Wprawdzie będzie brzydko, ale siła wyższa - przynajmniej nic nie ucieknie (swoją drogą, miał już ktoś problemy z Code Snipperem?).

Na początku trzeba zdefiniować sobie dwie rzeczy – strukturę CHashNode, która będzie opisywała daną wartość w tablicy haszującej oraz typ wyliczeniowy, dzięki któremu będzie łatwiejsze określenie, jakiego typu jest wartość, którą przechowujemy na danej pozycji. Warto bowiem wspomnieć, iż chociaż pod jednym kluczem może się znajdować zarówno wartość typu int jak i typu float (i będą to różne wartości), to będą one przechowywane na osobnych elementach listy.

#include <>
#include <>

// typ wyliczeniowy rodzaju zmiennych do hashowania
enum HASH_TYPE
{
HT_INT, // wartość typu int
HT_FLOAT // wartość typu float
};

// struktura węzła w tablicy hashującej
struct CHashNode
{
int h_iValue; // wartość int
float h_fValue; // wartość float
std::string h_cKey; // nazwa klucza

HASH_TYPE h_htType; // typ danej
};

Wartości rozróżniamy według notacji, jaką sobie założyłem, czyli h_pierwsza-literka-typu-zmiennejValue. Dodatkowo, przechowujemy informację o tym typie oraz łańcuch klucza prowadzącego do danego węzła (aby można było porównać).

Przystępujemy zatem do deklaracji klasy CHash.

class CHash
{
private:

std::list* h_lHashTable; // wskaźnik na tablicę z danymi
unsigned h_uQuantity; // wielkość tablicy hashującej

void InitNode (CHashNode*); // inicjalizacja węzła
int Hash (char*); // funkcja hashująca

public:

CHash (unsigned); // konstruktor
~CHash(); // destruktor

void SetInt (char*, int); // wczytanie wartości typu int
void SetFloat (char*, float); // wczytanie wartości typu float

void ChangeInt (char*, int); // zmiana wartości typu int
void ChangeFloat (char*, float); // zmiana wartości typu float

int GetInt (char*); // pobranie wartości typu int
float GetFloat (char*); // pobranie wartości typu float

void RemoveInt (char*); // usunięcie wartości typu int powiązanej z danym kluczem
void RemoveFloat (char*); // usunięcie wartości typu float powiązanej z danym kluczem
};

Widać, że stosujemy metodę łańcuchową – każdy indeks tablicy będzie tak naprawdę głową listy, na której będą zapisywane kolejne elementy. Ta struktura oraz wielkość tablicy jest inicjalizowana w konstruktorze – zastosowałem tutaj znany i lubiany model RAII, który z uwielbieniem jest wykorzystywany w całym frameworku. Mamy dwie metody prywatne – InitNode (zerującą każdy nowo utworzony element tablicy haszującej) oraz Hash (czyli naszą funkcję haszującą). Lekki bałagan panuje w sekcji publicznej – mam na myśli to, że Code Snipper niezbyt poprawnie formatuje kod i z tego powodu możecie widzieć takie kwiatki, za co serdecznie przepraszam. Można jednak zauważyć cztery rodzaje operacji – Set (dodanie nowego elementu do tablicy wraz z odpowiadającym mu kluczem), Change (zmiana wartości elementu określonego danym kluczem), Get (pobranie wartości z tablicy za pomocą klucza) oraz Remove (usunięcie klucza z tablicy). Każda metoda zawiera dodatkowo sufiks Int lub Float, który naturalnie określa aktualną pogodę na wyspie Fidżi, choć prawdopodobnie jednak determinuje wykonanie operacji na wartości o żądanym typie.

Tyle implementacji pliku nagłówkowego. Należy zająć się zatem plikiem źródłowym. Na początek konstruktor oraz destruktor, czyli wykorzystanie wcześniej wspomnianego wzorca RAII.

#include "CHash.h"

CHash::CHash (unsigned n) // konstruktor
{
// pobranie wielkości tablicy haszującej
h_uQuantity = n;
h_lHashTable = new std::list[n];
}

CHash::~CHash() // destruktor
{
// zwolnienie pamięci po strukturze
delete[] h_lHashTable;
h_lHashTable = NULL;
}

Do konstruktora podajemy rozmiar tablicy haszującej, a w nim samym alokowana jest pamięć dla tablicy głów list, która zwalniana jest w destruktorze. Nie ma tutaj nic ciekawego, zatem przejdziemy do implementacji metody InitNode.

void CHash::InitNode (CHashNode* node) // inicjalizacja węzła
{
node->h_cKey = "";
node->h_fValue = 0.0f;
node->h_iValue = 0;
}

Jak widać, nie jest to też demon komp(l)ikacji. Przekazany węzeł ma zerowane wartości oraz klucz. Zmienne te potraktujemy odpowiednio w metodach SetInt oraz SetFloat. Natomiast teraz proponuję zająć się czymś ciekawszym – funkcja haszująca.

int CHash::Hash (char* key) // funkcja haszująca
{
// pobranie długości klucza oraz inicjalizacja zmiennej sumującej
int length = strlen(key);
unsigned s = 0;

// funkcja haszujca działa następująco:
// zsumuj kody ASCII wszystkich znaków oraz i, gdzie i to pozycja każdego znaku
// czyli np. klucz "kot", to dodawanie:
// 107 + 0 + 111 + 1 + 116 + 2 = 337
for (unsigned i = 0; i <>
{
s += static_cast<>(key[i]) + i;
}

// zwrócony indeks to ta suma modulo wielkość tablicy
return (s % h_uQuantity);
}

Pozwoliłem sobie na zostawienie całego kodu w niezmienionej postaci wraz z komentarzami. Nie postarałem się specjalnie – zastosowałem zwykłe haszowanie modularne, ale z małym mykiem – dodawanie wartości ASCII znaków łańcucha do siebie nie jest tak bezmyślne. Uwzględniana jest również pozycja danego znaku w łańcuchu. Ma to na celu zapobieganie sytuacji, gdy klucz “banan” ma dokładnie taką samą wartość jak “nanab” czy inna dowolna permutacja tego ciągu znaków. Nie jest to może nadto wyrafinowane, gdyż nadal stosunkowo łatwo uzyskać kolizję, ale lepszy rydz niż nic.

Uzbrojeni w potrzebne funkcje, napiszmy teraz pierwszą parę metod operacyjnych – SetInt oraz SetFloat.

void CHash::SetInt (char* key, int value) // wczytanie wartości typu int
{
// pobranie zahaszowanego indeksu
int index = Hash(key);

// utworzenie nowego węzła i wyczyszczenie go
CHashNode node;
InitNode(&node);

// zapisanie wartości, klucza i typu w nowym węźle
node.h_cKey.assign(key);
node.h_iValue = value;
node.h_htType = HT_INT;

// dopisanie węzła do listy
h_lHashTable[index].push_back(node);
}

void CHash::SetFloat (char* key, float value) // wczytanie wartości typu float
{
// pobranie zahaszowanego indeksu
int index = Hash(key);

// utworzenie nowego węzła i wyczyszczenie go
CHashNode node;
InitNode(&node);

// zapisanie wartości, klucza i typu w nowym węźle
node.h_cKey.assign(key);
node.h_fValue = value;
node.h_htType = HT_FLOAT;

// dopisanie węzła do listy
h_lHashTable[index].push_back(node);
}

Dla formalności będę podawał zawsze obie wersje – chociażby dlatego, że sam lubię mieć wszystko “na tacy”. Przy omawianiu jednak skupię się na ogólnym zarysie algorytmów ze względu na to, że obie wersje różnią się między sobą typem oraz zmienną, do której jest zapisywana wartość. Tak czy inaczej, najpierw pobierany jest indeks obliczony przez funkcję haszującą dla danego klucza, a także tworzony i zerowany nowy węzeł. Pewne komplikacje wynikły przy typie łańcuchów char* – w całym frameworku stosuje właśnie tą konwencję, natomiast tutaj wyjątkowo jest to konwertowane w locie na std::string, co akurat wielkim problemem nie jest – z punktu widzenia obsługi obiektu wszystko zostaje po staremu. Zapisywana jest wartość klucza, wartość value w odpowiedniej zmiennej oraz ustawiana jest flaga typu tej zmiennej. Po wykonaniu tych operacji, cały element jest dodawany do listy znajdującej się w odpowiednim indeksie, obliczonym wcześniej przez funkcję h(k).

Świetnie, umiemy zapisać wartość do tablicy haszującej. Czasami jednak trzeba ją zmienić. Dlatego teraz implementacja metod ChangeInt oraz ChangeFloat.

void CHash::ChangeInt (char* key, int value) // zmiana wartości typu int
{
// pobranie zahaszowanego indeksu
int index = Hash(key);

// jeśli dany indeks jest "pusty"
if (h_lHashTable[index].size() == 0)
{
return;
}

// poruszanie się po liście na danym indeksie, w celu
// znalezienia pozycji, na której znajduje się wartość
// o danym kluczu

std::list::iterator it;

for (it = h_lHashTable[index].begin(); it != h_lHashTable[index].end(); ++it)
{
// jeśli klucz się zgadza i przechowuje wartość typu int
if (it->h_cKey.compare(key) == 0 && it->h_htType == HT_INT)
{
// wartość zostaje zmieniona na nową
it->h_iValue = value;
break;
}
}
}

void CHash::ChangeFloat (char* key, float value) // zmiana wartości typu float
{
// pobranie zahaszowanego indeksu
int index = Hash(key);

// jeśli dany indeks jest "pusty"
if (h_lHashTable[index].size() == 0)
{
return;
}

// poruszanie się po liście na danym indeksie, w celu
// znalezienia pozycji, na której znajduje się wartość
// o danym kluczu

std::list::iterator it;

for (it = h_lHashTable[index].begin(); it != h_lHashTable[index].end(); ++it)
{
// jeśli klucz się zgadza i przechowuje wartość typu float
if (it->h_cKey.compare(key) == 0 && it->h_htType == HT_FLOAT)
{
// wartość zostaje zmieniona na nową
it->h_fValue = value;
break;
}
}
}

Początek operacji standardowy – obliczamy indeks w tablicy według klucza. Jeśli z jakiś względów podaliśmy zły klucz i w dodatku na danej pozycji lista jest pusta, wychodzimy od razu z metody, żeby nie zabierać czasu na bezsensowne operacje. Jeśli jednak istnieje uzasadnione prawdopodobieństwo, iż działamy zgodnie z planem, deklarujemy sobie iterator do wędrowania po liście, a następnie sprawdzamy ją całą. Jeśli w którymś miejscu dopasowanie podanego klucza do wcześniej zapisanego skończy się sukcesem, a w dodatku typ zmiennej się zgadza – wartość zostanie zmieniona na nową. Wtedy wychodzimy z pętli for i całej funkcji.

Na tym schemacie bazują praktycznie wszystkie następne funkcje. Korzystając z tego, jeszcze bardziej ułatwię sobie zadanie i będę opisywał wyłącznie operacje, które są z jakiegoś względu niezwykłe. Można tak powiedzieć o parze metod GetInt i GetFloat, które są kluczowe, gdyż pozwalają nam uzyskać dostęp do zapisanych wcześniej wartości.

int CHash::GetInt (char* key) // pobranie wartości typu int
{
// pobranie zahaszowanego indeksu
int index = Hash(key);

// jeśli dany indeks jest "pusty", zwracamy -1
if (h_lHashTable[index].size() == 0)
{
return 0;
}

// poruszanie się po liście na danym indeksie, w celu
// znalezienia pozycji, na której znajduje się wartość
// o danym kluczu

std::list::iterator it;
int ret = 0;

for (it = h_lHashTable[index].begin(); it != h_lHashTable[index].end(); ++it)
{
// jeśli klucz się zgadza i przechowuje wartość typu int - zwracamy wartość
if (it->h_cKey.compare(key) == 0 && it->h_htType == HT_INT)
{
// będziemy zwracać tą wartość
ret = it->h_iValue;
break;
}
}

// zwrócenie danej wartości
return ret;
} // int CHash::GetInt (char* key)

float CHash::GetFloat (char* key) // pobranie wartości typu float
{
// pobranie zahaszowanego indeksu
int index = Hash(key);

// jeśli dany indeks jest "pusty", zwracamy -1
if (h_lHashTable[index].size() == 0)
{
return 0.0f;
}

// poruszanie się po liście na danym indeksie, w celu
// znalezienia pozycji, na której znajduje się wartość
// o danym kluczu

std::list::iterator it;
float ret = 0.0f;

for (it = h_lHashTable[index].begin(); it != h_lHashTable[index].end(); ++it)
{
// jeśli klucz się zgadza i przechowuje wartość typu float - zwracamy wartość
if (it->h_cKey.compare(key) == 0 && it->h_htType == HT_FLOAT)
{
// będziemy zwracać tą wartość
ret = it->h_fValue;
break;
}
}

// zwrócenie danej wartości
return ret;
} // float CHash::GetFloat (char* key)

Domyślnie zwracaną wartością jest 0 i to zarówno gdy podamy zły klucz jak i zły typ. Sam algorytm przebiega praktycznie identycznie jak operacja Change – z tym wyjątkiem jednak, że tutaj zwracamy wartość, a nie zamieniamy jej.

Pozostała nam jeszcze jedna operacja – usuwanie atrybutu (w takim kontekście można to określić) z tablicy. Przyjrzyjmy się zatem metodom RemoveInt oraz RemoveFloat.

void CHash::RemoveInt (char* key) // usunięcie wartości typu int powiązanej z danym kluczem
{
// pobranie zahaszowanego indeksu
int index = Hash(key);

// jeśli dany indeks jest "pusty"
if (h_lHashTable[index].size() == 0)
{
return;
}

// poruszanie się po liście na danym indeksie, w celu
// znalezienia pozycji, na której znajduje się wartość
// o danym kluczu

std::list::iterator it;

for (it = h_lHashTable[index].begin(); it != h_lHashTable[index].end(); ++it)
{
// jeśli klucz się zgadza i przechowuje wartość typu float
if (it->h_cKey.compare(key) == 0 && it->h_htType == HT_INT)
{
// wartość zostanie usunięta
h_lHashTable[index].erase(it);
break;
}
}
} // void CHash::RemoveInt (char* key)

void CHash::RemoveFloat (char* key) // usunięcie wartości typu float powiązanej z danym kluczem
{
// pobranie zahaszowanego indeksu
int index = Hash(key);

// jeśli dany indeks jest "pusty"
if (h_lHashTable[index].size() == 0)
{
return;
}

// poruszanie się po liście na danym indeksie, w celu
// znalezienia pozycji, na której znajduje się wartość
// o danym kluczu

std::list::iterator it;

for (it = h_lHashTable[index].begin(); it != h_lHashTable[index].end(); ++it)
{
// jeśli klucz się zgadza i przechowuje wartość typu float
if (it->h_cKey.compare(key) == 0 && it->h_htType == HT_FLOAT)
{
// wartość zostanie usunięta
h_lHashTable[index].erase(it);
break;
}
}
} // void CHash::RemoveFloat (char* key)

Ponownie nic ciekawego się tutaj nie dzieje – stały schemat, który ulega modyfikacji dopiero po najechaniu iteratorem na element przeznaczony do usunięcia, który znajduje się na strukturze pod obliczonym indeksem w tablicy. Wykonywana jest tutaj zwykła operacje erase, która kasuje element znajdujący się na liście. I już.

Mam nadzieję, że przedstawiona poniżej implementacja haszowania nieco rozjaśnia całe zagadnienie. Zdaję sobie jednak sprawę, że być może zbyt pobieżnie przeanalizowałem kody źródłowe. Aby formalności stało się za dość, przedstawiam króciutki programik testujący nasz algorytm.

#include <>
#include "CHash.h"

int main()
{
CHash hash(10);

hash.SetFloat("kot", 3.04f);
hash.SetInt("koteczek", 34);

std::cout << hash.GetInt("zuo") << std::endl; // nie przypisaliśmy wartości do klucza "zuo"
std::cout << hash.GetInt("kot") << std::endl; // niepoprawne wywołanie, "kot" jest floatem
std::cout << hash.GetFloat("kot") << std::endl;
std::cout << hash.GetInt("koteczek") << std::endl;

hash.ChangeInt("koteczek", 26);
std::cout << hash.GetInt("koteczek") << std::endl;

hash.ChangeFloat("kot", -1.1f);
std::cout << hash.GetFloat("kot") << std::endl;

hash.RemoveFloat("kot");
std::cout << hash.GetFloat("kot") << std::endl;

hash.SetFloat("kot", -1.1f);
std::cout << hash.GetFloat("kot") << std::endl;

getchar();
return 0;
}

Skompilowanie i uruchomienie tego kodu powinno dać poniższy rezultat.

0
0
3.04
34
26
-1.1
0
-1.1

Widać, że nasze starania warte były zachodu – w przypadku podania nieodpowiedniego klucza uzyskujemy wartość domyślną zero, a w przy poprawnych wywołaniach – to, o co nam chodziło.

Warto tutaj wspomnieć, że domyślne zero to bardzo wygodna wartość. Przykładowo – odmierzamy czas jaki pozostał do wygaśnięcia jakiegoś czaru, przyjmijmy Spowolnienie. W tym celu, po jego rzuceniu wywołujemy funkcję nadającą wartość danemu atrybutowi.

hash.SetFloat("slow_time_to_live", 10.0f);

W każdej klatce zmniejszamy ten czas o pewną wartość delta_time.

int remaining_time = hash.GetFloat("slow_time_to_live");
hash.ChangeFloat("slow_time_to_live", remaining_time - delta_time);

A jeśli czas ten dojedzie (bądź minie) do zera – możemy usunąć atrybut.

hash.RemoveFloat("slow_time_to_live");

W ten sposób nie musimy pamiętać indeksu w tablicy (co cały czas podkreślam). Wystarczy wiedzieć, że dany stan bohatera czy potwora określony jest przez atrybut (klucz) “slow_time_to_live”.

Cóż, to wszystko co miałbym do przekazania odnośnie transformacji kluczowej. Mam nadzieję, iż udało mi się przekazać to zagadnienie w sposób przyjazny i zrozumiały. Jeśli gdzieś zauważyliście błędy, nieścisłości bądź chcecie mi wytknąć poważną pomyłkę merytoryczną żebym się zamknął w sobie i zaczął kręcić kółeczka – jestem do Waszej dyspozycji w komentarzach pod notką.

Na koniec podam jeszcze referencje, czyli małą bibliografię i linki, pod którymi można znaleźć ciekawe rzeczy odnośnie haszowania (z czego skrzętnie korzystałem podczas redagowania artykułu).

[1] Cormen T.H., Leiserson Ch.E., Rivest R.L., Stein C., Wprowadzenie do algorytmów, Wydawnictwo Naukowo-Techniczne, 2007, Seria Klasyka Informatyki
[2] Wróblewski P., Algorytmy - struktury danych i techniki programowania, Wydanie III, Wydawnictwo Helion, Gliwice, 2003
[3] http://en.wikipedia.org/wiki/Hash_table
[4] http://pl.wikipedia.org/wiki/Tablica_mieszaj%C4%85ca
[5] http://krzyjab.w.interia.pl/html/edu_haszowanie.html
[6] http://www.mif.pg.gda.pl/homepages/sylas/students/alg_podypl/w9.pdf
[7] http://math.univ.gda.pl/~blaszep/asd/wyklad/wyklad13_drukuj.pdf
[8] http://pl.wikipedia.org/wiki/Prawa_Murphy%27ego

Pozdrawiam i dziękuję – SceNtriC.