• U - Uniwersum kluczy. Zbiór wszystkich możliwych kluczy U = {0,1,…,m-1}.
• K - Zbiór kluczy elementów aktualnie znajdujących się w zbiorze.
• T - Zbiór będący tablicą haszującą.
• h(k) - funkcja haszująca oblicza pozycję w tablicy T elementu o kluczu k.
• floor(a) - funkcja zwracająca część całkowitą liczby a.

• haszowanie bezpośrednie
• haszowanie modularne
• haszowanie przez mnożenie
• haszowanie uniwersalne
• haszowanie doskonałe

Haszowanie jest wykonywane przy pomocy funkcji haszującej. Dobra funkcja haszująca powinna spełniać założenia prostego równomiernego haszownia: losowo wybrany klucz jest z jednakowym prawdopodobieństwem odwzorowywany na każdą z m pozycji niezależenie od tego, gdzie zostają odwzrowane inne klucze.
Niestety rzadko jest znany rozkład prawdopodobieństwa pojawiania się kluczy. Dla przykładu niech kluczę będą losowymi liczbami rzeczywistymi rozłożonymi równomiernie i niezależnie w przedziale 0 ⇐ k < 1. W tym przypadku można pokazać że funkcja haszująca: h(k) = floor(km) spełnia warunki dobrej funkcji haszującej.

Jest to takie haszowanie w którym element o kluczu k znajduje się na pozycji k-tej: h(k) = k. Głównym założeniem tej metody haszowania jest to że żadne dwie różne wartości nie mają tego samego klucza. Główną wadą tego haszowanie jest to że jeżeli |U| jest zbyt duże to przechowywanie całej tablicy w pamięci komputera może być nie realne. Co więcej jeżeli |K| będzie zbyt małe w porównaniu z |U| to większość pamięci zarezerwowanej dla T może się niepotrzebnie marnować.

Funkcja haszująca stosowana w haszowaniu modularnym na kluczu k daje wartość będącą resztą z dzielenia k przez m, gdzie m jest liczbą pozycji w tablicy:

h(k) = k modulo m

W tej metodzie ważne jest aby dobrać odpowiednio wartość m. Tzn. należy unikać wartości m będących potęgą 2, ponieważ jeżeli m = 2^p to h(k) jest liczbą stanowiącą p najmniej znaczących bitów liczy k. Należy używać funkcji zależącej od wszystkich bitów wartości k. Dobrymi wartościami m są liczby pierwsze niezbyt bliskie potęgom 2.
Dla przykładu: jeżeli w tablicy zamierzamy przechowywać około 2000 wartości przy czym dopuszczamy średnią długość listy równą 3 wtedy należy stworzyć tablicę T o wielkości 701 ponieważ 701 jest liczbą pierwszą leżącą blisko wartości 2000/3 oraz daleko od potęg 2. Wtedy h(k) = k modulo 701

Haszowanie przez mnożenie przebiega w dwóch krokach:

• Mnożymy wartość przez stałą A taką że 0 < A < 1 i wyznaczamy część ułamkową iloczynu kA.
• Otrzymaną wartość mnożymy przez m.

Postać funkcji haszującej można zapisać w następujący sposób: h(k) = floor(m(kA modulo 1))
gdzie „kA modulo 1” oznacza część ułamkową tj. kA - floor(kA)

Haszowanie uniwersalne rozwiązuje problem „złośliwych” danych, tzn. takich, które przy stałej funkcji haszującej są odwzorowywane na tę samą pozycję w tablicy. Funkcja haszująca w metodzie uniwersalnej jest dobierana losowo z rodziny funkcji, o szczególnych właściwościach. Wszystkie funkcje z rodziny funkcji haszujących są niezależne od wstawianych do tablicy kluczy.
Niech H będzie rodziną funkcji haszujących które odwzorowywują uniwersum kluczy U w zbiór {0,1,…,m-1}.

Jest to prosta procedura:

• Wybieramy dużą liczbę pierwszą p tak aby każdy klucz k wpadał do przedziału [0…p-1].
• Z_p jest zbiorem {0,1,…,p-1}.
• Z*_p jest zbiorem {1,…,p-1}.
• Wiemy że p > m - z założenia że uniwersum kluczy jest większe od liczby miejsc w tablicy.
• a ∈ Z*_p oraz b ∈ Z_p.

Mając wszystkie parametry możemy wyznaczyć rodzinę funkcji:
H_p,m = {h_a,b: a ∈ Z*_p i b ∈ Z_p}
gdzie:
h_a,b(k) = ( (ak + b) modulo p) modulo m

