Hash Table w strukturze danych: przykład w Pythonie

Spisie treści:

Anonim

Co to jest haszowanie?

Hash to wartość o ustalonej długości, generowana za pomocą wzoru matematycznego. Wartości skrótu są używane w kompresji danych, kryptologii itp. Podczas indeksowania danych używane są wartości skrótu, ponieważ mają one stałą długość, niezależnie od wartości użytych do ich wygenerowania. Sprawia, że ​​wartości skrótu zajmują minimalną przestrzeń w porównaniu z innymi wartościami o różnych długościach.

Funkcja skrótu wykorzystuje algorytm matematyczny do konwersji klucza na skrót. Kolizja występuje, gdy funkcja skrótu generuje tę samą wartość skrótu dla więcej niż jednego klucza.

W tym samouczku dotyczącym algorytmu dowiesz się:

  • Co to jest haszowanie?
  • Co to jest tabela skrótów?
  • Funkcje skrótu
  • Cechy dobrej funkcji skrótu
  • Kolizja
  • Operacje na tablicy skrótów
  • Przykład Hash Table w Pythonie
  • Objaśnienie kodu tablicy skrótów
  • Przykład słownika Pythona
  • Analiza złożoności
  • Aplikacje w świecie rzeczywistym
  • Zalety tablic mieszających
  • Wady tabel skrótów

Co to jest tabela skrótów?

Tablica mieszająca jest strukturą danych, która przechowuje wartości za pomocą pary kluczy i wartości. Każdej wartości jest przypisany unikalny klucz, który jest generowany za pomocą funkcji skrótu.

Nazwa klucza służy do uzyskiwania dostępu do skojarzonej z nim wartości. To sprawia, że ​​wyszukiwanie wartości w tablicy skrótów jest bardzo szybkie, niezależnie od liczby elementów w tablicy.

Funkcje skrótu

Na przykład, jeśli chcemy przechowywać akta pracowników, a każdy pracownik jest jednoznacznie identyfikowany za pomocą numeru pracownika.

Możemy użyć numeru pracownika jako klucza i przypisać dane pracownika jako wartość.

Powyższe podejście będzie wymagało dodatkowego wolnego miejsca rzędu (m * n 2 ), gdzie zmienna m to rozmiar tablicy, a zmienna n to liczba cyfr numeru pracownika. Takie podejście wprowadza problem z przestrzenią dyskową.

Funkcja skrótu rozwiązuje powyższy problem, pobierając numer pracownika i używając go do wygenerowania wartości całkowitej skrótu, stałych cyfr i optymalizacji przestrzeni dyskowej. Celem funkcji skrótu jest utworzenie klucza, który będzie używany do odwoływania się do wartości, którą chcemy przechowywać. Funkcja akceptuje wartość do zapisania, a następnie używa algorytmu do obliczenia wartości klucza.

Poniżej znajduje się przykład prostej funkcji skrótu

h(k) = k1 % m

TUTAJ,

  • h (k) to funkcja skrótu, która przyjmuje parametr k. Parametr k to wartość, dla której chcemy obliczyć klucz.
  • k 1 % m to algorytm naszej funkcji skrótu, gdzie k1 to wartość, którą chcemy przechowywać, a m to rozmiar listy. Używamy operatora modułu do obliczenia klucza.

Przykład

Załóżmy, że mamy listę o stałym rozmiarze 3 i następujących wartościach

[1, 2, 3]

Możemy użyć powyższego wzoru, aby obliczyć pozycje, które powinna zajmować każda wartość.

Poniższy obraz przedstawia dostępne indeksy w naszej tabeli skrótów.

Krok 1)

Oblicz pozycję, która będzie zajmowana przez pierwszą wartość w ten sposób

h (1) = 1% 3

= 1

Wartość 1 zajmie miejsce pod indeksem 1

Krok 2)

Oblicz pozycję, która będzie zajmowana przez drugą wartość

h (2) = 2% 3

= 2

Wartość 2 zajmie miejsce na indeksie 2

Krok 3)

Oblicz pozycję, która będzie zajmowana przez trzecią wartość.

h (3) = 3% 3

= 0

Wartość 3 zajmie miejsce pod indeksem 0

Ostateczny wynik

Nasza wypełniona tabela skrótów będzie teraz wyglądać następująco.

Cechy dobrej funkcji skrótu

Dobra funkcja skrótu powinna mieć następujące cechy.

  • Formuła do generowania skrótu powinna wykorzystywać wartość danych, które mają być przechowywane w algorytmie.
  • Funkcja skrótu powinna generować unikalne wartości skrótu nawet dla danych wejściowych o tej samej ilości.
  • Funkcja powinna minimalizować liczbę kolizji. Kolizje występują, gdy ta sama wartość jest generowana dla więcej niż jednej wartości.
  • Wartości muszą być rozłożone konsekwentnie na wszystkie możliwe skróty.

Kolizja

Kolizja występuje, gdy algorytm generuje ten sam skrót dla więcej niż jednej wartości.

