[c++] Hashowanie

[Leogict]

Witam!

Napisałem 4 programy na hashowanie (mieszanie):

1. Sondowanie liniowe

2. Podwójne hashowanie

3. Sondowanie kwadratowe

4. Sondowanie kwadratowe z równomiernym wypełnieniem tablicy.

 

Co myślicie o moich programach? Będę wdzięczny za wszelkie uwagi, spostrzeżenia, porady i wskazówki.

 

1. Sondowanie liniowe

Rozmiar tablicy: 103 (liczba pierwsza-lepszy rezultat)

// Sondowanie liniowe#include <iostream>using namespace std;void sondowanie(int tablica[], int klucz);int main(){  int tablica[103]={0},n,klucz;  cout << "Podaj n: ";  cin >> n;  for(int i=0; i<n; i++)	{	  cout << "Podaj element nr: " << i+1 << ": ";	  cin >> klucz;	  sondowanie(tablica, klucz); // umieszczamy klucz w wyhaszowanym indeksie tablicy	}  for(int j=0; j<103; j++) // po hashowaniu, wypisujemy tablice	{	  cout << tablica[j] << ", ";	}  return 0;}void sondowanie(int tablica[], int klucz){  int indeks,sukces=0;  indeks=klucz%103;  // wyliczenie indeksu  while(!sukces)  // dopoki nie sukces	{	  if(!tablica[indeks]) // jezeli nie ma kolizji, tzn tablica[indeks]=0		{			tablica[indeks]=klucz; // wpisanie do tablicy			sukces=1;  // wolne, dalej sie while nie wykona w tym wywolanie funkcji		}	  else // kolizja!		{			indeks++; // szukamy nastepnego wolnego miejsca			if(indeks>=103) indeks=0; // jak dojedzie do konca tablicy to zerujemy indeks		}	}}

2. Podwójne hashowanie

Rozmiar tablicy: 103, drugie hashowanie po liczbie 101:

Zastosowałem wzory:

h0=k mod N

H(k)=(k mod M)+1

hi=(h0+i*H(k)) mod N , i=1,2,...,N-1

gdzie:

h0 - indeks początkowy (bez kolizji), hi=i-ty indeks z kolizją, M - rozmiar tablicy (103), N - dzielnik drugiego hashowania (101), k - klucz

//Podwojne haszowanie#include <iostream>using namespace std;void podwojne_hashowanie(int tablica[], int klucz);int main(){  int tablica[103]={0},n,klucz;  cout << "Podaj n: ";  cin >> n;  for(int i=0; i<n; i++)	{	  cout << "Podaj element nr: " << i+1 << ": ";	  cin >> klucz;	  podwojne_hashowanie(tablica, klucz); // wywolanie podwojnego haszowania dla kazdego klucza	}  for(int j=0; j<103; j++) // wyswietlenie tablicy	{	  cout << tablica[j] << ", ";	}  cout << endl;  return 0;}void podwojne_hashowanie(int tablica[], int klucz){  int indeks,sukces=0,licznik_kolizji=0,indeks_bez_kolizji;  indeks=klucz%103;  // obliczenie indeksu  indeks_bez_kolizji=indeks; // zapamietanie pierwszego indeksu, potrzebny do wzoru na drugie haszowanie  while(!sukces) // dopoki nie znajdziemy wolnego miejsca w tablicy	{	  if(!tablica[indeks])  // jezeli nie ma kolizji		{		  tablica[indeks]=klucz;  // wpisanie klucza pod wyhaszowanym indeksem		  sukces=1; 		}	 else  // kolizja!		{		  licznik_kolizji++; 		  indeks=(indeks_bez_kolizji+licznik_kolizji*(klucz%101+1))%103; // haszujemy drugi raz		  if(indeks>=103) indeks=0;  // jak indeks przekracza rozmiary tablicy, to go zerujemy		}	}}

3. Sondowanie kwadratowe

Rozmiar tablicy: M=103

Zastosowałem następujący wzór na sondowanie kwadratowe:

hi=(h0+c*i+c*i^2) mod M , c=1/2

