Haszowanie w strukturze danych: funkcja, techniki [z przykładami]

Wstęp

Haszowanie to ważna struktura danych zaprojektowana w celu rozwiązania problemu wydajnego wyszukiwania i przechowywania danych w tablicy. Na przykład, jeśli masz listę 20000 numerów i podałeś numer do przeszukania na tej liście - będziesz skanować każdy numer na liście, aż znajdziesz dopasowanie.

Przeszukanie całej listy i zlokalizowanie tego konkretnego numeru wymaga znacznej ilości czasu. Ten ręczny proces skanowania jest nie tylko czasochłonny, ale także nieefektywny. Dzięki haszowaniu w strukturze danych możesz zawęzić wyszukiwanie i znaleźć liczbę w ciągu kilku sekund.

Ten blog da ci głębsze zrozumienie metody haszowania, tabel haszowania i sondowania liniowego z przykładami.

Co to jest haszowanie w strukturze danych?

Haszowanie w strukturze danych to technika mapowania dużej porcji danych na małe tabele za pomocą funkcji mieszającej. Jest również znany jako funkcja skrótu wiadomości. Jest to technika, która jednoznacznie identyfikuje określony przedmiot ze zbioru podobnych przedmiotów.

Używa tablic mieszających do przechowywania danych w formacie tablicy. Każda wartość w tablicy ma przypisany unikalny numer indeksu. Tabele mieszające wykorzystują technikę generowania tych unikalnych numerów indeksów dla każdej wartości przechowywanej w formacie tablicy. Ta technika nazywa się techniką mieszania.

Musisz tylko znaleźć indeks żądanego elementu, a nie znaleźć dane. Dzięki indeksowaniu możesz szybko przeskanować całą listę i pobrać żądany element. Indeksowanie pomaga również w operacjach wstawiania, gdy trzeba wstawić dane w określonej lokalizacji. Bez względu na to, jak duża lub mała jest tabela, możesz aktualizować i pobierać dane w ciągu kilku sekund.

Haszowanie w strukturze danych to proces dwuetapowy.

1. Funkcja skrótu konwertuje element na małą liczbę całkowitą lub wartość skrótu. Ta liczba całkowita jest używana jako indeks do przechowywania oryginalnych danych.
2. Przechowuje dane w tablicy mieszającej. Możesz użyć klucza skrótu, aby szybko zlokalizować dane.

Przykłady haszowania w strukturze danych

Poniżej znajdują się rzeczywiste przykłady mieszania w strukturze danych –

• W szkołach nauczyciel przypisuje każdemu uczniowi unikalny numer listy. Później nauczyciel używa tego numeru rzutu, aby uzyskać informacje o tym uczniu.
• Biblioteka ma nieskończoną liczbę książek. Każdej księdze bibliotekarz nadaje unikalny numer. Ten unikalny numer pomaga w identyfikacji pozycji książek na półce.

Zamówienie: sortowanie w strukturze danych

Funkcja skrótu

Funkcja skrótu w strukturze danych mapuje dowolny rozmiar danych na dane o stałym rozmiarze. Zwraca następujące wartości: małą wartość całkowitą (znaną również jako wartość skrótu), kody skrótu i ​​sumy skrótu.

hash = hashfunc(klucz)

index = hash % array_size

Funkcja has musi spełniać następujące wymagania:

• Dobra funkcja mieszająca jest łatwa do obliczenia.
• Dobra funkcja skrótu nigdy nie blokuje się w klastrowaniu i rozprowadza klucze równomiernie w tabeli skrótów.
• Dobra funkcja skrótu pozwala uniknąć kolizji, gdy dwa elementy lub elementy zostaną przypisane do tej samej wartości skrótu.

Tabela haszowania

Haszowanie w strukturze danych wykorzystuje tabele haszujące do przechowywania par klucz-wartość. Tablica mieszająca używa następnie funkcji mieszającej do wygenerowania indeksu. Funkcja mieszania używa tego unikalnego indeksu do wykonywania operacji wstawiania, aktualizowania i wyszukiwania.

Jak działa haszowanie w strukturze danych?

W mieszaniu funkcja mieszająca mapuje ciągi lub liczby na małą wartość całkowitą. Tabele haszujące pobierają element z listy za pomocą funkcji haszującej. Celem techniki haszowania jest równomierne rozłożenie danych w całej macierzy. Haszowanie przypisuje wszystkim elementom unikalny klucz. Tablica mieszająca używa tego klucza, aby uzyskać dostęp do danych na liście.

Tablica mieszająca przechowuje dane w parze klucz-wartość. Klucz działa jako wejście do funkcji mieszającej. Funkcja mieszająca generuje następnie unikalny numer indeksu dla każdej przechowywanej wartości. Numer indeksu przechowuje wartość odpowiadającą temu kluczowi. Funkcja skrótu zwraca małą wartość całkowitą jako dane wyjściowe. Dane wyjściowe funkcji mieszającej nazywa się wartością skrótu.