Dla przykładu dla p=17 i m=6 mamy h_3,4(8) = 5

Nie rozwodziłbym się nad tym typem haszowania, a tylko wspomniał, opisał co to jest. Lub jeżeli ktoś prowadzi taką politykę tylko odpytał na czym ono polega. O haszowaniu mówimy że jest doskonałe jeżeli w przypadku pesymistycznym wyszukiwanie wymaga stałej liczby odwołań do tablicy. Chociaż haszowanie znajduje szerokie zastosowanie ze względu na swoje znakomite zachowanie już w przypadku średnim, to okazuje się że również w przypadku pesymistycznym można osiągnąć podobną jakość. Zbiór kluczy jest zbiorem statycznym tzn. po umieszczeniu kluczy w tablicy, jej zawartość nigdy nie ulega zmianie. Takie przypadki czasami pojawiają się naturalnie np. w przypadku zbioru nazw plików na CD-ROM-ie.
Podstawowy pomysł haszowania doskonałego polega na wprowadzeniu dwupoziomowego haszownia:

Pierwszy poziom to zwykłe haszowanie uniwersalne z łańcuchową metodą rozwiązywania konfliktów. n kluczy rozmieszczamy w m miejscach za pomocą funkcji haszującej. Zamiast jednak tworzenia listy kluczy odwzorowywanych na pozycję j tworzymy dodatkową tablicę z haszowaniem S_j wraz ze związaną z nią funkcją haszującą h_j. Można tak dobrać funkcję h_j aby zagwarantować że na drugim poziomie nie będzie kolizji!. Aby zagwarantować brak kolizji na drugim poziomie musimy pozwolić aby rozmiar m_j tablicy S_j był kwadratem liczby n_j czyli kluczy odwzorowywanych na pozycję j. Wtedy można udowodnić że prawdopodobieństwo wystąpienia kolizji jest mniejsze od 1/2.

Konflikty pojawiają się w momencie kiedy dla dwóch różnych kluczy funkcja haszująca wyznacza tę samą pozycję.

W metodzie łańcuchowej wszystkie elementy którym odpowiada ta sama pozycja w tablicy, zostają umieszczone na jednej liście. Na pozycji j w tablicy jest pamiętany wskaźnik do początku listy tych wszystkich elementów, dla których funkcja h daje wartość j. Jeżeli w zbiorze nie ma takich elementów to pozycja j ma wartość NIL.
W przypadku pesymistycznym zakłada się że wszystkie klucze są odwzorowywane na tę samą pozycję w tablicy. W takim przypadku wyszukiwanie staje się bardzo nieefektywne gdyż jego złożoność wynosi O(n).
Współczynnik zapełnienia α dla danej tablicy T o m pozycjach w której znajduje się n elementów określa się jako n/m czyli średnią liczbę elementów w łańcuchu.
Oczekiwany czas wyszukiwania zakończonego porażką wynosi O(α).

Adresowanie otwarte jest kolejną metodą rozwiązywania konfliktów. W tej metodzie wszystkie elementy są przechowywane wprost w tablicy (konsekwencją jest to że α nie może być większa od 1 - przepełnienie tablicy).
Wyszukanie elementu polega na kolejnym sprawdzaniu pozycji w tablicy T wyznaczanych za pomocą ciągu do momentu aż dany element zostanie znaleziony, lub do momentu aż będzie wiadomo że danego elementu na pewno nie ma w tablicy. Wyróżniamy różne metody generowania ciągu:

• liniowa
• kwadratowa
• dwukrotna

Wstawienie wartości do tablicy polega na znalezieniu w niej wolnego miejsca. Kolejność w jakiej będziemy analizować elementy tablicy powinna zależeć od wstawianego klucza. W tym celu należy zmienić definicję funkcji haszującej tak aby przyjmowała dwa argumenty:

• klucz,
• numer wyrazu ciągu począwszy od zera.

Pozycja w tablicy T jest zatem wyznaczana na podstawie klucza oraz wyrazu ciągu kontrolnego. Kolejne elementy tablicy T wyznaczone przy pomocy funkcji haszującej są następujące:
<h(k,0),h(k,1),…,h(k,m-1)> Powyższy ciąg jest oczywiście jedną z permutacji elementów zbioru {0,1,…,m-1}
Przykładowa funkcja wstawiania może wyglądać następująco:

