HASH-OWANIE

CO trzeba umieć:

-- TABLICE

-- LISTY 

//////////////////////////////////////////////////////////////////

Hash-owanie to bardzo rozległy temat. Dlatego opowiem tylko krótko samą idę oraz zastosowania, ponieważ rozumienie tego tematu pozwoli łatwiej zrozumieć temat następny jakim jest reprezentacja grafu.

Hash-owanie, a dokładniej funkcje hash-ujące polegają na jednoznacznym odwzorowaniu, czyli przyporządkowujemy nasze dane w określony sposób w określone miejsce. Naszym miejscem będzie tablica lub lista. Dzięki odpowiedniemu przyporządkowaniu możemy łatwiej znaleźć nasz element lub wręcz przeciwnie utrudnić zrozumienie przesyłanej informacji. Sposobów i metod jak rozmieszczać elementy jest bardzo dużo, ale ja omówię ten, który później nam się przyda.

Np.:

Musimy rozmieścić liczby dwucyfrowe(x) w tablicy(t), która zawiera 10 miejsc, za pomocą funkcji hash-ującej.

Naszą funkcją hash-ującą będzie działanie: x mod 10. Takie działanie może dać 10 wyników czyli tyle co komórek w tablicy oraz zapewnia nam jednoznaczność (tzn. 15 mod 10 jest zawsze 5). 
 

indeks	0	1	2	3	4	5	6	7	8	9
0

Na razie nasza tablica jest pusta.

Dodajemy element 15. 15 mod 10 = 5, czyli dodajemy do komórki o indeksie 5 liczbę 15.

indeks	0	1	2	3	4	5	6	7	8	9
0						15

Następnie dodajemy liczbę 88. Postępujemy w taki sam sposób.
88 mod 10 = 8, dodajemy do komórki 8.

indeks	0	1	2	3	4	5	6	7	8	9
0						15			88

Teraz dodajemy liczbę 30. 30 mod 10 = 0.

indeks	0	1	2	3	4	5	6	7	8	9
0	30					15			88

Teraz dodajmy liczbę 75. 75 mod 10 = 5. I co teraz? Przecież już jest element w komórce o numerze 5. Tutaj technik rozwiązywania tego problemu jest kilka, ale nas interesował będzie jeden, ten którego będziemy używać przy grafach. Mianowicie musimy nasz element 75 dodać za element 15 w komórce 5.

indeks	0	1	2	3	4	5	6	7	8	9
0	30					15			88
1						75

W ten sposób będziemy umieszczać elementy. Jak widzimy do tego potrzebujemy tablicy dwuwymiarowej (tzw. macierzy). Ewentualnie tablicy tablicy (tego się będziemy trzymać). Wadą takiego rozwiązania jest to, że generuje bardzo dużo przestrzeni, ponieważ na ulokowanie 4 elementów potrzebowałem 20 „pól”. Natomiast zaletą jest to, że elementów się bardzo szybko szuka (oczywiście trzeba znać funkcję kodującą). Dzieje się tak, bo przeszukujemy tylko kilka „pól” w których może znajdować się nasza liczba, a nie wszystko.

Zamiast używać tablicy, która wbrew pozorom jest trudno do obsługi, gdyż jest problem z usuwaniem elementów. Możemy używać Listy, a będą już bardziej dokładnym listy list. Takie rozwiązanie może jest bardziej skomplikowanie, jeśli list dobrze nie rozumiesz, ale jest dożo lepsze. Ponieważ listy nie generują zbędnego miejsca (tzn. nie będę miał pustych komórek, bo listy rosną wraz z danymi). Poza tym w strukturze listy możemy zawrzeć wszystkie potrzebne nam informacje. Tak wiem, że może przeszukiwanie list nie jest takie milusie jak tablic, ale to tylko jedna wada list.

W sumie to o hash-owaniu to tyle, więcej będzie przy grafach, bo tam będziemy używali tego w praktyce, ale to nie jest trudne :).