//Sondowanie kwadratowe#include <iostream>using namespace std;void sondowanie_kwadratowe(int tablica[], int klucz);int main(){  int tablica[103]={0},n,klucz;  cout << "Podaj n: ";  cin >> n;  for(int i=0; i<n; i++)	{	  cout << "Podaj element nr: " << i+1 << ": ";	  cin >> klucz;	  sondowanie_kwadratowe(tablica, klucz); // wywolanie sondowania kwadratowego dla kazdego klucza	}  for(int j=0; j<103; j++) // wyswietlenie tablicy	{	  cout << tablica[j] << ", ";	}  cout << endl;  return 0;}void sondowanie_kwadratowe(int tablica[], int klucz){  int indeks,sukces=0,licznik_kolizji=0,indeks_bez_kolizji;  indeks=klucz%103;  // obliczenie indeksu  indeks_bez_kolizji=indeks; // zapamietanie pierwszego indeksu, potrzebny do wzoru na sondowanie kwadratowe  while(!sukces) // dopoki nie znajdziemy wolnego miejsca w tablicy	{	  if(!tablica[indeks])  // jezeli nie ma kolizji		{		  tablica[indeks]=klucz;  // wpisanie klucza pod wyliczonym indeksem		  sukces=1; 		}	 else  // kolizja!		{		  licznik_kolizji++; 		  indeks=(int)(indeks_bez_kolizji+licznik_kolizji/2.+(licznik_kolizji*licznik_kolizji)/2.)%103; // sondowanie kwadratowe		  if(indeks>=103) indeks=0;  // jak indeks przekracza rozmiary tablicy, to go zerujemy		}	}}

4. Sondowanie kwadratowe z równomiernym wypełnieniem tablicy

Zastosowałem liczbę złotego podziału dla równomiernego wypełnienia tablicy hasciach!ącej. A=(sqrt(5)-1)/2

Zastosowałem wzór: hi=entier(M*(A*klucz mod 1))

//Sondowanie kwadratowe z rownomiernym wypelnieniem tablicy has[color= red;][ciach!][/color]acej#include <iostream>#include <math.h> // do pierwiastka (sqrt)using namespace std;void sondowanie_kwadratowe_rownomierne(int tablica[], int klucz);int main(){  int tablica[128]={0},n,klucz;  // ta metoda dziala najlepiej dla rozmiaru tablicy 2^p, p nalezy do N+  cout << "Podaj n: ";  cin >> n;  for(int i=0; i<n; i++)	{	  cout << "Podaj element nr: " << i+1 << ": ";	  cin >> klucz;	  sondowanie_kwadratowe_rownomierne(tablica, klucz); // wywolanie sondowania kwadratowego dla kazdego klucza	}  for(int j=0; j<128; j++) // wyswietlenie tablicy	{	  cout << tablica[j] << ", ";	}  cout << endl;  return 0;}void sondowanie_kwadratowe_rownomierne(int tablica[], int klucz){  int indeks,sukces=0,licznik_kolizji=0,indeks_bez_kolizji,B;  const double A=(sqrt(5.0)-1)/2;  // okolo 0,618 - dla tej wartosci uzyskujemy rownomierne rozmieszczenie kluczy w tablicy  B=(int)(A*klucz); // czesc calkowita  indeks=(int)(128*(A*klucz-B));  // obliczenie indeksu, wyrazenie w nawiasie - czesc ulamkowa, zamiast A*klucz%1  indeks_bez_kolizji=indeks; // zapamietanie pierwszego indeksu, potrzebny do wzoru na sondowanie kwadratowe  while(!sukces) // dopoki nie znajdziemy wolnego miejsca w tablicy	{	  if(!tablica[indeks])  // jezeli nie ma kolizji		{		  tablica[indeks]=klucz;  // wpisanie klucza pod wyhaszowanym indeksem		  sukces=1; 		}	 else  // kolizja!		{		  licznik_kolizji++; // nastepny (sondowanie liniowe)		  indeks=(int)(indeks_bez_kolizji+licznik_kolizji/2.+(licznik_kolizji*licznik_kolizji)/2.)%128; // sondowanie kwadratowe		  if(indeks>=128) indeks=0;  // jak indeks przekracza rozmiary tablicy, to go zerujemy		}	}}

Pozdrawiam.