func INSERT(T,k)
   i := 0
   while i < m
      j := h(k,i)
      if T[j] = NIL
         return j
      else
         i := i + 1
      end if
   end while
   wyrzuć wyjątek o przepełnieniu tablicy z haszowaniem
end func

Algorytm wyszukiwania klucza k przegląda ten sam ciąg pozycji, które odwiedził algorytm wstawiania. Dlatego wyszukiwanie można przerwać jeżeli znajdziemy dany klucz lub gdy napotkamy pustą pozycję gdyż klucz z pewnością nie będzie wstawiony dalej.
Przykładowa funkcja wyszukiwania może wyglądać następująco:

func SEARCH(T,k)
   i := 0
   j := h(k,i)
   while T[j] != NIL and i < m
      if T[j] = k
         return j
      end if
      i := i + 1
      j := h(k,i)
   end while
   return NIL
end func

Usuwanie elementów z tablic z haszowaniem przez adresowanie otwarte jest trudne. Jeżeli usuwany element wyznaczony za pomocą i-tej wartości ciągu kontrolnego to nie możemy tej pozycji po prostu oznaczyć jako wolnej gdyż w przeciwnym wypadku dostęp do kluczy wyznaczonych za pomocą dlaszych wyrazów ciągu zostanie zablokowany. Problem ten można rozwiązać przy pomocy stałej np. DELETED która będzie umieszczana w miejsce usuniętej wartości natomiast którą funkcja insert będzie traktowała tak samo jak NIL. Powodem jest to że funkcja insert powinna kontynuować przeszukiwanie ponieważ na pozycjach wyznaczonych przy pomocy kolejnych wyrazów ciągu kontrolnego mogą znajdować się dalsze elementy.
Powyżej wymienione metody generowania ciągów kontrolnych gwarantują że <h(k,0),h(k,1),…,h(k,m-1)> jest permutacją liczb {0,1,…,m-1} dla każdego klucza k.

Adresowanie liniowe jest najprostszą metodą tworzenia ciągu kontrolnego. Funkcja haszująca ma postać: h(k,i) = (h'(k)+i) modulo m.
Gdzie:
h':U → {0,1,…,m}
h' jest zwane pomocniczą funkcją haszującą.
Z powyższego wzoru wynika że pierwszy wyraz ciągu (a więc jednocześnie pierwsza pozycja w tablicy T) ma wartość h'(k) natomiast kolejną jest h'(k)+1 itd.
Adresowanie liniowe ma jedną poważną wadę polegającą na istnieniu tendencji grupowania zajętych pozycji (grupowanie pierwotne). Długie spójne ciągi zajętych pozycji powodują że średni czas wyszukiwania rośnie.

W adresowaniu kwadratowym stosuje się funkcje haszujące postaci: h(k,i) = (h'(k)+c₁i+c₂i²) modulo m
gdzie h'(k) jest podobnie jak w adresowaniu liniowym pomocniczą funkcją haszującą.
Pierwszym wyrazem ciągu kontrolnego wyznaczanego poprzez adresowanie kwadratowe jest h'(k) a kolejne zależą od kwadratu numeru pozycji i w ciągu kontrolnym. Ta metoda jest lepsza od adresowania liniowego ponieważ w dużym stopniu eliminuje niebezpieczeństwa grupowania pierwotnego.

Jest to najlepsza metoda adresowanie otwartego generowania ciągów kontrolnych. W haszowaniu dwukrotnym funkcja haszująca ma postać: h(k,i) = (h₁(k) + ih₂(k)) modulo m
Gdzie:
h₁ i h₂ są pomocniczymi funkcjami haszującymi.
W odróżnieniu od wcześniej opisanych metod w tej metodzie wyrazy ciągu kontrolnego w dwojaki sposób zależą od wartości klucza. Aby mieć pewność że w razie potrzeby przeszukana zostanie cała tablica musimy zapewnić że wartość h₂(k) jest względnie pierwsza z rozmiarem tablicy. Warunek ten można łatwo spełnić np.:

• dobierając pewna potęgę jako wartość m oraz zapewniając że h₂(k) daje tylko wartości nieparzyste.
• jako wartość m dobrać pewną liczbę pierwszą a następnie zagwarantować że wartościami h₂(k) są tylko liczby dodatnie mniejsze od m
  np.:
  dla liczby pierwszej m można przyjąć:
  h₁(k) = k modulo m
  h₂(k) = 1 + (k modulo m')
  gdzie m' jest nieco mniejsze od m np. (m-1).
  Jeśli np. k=123456 m=701 i m'=700 to
  h₁(k) = 80 oraz h₂(k) = 257.