algorytm.org

Tablice z hashowaniem

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Tablice z hashowaniem
Ocena użytkowników:***** / 26
SłabyŚwietny 
Wpisany przez Michał Knasiecki, 16 sierpnia 2005 19:29

Tablice z hashowaniem są stosowane, gdy z pewnego dużego zbioru danych w danej chwili musimy znać stosunkowo jego niewielki podzbiór. Elementy z tego podzbioru są zapisywane w tablicy, której indeksy dla danego elementu oblicza specjalna funkcja hashująca. Takie rozwiązanie zmniejsza złożoność pamięciową algorytmy, np. wyobraźmy sobie, że ze zbioru 10.000 liczb całkowitych w danej chwili potrzebujemy jedynie 10. Po zastosowaniu tablicy z hashowaniem zmniejszamy wymaganą pamięć 1000-krotnie. Ponieważ adres danego elementu jest obliczany na podstawie jego wartości, funkcja hashująca jest bardzo szybka. Jednak z tego samego powodu może dojść do konfliktu. Może się bowiem zdarzyć tak, że funkcja wyznaczy kilku danym tą samą komórkę w pamięci. Jest to niedopuszczalne, należy więc w takim przypadku do komórki wyznaczonej przez funkcję doczepić statyczną tablicę o ilości elementów równej ilości przydzielonych komórce elementów. Ponieważ tablice są statyczne, algorytm nie traci na szybkości, a ponieważ każdy element ma osobne w niej miejsce nie dochodzi do konfliktu.

Jeśli funkcja hashująca wyznaczy wszystkim elementom tą samą komórkę, elementy te zostaną zapisane w jednej tablicy. W najgorszym przypadku więc tablica z hashowaniem 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). Jednym z najczęściej przytaczanych przykładów zastosowania tablicy z hashowaniem są kompilatory. Podczas analizowania programu muszą one zapamiętywać, czy dana zmienna już wystąpiła, a jeśli tak, to co znaczy.
Podstawą tablic z hashowaniem jest dobra funkcja hashująca. Miarą tej "dobroci" jest stopień, w jakim spełnia ona zasadę prostego równomiernego hashowania, tzn: losowo wybrany klucz jest z takim samym prawdopodobieństwem odwzorowywany na każdą z pozycji. Oznacza to poprosty, by klucze były w miarę równomiernie rozpraszane w tablicy.
Jedną z najprostszych funkcji hashujących jest funkcja modularna, która dla klucza k zwraca wartość reszty z dzielenia k przez m (m-długość tablicy), czyli h(k)=k modulo m.
Funkcja hashująca dla hasowania modularnego może wyglądać następująco:

#include <math.h>
...
int h(int x){
return fmod(x, m);
}


Aby funkcja modularna dawała zadowalające efekty należy dobrać odpowiednią wartość m: nie powinna być ona potęgą dwójki. Dlatego należy wybierać liczby pierwsze daleko położone od potęg dwójki, np. dobrą wartością jest m=701.

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 29 sierpnia 2012 20:51
Dodaj komentarz