Witam!
Napisałem 4 programy na hashowanie (mieszanie):
-
Sondowanie liniowe
-
Podwójne hashowanie
-
Sondowanie kwadratowe
-
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.
- Sondowanie liniowe
Rozmiar tablicy: 103 (liczba pierwsza-lepszy rezultat)
// Sondowanie liniowe
#include
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
{
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
}
}
}
-
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
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
{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 } }}
-
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
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
{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 } }}
-
Sondowanie kwadratowe z równomiernym wypełnieniem tablicy Zastosowałem liczbę złotego podziału dla równomiernego wypełnienia tablicy hashującej. A=(sqrt(5)-1)/2 Zastosowałem wzór: hi=entier(M*(A*klucz mod 1))
//Sondowanie kwadratowe z rownomiernym wypelnieniem tablicy hashujacej
#include
#include // 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
{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*(Aklucz-B)); // obliczenie indeksu, wyrazenie w nawiasie - czesc ulamkowa, zamiast Aklucz%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.