[C++] Hashowanie


(Kanaliaon) #1

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 


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

		}

    }

}
  1. 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
    
    	}
    
    }

    }

  2. 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
    
    	}
    
    }

    }

  3. 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*(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.