Rozumiemy hashowanie w strukturze danych na przykładzie. Wyobraź sobie, że musisz przechowywać niektóre elementy (ułożone w parę klucz-wartość) w tabeli mieszającej z 30 komórkami.

Wartości są następujące: (3,21) (1,72) (40,36) (5,30) (11,44) (15,33) (18,12) (16,80) (38,99)

Tablica mieszająca będzie wyglądać następująco:

Przeczytaj także: Rodzaje struktur danych w Pythonie

Techniki rozwiązywania kolizji

Haszowanie w strukturze danych wchodzi w kolizję, jeśli dwa klucze mają przypisany ten sam numer indeksu w tablicy mieszającej. Kolizja stwarza problem, ponieważ każdy indeks w tablicy mieszającej powinien przechowywać tylko jedną wartość. Haszowanie w strukturze danych wykorzystuje kilka technik rozwiązywania kolizji do zarządzania wydajnością tablicy mieszającej.

Sondy liniowe

Mieszanie w strukturze danych powoduje, że indeks tablicy jest już zajęty do przechowywania wartości. W takim przypadku haszowanie wykonuje operację wyszukiwania i sonduje liniowo następną pustą komórkę.

Przykład sondowania liniowego

Wyobraź sobie, że zostałeś poproszony o przechowywanie niektórych elementów w tabeli mieszania o rozmiarze 30. Elementy są już posortowane według formatu pary klucz-wartość. Podane wartości to: (3,21) (1,72) (63,36) (5,30) (11,44) (15,33) (18,12) (16,80) (46,99) .

Hash(n) to indeks obliczany za pomocą funkcji mieszającej, a T to rozmiar tabeli. Jeśli indeks slotu = ( hash(n) % T) jest pełny, szukamy następnego indeksu slotu, dodając 1 ((hash(n) + 1) % T). Jeśli (hash(n) + 1) % T też jest pełny, wtedy próbujemy (hash(n) + 2) % T. Jeśli (hash(n) + 2) % T też jest pełny, wtedy próbujemy (hash( n) + 3) % T.

Tablica mieszająca będzie wyglądać następująco:

Podwójne haszowanie

Technika podwójnego haszowania wykorzystuje dwie funkcje haszujące. Druga funkcja skrótu jest używana, gdy pierwsza powoduje kolizję. Zapewnia indeks przesunięcia do przechowywania wartości.

Wzór na technikę podwójnego haszowania jest następujący:

(firstHash(key) + i * secondHash(key)) % sizeOfTable

Gdzie i jest wartością przesunięcia. Ta wartość przesunięcia jest zwiększana, dopóki nie znajdzie pustego gniazda.

Na przykład masz dwie funkcje skrótu: h1 i h2. Aby znaleźć wolne miejsce, musisz wykonać następujące czynności:

1. Sprawdź, czy hash1 (klucz) jest pusty. Jeśli tak, zapisz wartość w tym slocie.
2. Jeśli hash1(key) nie jest pusty, znajdź inne gniazdo za pomocą hash2(key).
3. Sprawdź, czy hash1(klucz) + hash2(klucz) jest pusty. Jeśli tak, zapisz wartość w tym slocie.
4. Kontynuuj zwiększanie licznika i powtarzaj z hash1(key)+2hash2(key), hash1(key)+3hash2(key) i tak dalej, aż znajdzie puste miejsce.

Przykład podwójnego haszowania

Wyobraź sobie, że musisz przechowywać niektóre elementy w tablicy mieszającej o rozmiarze 20. Podane wartości to: (16, 8, 63, 9, 27, 37, 48, 5, 69, 34, 1).

h1(n)=n%20

h2(n)=n%13

nh(n, i) = (h1 (n) + ih2(n)) mod 20

Wniosek

Podwójne mieszanie wiąże się z wysokimi kosztami obliczeniowymi, ale przeszukuje następny wolny slot szybciej niż metoda sondowania liniowego. Przykłady podane w artykule mają jedynie charakter wyjaśniający. Możesz modyfikować powyższe oświadczenia zgodnie z własnymi wymaganiami. Na tym blogu poznaliśmy pojęcie haszowania w strukturze danych .

Możesz wypróbować ten przykład, aby wzmocnić swoją wiedzę o strukturze danych. Jeśli chcesz dowiedzieć się więcej o strukturze danych , zapoznaj się z kursem UpGrad Executive PG Program in Full Stack Development . Ten kurs jest przeznaczony dla pracujących profesjonalistów i oferuje rygorystyczne szkolenia i pośrednictwo pracy w najlepszych firmach.