Spójrzmy na przykład.

Załóżmy, że mamy następującą listę wartości

[3,2,9,11,7]

Załóżmy, że rozmiar tablicy haszującej wynosi 7 i użyjemy wzoru (k 1 % m), gdzie m jest rozmiarem tablicy haszującej.

W poniższej tabeli przedstawiono wartości skrótu, które zostaną wygenerowane.

Klucz Algorytm skrótu (k 1 % m) Wartość skrótu
3 3% 7 3
2 3% 7 2
9 3% 7 2
11 3% 7 4
7 3% 7 0

Jak widać z powyższych wyników, wartości 2 i 9 mają tę samą wartość skrótu i ​​nie możemy przechowywać więcej niż jednej wartości na każdej pozycji.

Podany problem można rozwiązać za pomocą łańcuchów lub sondowania. W poniższych sekcjach szczegółowo omówiono tworzenie łańcuchów i sondowanie.

Łańcuch

Łańcuch to technika używana do rozwiązywania problemu kolizji za pomocą połączonych list, z których każda ma unikalne indeksy.

Poniższy obraz ilustruje, jak wygląda połączona lista

Zarówno 2, jak i 9 zajmują ten sam indeks, ale są przechowywane jako połączone listy. Każda lista ma unikalny identyfikator.

Korzyści z połączonych list

Oto zalety list łańcuchowych:

  • Listy łańcuchowe mają lepszą wydajność podczas wstawiania danych, ponieważ kolejność wstawiania to O (1).
  • Nie ma potrzeby zmiany rozmiaru tabeli skrótów, która używa listy łańcuchowej.
  • Może z łatwością pomieścić dużą liczbę wartości, o ile jest dostępne wolne miejsce.

Sondowanie

Inną techniką używaną do rozwiązywania kolizji jest sondowanie. Korzystając z metody sondowania, jeśli dojdzie do kolizji, możemy po prostu przejść dalej i znaleźć puste miejsce do przechowywania naszej wartości.

Poniżej przedstawiono metody sondowania:

metoda Opis
Sondowanie liniowe Jak sama nazwa wskazuje, ta metoda wyszukuje puste miejsca liniowo, zaczynając od miejsca, w którym nastąpiła kolizja, i posuwając się naprzód. Jeśli osiągnięto koniec listy i nie znaleziono pustego miejsca. Sondowanie rozpoczyna się na początku listy.
Sondowanie kwadratowe Ta metoda wykorzystuje kwadratowe wyrażenia wielomianowe do znalezienia następnego wolnego miejsca.
Podwójne haszowanie Ta technika wykorzystuje dodatkowy algorytm funkcji skrótu, aby znaleźć następny wolny dostępny slot.

Korzystając z powyższego przykładu, tablica skrótów po użyciu sondowania wyglądałaby następująco:

Operacje na tablicy skrótów

Oto operacje obsługiwane przez tabele skrótów:

  • Wstawianie - ta operacja służy do dodawania elementu do tablicy skrótów
  • Wyszukiwanie - ta operacja służy do wyszukiwania elementów w tablicy skrótów za pomocą klucza
  • Usuwanie - ta operacja służy do usuwania elementów z tablicy skrótów

Operacja wstawiania danych

Operacja wstawiania służy do przechowywania wartości w tablicy skrótów. Gdy nowa wartość jest przechowywana w tablicy skrótów, przypisywany jest jej numer indeksu. Numer indeksu jest obliczany za pomocą funkcji skrótu. Funkcja skrótu rozwiązuje wszelkie kolizje, które występują podczas obliczania numeru indeksu.

Wyszukaj operację na danych

Operacja wyszukiwania służy do wyszukiwania wartości w tablicy skrótów przy użyciu numeru indeksu. Operacja wyszukiwania zwraca wartość, która jest połączona z numerem indeksu wyszukiwania. Na przykład, jeśli zapiszemy wartość 6 pod indeksem 2, operacja wyszukiwania z indeksem numer 2 zwróci wartość 6.

Usuń operację na danych

Operacja usuwania służy do usuwania wartości z tabeli skrótów. Aby usunąć operację, należy użyć numeru indeksu. Po usunięciu wartości numer indeksu staje się wolny. Może służyć do przechowywania innych wartości za pomocą operacji wstawiania.

Implementacja tablicy skrótów na przykładzie języka Python

Spójrzmy na prosty przykład, który oblicza wartość skrótu klucza

def hash_key( key, m):return key % mm = 7print(f'The hash value for 3 is {hash_key(3,m)}')print(f'The hash value for 2 is {hash_key(2,m)}')print(f'The hash value for 9 is {hash_key(9,m)}')print(f'The hash value for 11 is {hash_key(11,m)}')print(f'The hash value for 7 is {hash_key(7,m)}')

Objaśnienie kodu tablicy skrótów

