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)
Kod: Zaznacz cały
// 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
}
}
}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
Kod: Zaznacz cały
//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
}
}
}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
Kod: Zaznacz cały
//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
}
}
}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))
Kod: Zaznacz cały
//Sondowanie kwadratowe z rownomiernym wypelnieniem tablicy hashujacej
#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
}
}
}