Funkcja skrótu
W tej sekcji omówimy funkcję skrótu, która pomaga wykonać kod skrótu powiązanego klucza elementu danych w strukturze danych, jak wspomniano poniżej:
Int hashItem ( wew klucz ){
powrót klucz % rozmiar tabeli ;
}
Proces wykonywania indeksu tablicy nazywa się haszowaniem. Czasami ten sam typ kodu jest wykonywany w celu wygenerowania tego samego indeksu przy użyciu tych samych kluczy zwanych kolizjami, które są obsługiwane poprzez różne tworzenie łańcuchów (tworzenie połączonych list) i wdrażanie strategii otwartego adresowania.
Działanie tablicy mieszającej w C++
Wskaźniki do wartości rzeczywistych są przechowywane w tablicy mieszającej. Używa klucza do wyszukiwania indeksu tablicy, w którym wartości odpowiadające kluczom muszą być przechowywane w żądanym miejscu w tablicy. Wzięliśmy tabelę skrótów o rozmiarze 10, jak wspomniano poniżej:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Weźmy losowo dowolne dane z różnych kluczy i przechowujmy te klucze w tabeli mieszającej, po prostu obliczając indeks. Zatem dane są przechowywane w odniesieniu do kluczy obliczonego indeksu za pomocą funkcji skrótu. Załóżmy, że bierzemy dane = {14,25,42,55,63,84} i klucze =[15,9,5,25,66,75].
Oblicz indeks tych danych za pomocą funkcji skrótu. Wartość indeksu jest wymieniona poniżej:
| Klucz | piętnaście | 9 | 29 | 43 | 66 | 71 |
|---|---|---|---|---|---|---|
| Oblicz indeks | 15%10 = 5 | 9%10=0 | 29%10=9 | 43%10=3 | 66%10=6 | 71%10=1 |
| Dane | 14 | 25 | 42 | 55 | 63 | 84 |
Po utworzeniu indeksu tablicy, umieść dane pod kluczem dokładnie o indeksie danej tablicy, jak opisano wcześniej.
| 25 | 84 | 55 | 14 | 63 | 42 | ||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Następnie widzimy, że do kolizji dochodzi, jeśli dwa lub więcej kluczy ma ten sam kod skrótu, co skutkuje tym samym indeksem elementów tablicy. Mamy jedno rozwiązanie, które pozwala uniknąć ryzyka kolizji: wybór dobrej metody mieszania i wdrożenie dokładnych strategii.
Omówmy teraz różne techniki wdrażania za pomocą odpowiednich przykładów.
Przykład: dodanie danych do tabeli mieszającej przy użyciu techniki otwartego mieszania
W tym przykładzie zastosujemy technikę implementacji, taką jak Open Hashing, aby uniknąć kolizji w tabeli mieszającej. W przypadku otwartego mieszania lub łączenia w łańcuchy tworzymy połączoną listę, aby połączyć wartości tabeli mieszającej. Fragment kodu tego przykładu znajduje się w załączniku poniżej, który opisuje technikę otwartego mieszania:
#include#uwzględnij
klasa Tabela Hash {
prywatny :
statyczny konst wew rozmiar tabeli = 10 ;
st :: lista < wew > stółMa [ rozmiar tabeli ] ;
wew funkcja hash ( wew klucz ) {
powrót klucz % rozmiar tabeli ;
}
publiczny :
próżnia wstawić ( wew klucz ) {
wew indeks = funkcja hash ( klucz ) ;
stółMa [ indeks ] . push_back ( klucz ) ;
}
próżnia zobaczTabelę ( ) {
Do ( wew I = 0 ; I < rozmiar tabeli ; ++ I ) {
st :: cout << „[” << I << „]” ;
Do ( automatyczny To = stółMa [ I ] . zaczynać ( ) ; To ! = stółMa [ I ] . koniec ( ) ; ++ To ) {
st :: cout << ' -> ' << * To ;
}
st :: cout << st :: koniec ;
}
}
} ;
wew główny ( ) {
HashTable maTable ;
maTabelę. wstawić ( piętnaście ) ;
maTabelę. wstawić ( 33 ) ;
maTabelę. wstawić ( 23 ) ;
maTabelę. wstawić ( 65 ) ;
maTabelę. wstawić ( 3 ) ;
maTabelę. zobaczTabelę ( ) ;
powrót 0 ;
}
To bardzo interesujący przykład: budujemy listę połączoną i wstawiamy dane do tablicy mieszającej. Przede wszystkim definiujemy biblioteki na początku programu. The < lista > biblioteka jest używana do implementacji listy połączonej. Następnie budujemy klasę o nazwie „HashTable” i tworzymy atrybuty klasy, które są prywatne jako rozmiar tabeli i tablica tabeli, używając słowa kluczowego „private:”. Pamiętaj, że atrybutów prywatnych nie można używać poza klasą. Tutaj przyjmujemy rozmiar tabeli jako „10”. Za pomocą tego inicjujemy metodę skrótu i obliczamy indeks tablicy skrótów. W funkcji skrótu przekazujemy klucz i rozmiar tablicy mieszającej.
Budujemy kilka wymaganych funkcji i udostępniamy je publicznie w klasie. Pamiętaj, że funkcji publicznych można używać poza klasą w dowolnym miejscu. Używamy słowa kluczowego „public:”, aby rozpocząć publiczną część zajęć . Ponieważ chcemy dodać nowe elementy do tablicy mieszającej, tworzymy funkcję o nazwie „InsertHash” z kluczem jako argumentem funkcji. W funkcji „wstaw” inicjujemy zmienną indeksującą. Przekazujemy funkcję skrótu do zmiennej indeksującej. Następnie przekaż zmienną indeksującą do połączonej listy tableHas[], używając metody „push”, aby wstawić element do tabeli.
Następnie budujemy funkcję „viewHashTab”, która wyświetla tabelę mieszającą i pozwala zobaczyć nowo wstawione dane. W tej funkcji wykonujemy pętlę „for”, która przeszukuje wartości aż do końca tablicy mieszającej. Upewnij się, że wartości są przechowywane w tym samym indeksie, który został opracowany przy użyciu funkcji skrótu. W pętli przekazujemy wartości w odpowiednich indeksach i w tym miejscu kończymy klasę. W funkcji „main” bierzemy obiekt klasy o nazwie „hasTable”. Za pomocą tego obiektu klasy możemy uzyskać dostęp do metody wstawiania, przekazując klucz w metodzie. Klucz, który przekazaliśmy w funkcji „main” jest obliczany w funkcji „insert”, która zwraca pozycję indeksu w tablicy mieszającej. Tablicę skrótów wyświetliliśmy wywołując funkcję „view” za pomocą obiektu „Class”.
Dane wyjściowe tego kodu są załączone w następujący sposób:
Jak widzimy, tabela mieszająca została pomyślnie utworzona przy użyciu połączonej listy w C++. Aby uniknąć kolizji tego samego indeksu, stosuje się łańcuchy otwarte.
Wniosek
Ostatecznie doszliśmy do wniosku, że tablica skrótów to najbardziej rozwijająca się technika przechowywania i uzyskiwania kluczy z parami wartości, umożliwiająca wydajną obsługę ogromnych ilości danych. Ryzyko kolizji w tabeli skrótów jest bardzo wysokie, co może spowodować zniszczenie danych i ich przechowywania. Możemy przezwyciężyć tę kolizję, stosując różne techniki zarządzania tablicą mieszającą. Opracowując tabelę skrótów w języku C++, programiści mogą zwiększyć wydajność, stosując najlepszą odpowiednią technikę przechowywania danych w tabeli skrótów. Mamy nadzieję, że ten artykuł będzie pomocny w zrozumieniu tabeli skrótów.