algorytmy_i_struktury_danych:hash

## Czym jest hash, jakie ma zastosowania? Omów budowę i funkcjonowanie tablicy z hashowaniem z metodą łańcuchową.

wersja w formacie .doc

Funkcja haszująca to funkcja, która przyporządkowuje każdej liczbie wartość określaną jako hash (hasz) inaczej zwaną wartością skrótu funkcji lub po prostu skrótem. Jeżeli dwie liczby są różne, to ich hashe, z wysokim prawdopodobieństwem, też powinny być różne. Hash ma zwykle pewną z góry ustaloną długość (np. 128 bitów) i daje się bardzo łatwo obliczyć. Funkcja haszująca powinna uniemożliwiać łatwe obliczenie oryginalnej liczby na podstawie jej hasha.

Właściwości funkcji skrótu powodują, że zmiana choć jednego znaku w hashowanym tekście powinna powodować bardzo dużą zmianę jego skrótu. Jeżeli mamy hash jakiegoś tekstu, to odszukanie jego oryginalnej treści wymaga ogromnej mocy obliczeniowej i jest prawie niemożliwe.

Funkcje haszujące mają wiele zastosowań:

- buduje się za ich pomocą efektywne struktury danych,
- używa się ich do weryfikacji poprawności przesyłu danych,
- stosuje się je w kryptografii.

W kryptografii ważne jest, żeby mając wartość funkcji x nie można było zbudować wiadomości m, takiej że x = h(m).

Funkcje haszujące używane w kryptografii:

- historyczne: MD2, MD4, SHA
- współczesne: MD5, SHA-1, SHA2, RIPEMD-160

Tablica haszująca (zwana również tablicą mieszającą) to struktura danych służąca do przechowywania informacji, w taki sposób aby możliwy był do nich szybki dostęp. Odwołania do przechowywanych obiektów dokonywane są na podstawie klucza, który dany obiekt identyfikuje. Kluczem może być na przykład ciąg znaków zawierający nazwisko pracownika a wyszukiwaną informacją jego adres domowy. Położenie informacji w tablicy określa się obliczając wartość funkcji hashującej dla danego klucza.

W sytuacji gdy wartość funkcji mieszającej obliczonej dla klucza elementu wstawianego do tablicy pokrywa się z wartością klucza jakiegoś elementu już znajdującego się w tej tablicy mówimy o kolizji. Jednym ze sposobów rozwiązania problemu kolizji jest metoda łańcuchowa: Wszystkie elementy, którym odpowiada ta sama wartość w tablicy, zostają umieszczone na jednej liście. Tablica haszująca jest w tym przypadku tablicą wskaźników na listy tych elementów, które mają taką samą wartość funkcji haszującej. Zaletą metody łańcuchowej jest szybkość i prostota usuwania elementów z listy.

W najgorszym przypadku więc tablica z hashowaniem z metodą łańcuchową sprowadza się do zwykłej tablicy statycznej (stąd złożoność pesymistyczna przeszukiwania jest O(n)). Jeśli jednak funkcja hashująca wyznaczy każdemu elementowi inny adres złożoność przeszukiwania jest stała: O(1), (wynika to z faktu, że wartość szukanego elementu jest jednoznaczna z jego adresem w pamięci).

Podstawową wadą tablic hashujących jest duża złożoność pesymistyczna wyszukiwania, wynosząca O(n). Ponadto kosztowne może być także obliczanie wartości dobrej funkcji mieszającej. Kolejna wada wiąże się z architekturą współczesnych procesorów, które wykorzystują pamięć podręczną. Ponieważ pamięć podręczna przyspiesza odwołania do komórek pamięci operacyjnej gdy są one zgrupowane blisko siebie, zastosowanie tablicy mieszającej dla zbyt małej liczby elementów może być wolniejsze niż zastosownie zwykłej tablicy przeszukiwanej sekwencyjnie.

Więcej informacji pod adresami:

- http://pl.wikipedia.org/wiki/Funkcja_haszuj%C4%85ca
- http://pl.wikipedia.org/wiki/Tablica_mieszaj%C4%85ca
- http://www.algorytm.org/index.php?option=com_content&task=view&id=113&Itemid=54
- http://www.asdpb.republika.pl/wyk4sd.pdf