TUTAJ,

  1. Definiuje funkcję hash_key, która akceptuje klucz parametrów im.
  2. Używa prostej operacji modułu do określenia wartości skrótu
  3. Definiuje zmienną m, która jest inicjalizowana na wartość 7. To jest rozmiar naszej tablicy skrótów
  4. Oblicza i drukuje wartość skrótu 3
  5. Oblicza i drukuje wartość skrótu 2
  6. Oblicza i drukuje wartość skrótu 9
  7. Oblicza i drukuje wartość skrótu 11
  8. Oblicza i drukuje wartość skrótu 7

Wykonanie powyższego kodu daje następujące wyniki.

The hash value for 3 is 3The hash value for 2 is 2The hash value for 9 is 2The hash value for 11 is 4The hash value for 7 is 0

Przykład słownika Pythona

Python zawiera wbudowany typ danych o nazwie Dictionary. Słownik jest przykładem tablicy skrótów. Przechowuje wartości za pomocą pary kluczy i wartości. Wartości skrótu są dla nas generowane automatycznie, a wszelkie kolizje są dla nas rozwiązywane w tle.

Poniższy przykład pokazuje, jak można użyć typu danych słownikowych w Pythonie 3

employee = {'name': 'John Doe','age': 36,'position': 'Business Manager.'}print (f"The name of the employee is {employee['name']}")employee['position'] = 'Software Engineer'print (f"The position of {employee['name']} is {employee['position']}")employee.clear()print (employee)

TUTAJ,

  1. Definiuje zmienną słownikową pracownika. Nazwa klucza służy do przechowywania wartości John Doe, wiek przechowuje 36, a pozycja przechowuje wartość Business Manager.
  2. Pobiera wartość nazwy klucza i drukuje ją w terminalu
  3. Aktualizuje wartość pozycji kluczowej do wartości Inżynier oprogramowania
  4. Wyświetla wartości nazwy i pozycji kluczy
  5. Usuwa wszystkie wartości, które są przechowywane w naszej zmiennej słownikowej pracownika
  6. Drukuje wartość pracownika

Uruchomienie powyższego kodu daje następujące wyniki.

The name of the employee is John Doe.The position of John Doe is a Software Engineer.{}

Analiza złożoności

Tabele skrótów mają średnią złożoność czasową O (1) w najlepszym scenariuszu. W najgorszym przypadku złożoność czasowa to O (n). Najgorszy scenariusz ma miejsce, gdy wiele wartości generuje ten sam klucz mieszający i musimy rozwiązać kolizję przez sondowanie.

Aplikacje w świecie rzeczywistym

W świecie rzeczywistym tabele skrótów są używane do przechowywania danych

  • Bazy danych
  • Tablice asocjacyjne
  • Zestawy
  • Pamięć podręczna

Zalety tablic mieszających

Oto zalety / zalety korzystania z tabel skrótów:

  • Tabele skrótów mają wysoką wydajność podczas wyszukiwania danych, wstawiania i usuwania istniejących wartości.
  • Złożoność czasowa dla tabel skrótów jest stała niezależnie od liczby elementów w tabeli.
  • Działają bardzo dobrze nawet podczas pracy z dużymi zbiorami danych.

Wady tabel skrótów

Oto wady korzystania z tabel skrótów:

  • Nie można użyć wartości null jako klucza.
  • Nie można uniknąć kolizji podczas generowania kluczy przy użyciu. funkcje skrótu. Kolizje występują, gdy generowany jest już używany klucz.
  • Jeśli funkcja haszowania ma wiele kolizji, może to prowadzić do spadku wydajności.

Podsumowanie:

  • Tabele skrótów służą do przechowywania danych przy użyciu pary kluczy i wartości.
  • Funkcja skrótu używa algorytmu matematycznego do obliczenia wartości skrótu.
  • Kolizja występuje, gdy ta sama wartość skrótu jest generowana dla więcej niż jednej wartości.
  • Tworzenie łańcuchów rozwiązuje kolizje, tworząc połączone listy.
  • Sondowanie rozwiązuje kolizję, znajdując puste miejsca w tablicy skrótów.
  • Sondowanie liniowe wyszukuje następny wolny slot, aby zapisać wartość, zaczynając od szczeliny, w której wystąpiła kolizja.
  • Sondowanie kwadratowe wykorzystuje wyrażenia wielomianowe, aby znaleźć następną wolną szczelinę, gdy wystąpi kolizja.
  • Podwójne haszowanie wykorzystuje dodatkowy algorytm funkcji skrótu, aby znaleźć następny wolny slot, gdy wystąpi kolizja.
  • Tabele skrótów mają lepszą wydajność w porównaniu z innymi strukturami danych.
  • Średnia złożoność czasowa tabel skrótów wynosi O (1)
  • Typ danych słownikowych w Pythonie jest przykładem tablicy skrótów.
  • Tabele skrótów obsługują operacje wstawiania, wyszukiwania i usuwania.
  • Wartość pusta nie może być używana jako wartość indeksu.
  • W funkcjach skrótu nie można uniknąć kolizji. Dobra funkcja skrótu minimalizuje liczbę kolizji, które mają na celu poprawę wydajności.