Wprowadzenie do funkcji mieszania w C
W tym artykule znajduje się krótka uwaga na temat mieszania (tabela skrótów i funkcja skrótu). Najważniejszym pojęciem jest „wyszukiwanie”, które determinuje złożoność czasu. Aby zmniejszyć złożoność czasu niż jakakolwiek inna koncepcja hashująca strukturę danych, wprowadza się czas O (1) w przypadku przeciętnym, a najgorszy przypadek zajmie czas O (n).
Hashowanie to technika z szybszym dostępem do elementów, która mapuje dane przy użyciu mniejszego klucza do porównań. Zasadniczo w tej technice klucze są śledzone za pomocą funkcji skrótu w tabeli zwanej tabelą skrótów.
Co to jest funkcja skrótu?
Funkcja skrótu jest funkcją, która używa operacji o stałym czasie do przechowywania i pobierania wartości z tablicy skrótów, która jest stosowana na kluczach jako liczby całkowite i jest używana jako adres wartości w tablicy skrótów.
Rodzaje funkcji skrótu
Rodzaje funkcji skrótu wyjaśniono poniżej:
1. Metoda podziału
W tej metodzie funkcja skrótu zależy od pozostałej części podziału.
Przykład: elementy do umieszczenia w tablicy mieszającej to 42 728 89, 64 i weźmy rozmiar tabeli jako 10.
Hash (klucz) = Element% wielkości tabeli;
2 = 42% 10;
8 = 78% 10;
9 = 89% 10;
4 = 64% 10;
Reprezentację tabeli można zobaczyć jak poniżej:
2. Metoda Mid Square
W tej metodzie środkowa część kwadratu jest traktowana jako indeks.
Element do umieszczenia w tablicy mieszającej to 210, 350, 99, 890, a wielkość tabeli to 100.
210 * 210 = 44100, indeks = 1, ponieważ środkowa część wyniku (44100) wynosi 1.
350 * 350 = 122500, indeks = 25, ponieważ środkowa część wyniku (122500) wynosi 25.
99 * 99 = 9801, indeks = 80, ponieważ środkowa część wyniku (9801) wynosi 80.
890 * 890 = 792100, indeks = 21, ponieważ środkowa część wyniku (792100) wynosi 21.
3. Metoda składania cyfr
W tej metodzie elementem, który ma zostać umieszczony w tabeli, jest śpiewanie klucza skrótu, który jest uzyskiwany przez podzielenie elementów na różne części, a następnie połączenie części poprzez wykonanie prostych operacji matematycznych.
Element do umieszczenia to 23576623, 34687734.
- skrót (klucz) = 235 + 766 + 23 = 1024
- klucz skrótu) = 34 + 68 + 77 + 34 = 213
W tego typu mieszaniu załóżmy, że mamy liczby od 1 do 100, a rozmiar tablicy mieszającej = 10. Elementy = 23, 12, 32
Hash (klucz) = 23% 10 = 3;
Hash (klucz) = 12% 10 = 2;
Hash (klucz) = 32% 10 = 2;
Z powyższego przykładu zauważ, że oba elementy 12 i 32 wskazują na drugie miejsce w tabeli, gdzie nie jest możliwe napisanie obu w tym samym miejscu, taki problem jest znany jako kolizja. Aby uniknąć tego rodzaju problemów, można zastosować pewne techniki funkcji skrótu.
Rodzaje technik rozwiązywania kolizji
Omówmy rodzaje technik rozwiązywania kolizji:
1. Łańcuch
W metodzie tej, jak sama nazwa wskazuje, zapewnia ona ciąg pól dla rekordu w tabeli zawierającej dwa wpisy elementów. Tak więc za każdym razem, gdy takie kolizje wystąpią, pola będą działać jak utworzona lista połączona.
Przykład: 23, 12, 32 z rozmiarem stołu 10.
Hash (klucz) = 23% 10 = 3;
Hash (klucz) = 12% 10 = 2;
Hash (klucz) = 32% 10 = 2;
2. Otwórz adresowanie
- Sondowanie liniowe
To kolejna metoda rozwiązywania problemów kolizji. Jak sama nazwa wskazuje, gdy dojdzie do kolizji, dwa elementy powinny zostać umieszczone na tym samym wpisie w tabeli, ale tą metodą możemy wyszukać następną pustą przestrzeń lub wpis w tabeli i umieścić drugi element. Może to ponownie prowadzić do kolejnego problemu; jeśli nie znajdziemy żadnego pustego wpisu w tabeli, prowadzi to do grupowania. Dlatego jest to znane jako problem klastrowania, który można rozwiązać za pomocą następującej metody.
Przykład: 23, 12, 32 z rozmiarem stołu 10
Hash (klucz) = 23% 10 = 3;
Hash (klucz) = 12% 10 = 2;
Hash (klucz) = 32% 10 = 2;
Na tym schemacie 12 i 32 mogą być umieszczone w tym samym wpisie o indeksie 2, ale dzięki tej metodzie są one umieszczone liniowo.
- Kwadratowe sondowanie
Ta metoda stanowi rozwiązanie problemu klastrowania podczas sondowania liniowego. W tej metodzie funkcja skrótu z kluczem skrótu jest obliczana jako skrót (klucz) = (skrót (klucz) + x * x)% wielkości tabeli (gdzie x = 0, 1, 2…).
Przykład: 23, 12, 32 z rozmiarem stołu 10
Hash (klucz) = 23% 10 = 3;
Hash (klucz) = 12% 10 = 2;
Hash (klucz) = 32% 10 = 2;
W tym widzimy, że 23 i 12 można łatwo umieścić, ale 32 nie może, ponieważ ponownie 12 i 32 mają ten sam wpis z tym samym indeksem w tabeli, zgodnie z tą metodą hash (klucz) = (32 + 1 * 1) % 10 = 3. Ale w tym przypadku pozycja tabeli z indeksem 3 jest umieszczona z 23, więc musimy zwiększyć wartość x o 1. Hash (klucz) = (32 + 2 * 2)% 10 = 6. Więc możemy teraz umieścić 32 w pozycji z indeksem 6 w tabeli.
- Podwójne haszowanie
W tej metodzie musimy obliczyć 2 funkcje skrótu, aby rozwiązać problem kolizji. Pierwszy jest obliczany przy użyciu prostej metody podziału. Drugi musi spełniać dwie zasady; nie może być równe 0, a wpisy muszą być sondowane.
- 1 (klucz) = klucz% wielkości tabeli.
- 2 (klawisz) = p - (klawisz mod p), gdzie p jest liczbami pierwszymi <rozmiar tabeli.
Przykład: 23, 12, 32 z rozmiarem stołu 10
Hash (klucz) = 23% 10 = 3;
Hash (klucz) = 12% 10 = 2;
Hash (klucz) = 32% 10 = 2;
W tym ponownie element 32 można umieścić za pomocą hash2 (klucz) = 5 - (32% 5) = 3. Więc 32 można umieścić pod indeksem 5 w tabeli, która jest pusta, ponieważ musimy przeskoczyć 3 wpisy, aby go umieścić.
Podsumowanie-funkcja mieszania w C
Hashowanie jest jedną z ważnych technik w zakresie wyszukiwania danych zapewnianych za pomocą bardzo wydajnych i szybkich metod przy użyciu funkcji skrótu i tabel skrótów. Każdy element można wyszukiwać i umieszczać przy użyciu różnych metod mieszania. Ta technika jest bardzo szybsza niż jakakolwiek inna struktura danych pod względem współczynnika czasu.
Polecane artykuły
To jest przewodnik po funkcji mieszania w C. Tutaj omawiamy wprowadzenie funkcji mieszania w C, co to jest funkcja skrótu, rodzaje funkcji skrótu itp. Możesz także przejrzeć nasze inne sugerowane artykuły, aby dowiedzieć się więcej -
- Hashowanie w DBMS
- Proces szyfrowania
- Jak zainstalować CakePHP?
- Jak działa Blockchain
- Funkcja mieszania w Javie
- Funkcja mieszania w PHP | Jak pracować?