Tabela skrótów w strukturze danych: Python Przykład
Sara Chen
Co to jest haszowanie?
Hash to wartość o stałej długości, generowana przy użyciu wzoru matematycznego. Wartości skrótu są używane w kompresji danych, kryptologii itp. Podczas indeksowania danych wartości skrótu są używane, ponieważ mają stałą długość, niezależnie od wartości użytych do ich wygenerowania. Sprawia, że wartości skrótu zajmują minimalną ilość miejsca w porównaniu z innymi wartościami o różnej długości.
Funkcja skrótu wykorzystuje algorytm matematyczny do konwersji klucza na skrót. Kolizja ma miejsce, gdy funkcja mieszająca generuje tę samą wartość skrótu dla więcej niż jednego klucza.
Co to jest tabela mieszająca?
A TABELA HASZU to struktura danych przechowująca wartości za pomocą pary kluczy i wartości. Każdej wartości przypisany jest unikalny klucz generowany za pomocą funkcji skrótu.
Nazwa klucza jest używana do dostępu do jego skojarzonej wartości. Dzięki temu wyszukiwanie wartości w tablicy skrótów jest bardzo szybkie, niezależnie od liczby elementów w tablicy skrótów.
Funkcje skrótu
Na przykład, jeśli chcemy przechowywać dokumentację 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 dodatkowej wolnej przestrzeni rzędu (m * n2) gdzie zmienna m jest rozmiarem szyk, a zmienna n to liczba cyfr numeru pracownika. Takie podejście wprowadza problem związany z przestrzenią do przechowywania.
Funkcja skrótu rozwiązuje powyższy problem, pobierając numer pracownika i używając go do generowania 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, następnie na podstawie algorytmu oblicza wartość klucza.
Poniżej znajduje się przykład prostej funkcji skrótu
h(k) = k1 % m
TUTAJ,
- h(k) to funkcja skrótu, która akceptuje parametr k. Parametr k jest wartością, dla której chcemy obliczyć klucz.
- k1 % m to algorytm naszej funkcji skrótu, gdzie k1 to wartość, którą chcemy zapisać, a m to rozmiar listy. Używamy operatora modulo, aby obliczyć klucz.
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 do obliczenia pozycji, które powinna zajmować każda wartość.
Poniższy obraz pokazuje dostępne indeksy w naszej tablicy skrótów.
Krok 1) Oblicz pozycję, jaką zajmie pierwsza wartość w ten sposób
h(1) = 1% 3
= 1
Wartość 1 zajmie spacja na indeks 1
Krok 2) Oblicz pozycję, którą zajmie druga wartość
h(2) = 2% 3
= 2
Wartość 2 zajmie spacja na indeks 2
Krok 3) Oblicz pozycję, którą zajmie trzecia wartość.
h(3) = 3% 3
= 0
Wartość 3 zajmie spacja na indeks 0
Wynik końcowy
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 spełniać następujące cechy.
- Formuła generowania skrótu powinna wykorzystywać wartość danych, które mają być zapisane w algorytmie.
- Funkcja skrótu powinna generować unikalne wartości skrótu nawet dla danych wejściowych o tej samej wartoś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ć konsekwentnie rozłożone na wszystkie możliwe skróty.
Kolizja
Kolizja ma miejsce, 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 mieszającej wynosi 7 i skorzystamy ze wzoru (k1 % m) gdzie m jest rozmiarem tablicy mieszającej.
Poniższa tabela przedstawia wartości skrótu, które zostaną wygenerowane.
| Klawisz | Algorytm mieszający (k1% 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ć, stosując łańcuchowanie lub sondowanie. Poniższe sekcje szczegółowo omawiają łańcuchowanie i sondowanie.
Łańcuch
Łączenie w łańcuchy to technika stosowana do rozwiązywania problemu kolizji przy użyciu połączonych list, z których każda ma unikalne indeksy.
Poniższy obraz pokazuje, jak wygląda lista łańcuchowa
Zarówno 2, jak i 9 zajmują ten sam indeks, ale są przechowywane jako listy połączone. Każda lista ma unikalny identyfikator.
Korzyści z list łańcuchowych
Oto zalety list łańcuchowych:
- Listy łańcuchowe mają lepszą wydajność podczas wstawiania danych, ponieważ kolejność wstawiania jest równa O(1).
- Nie jest konieczna zmiana rozmiaru tabeli mieszającej, która korzysta z listy połączonej.
- Może z łatwością pomieścić dużą liczbę wartości, o ile jest dostępne wolne miejsce.
Sondowanie
Inną techniką stosowaną do rozwiązywania kolizji jest sondowanie. Jeśli podczas korzystania z metody sondowania wystąpi kolizja, możemy po prostu przejść dalej i znaleźć puste miejsce do przechowywania naszej wartości.
Poniżej przedstawiono metody sondowania:
| Metoda wykonania | Opis |
|---|---|
| Sondowanie liniowe | Jak sama nazwa wskazuje, metoda ta wyszukuje puste miejsca liniowo, zaczynając od miejsca, w którym doszło do kolizji i posuwając się do przodu. Jeśli osiągnięty zostanie koniec listy i nie zostanie znalezione żadne puste miejsce. Sondowanie rozpoczyna się od początku listy. |
| Sondowanie kwadratowe | Ta metoda wykorzystuje kwadratowe wyrażenia wielomianowe w celu znalezienia następnego wolnego miejsca. |
| Double Hashing | Technika ta wykorzystuje algorytm dodatkowej funkcji skrótu w celu znalezienia następnego wolnego wolnego miejsca. |
Korzystając z naszego powyższego przykładu, tabela mieszająca po użyciu sondowania wyglądałaby następująco:
Operacje na tablicy skrótów
Tu są Operaobsługiwane przez tablice Hash:
- Wprowadzenie - to Operasłuży do dodania elementu do tablicy mieszającej
- Badawczy - to Operasłuży do wyszukiwania elementów w tablicy mieszającej za pomocą klawisza
- Usuwanie - to Operasłuży do usuwania elementów z tablicy mieszającej
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 występujące podczas obliczania numeru indeksu.
Wyszukaj operację danych
Operacja wyszukiwania służy do wyszukiwania wartości w tabeli skrótów przy użyciu numeru indeksu. Operacja wyszukiwania zwraca wartość, która jest powiązana z numerem indeksu wyszukiwania. Na przykład, jeśli zapiszemy wartość 6 pod indeksem 2, operacja wyszukiwania z numerem indeksu 2 zwróci wartość 6.
Operacja usuwania danych
Operacja usuwania jest używana do usuwania wartości z tablicy skrótów. Aby usunąć Operacja odbywa się przy użyciu numeru indeksu. Po usunięciu wartości numer indeksu zostaje zwolniony. Można go użyć do przechowywania innych wartości przy użyciu operacji wstawiania.
Implementacja tabeli mieszającej za pomocą Python Przykład
Spójrzmy na prosty przykład, który oblicza wartość skrótu klucza
def hash_key( key, m):
return key % m
m = 7
print(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)}')
Wyjaśnienie kodu tabeli skrótów
TUTAJ,
- Definiuje funkcję hash_key, która akceptuje parametry key i m.
- Używa prostej operacji modulo do określenia wartości skrótu
- Definiuje zmienną m, która jest inicjowana wartością 7. Jest to rozmiar naszej tablicy mieszającej
- Oblicza i drukuje wartość skrótu wynoszącą 3
- Oblicza i drukuje wartość skrótu wynoszącą 2
- Oblicza i drukuje wartość skrótu wynoszącą 9
- Oblicza i drukuje wartość skrótu wynoszącą 11
- Oblicza i drukuje wartość skrótu wynoszącą 7
Wykonanie powyższego kodu daje następujące rezultaty.
The hash value for 3 is 3 The hash value for 2 is 2 The hash value for 9 is 2 The hash value for 11 is 4 The hash value for 7 is 0
Python Przykład słownika
Python posiada wbudowany typ danych o nazwie Dictionary. Słownik jest przykładem tablicy mieszającej. Przechowuje wartości za pomocą pary kluczy i wartości. Wartości skrótu są dla nas generowane automatycznie, a wszelkie kolizje rozwiązywane są za nas w tle.
Poniższy przykład pokazuje, jak można używać typu danych słownikowych w python 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,
- Definiuje zmienną słownikową pracownik. Nazwa klucza służy do przechowywania wartości John Doe, wiek przechowuje 36, a pozycja przechowuje wartość Business Manager.
- Pobiera wartość nazwy klucza i wypisuje ją w terminalu
- Aktualizuje wartość pozycji klucza do wartości Software Engineer
- Drukuje wartości nazwy i pozycji kluczy
- Usuwa wszystkie wartości zapisane w naszym słowniku zmiennej pracowniczej
- Drukuje wartość pracownika
Uruchomienie powyższego kodu daje następujące rezultaty.
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 przypadku. Złożoność czasowa w najgorszym przypadku wynosi O(n). Najgorszy scenariusz występuje, gdy wiele wartości generuje ten sam klucz skrótu i musimy rozwiązać kolizję poprzez sondowanie.
Aplikacje w świecie rzeczywistym
W świecie rzeczywistym tablice mieszające służą do przechowywania danych
- Bazy danych
- Tablice asocjacyjne
- Zestawy
- Pamięć podręczna
Zalety tabel mieszających
Oto zalety/korzyści korzystania z tabel skrótów:
- Tabele skrótów charakteryzują się wysoką wydajnością podczas wyszukiwania danych, wstawiania i usuwania istniejących wartości.
- Złożoność czasowa tablic 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 tablic mieszających
Oto wady używania tabel skrótów:
- Nie można użyć wartości null jako klucza.
- Nie da się uniknąć kolizji podczas generowania kluczy za pomocą. funkcje skrótu. Kolizje występują, gdy generowany jest klucz, który jest już używany.
- Jeśli funkcja mieszająca 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 wykorzystuje algorytm matematyczny do obliczenia wartości skrótu.
- Do kolizji dochodzi, gdy dla więcej niż jednej wartości zostanie wygenerowana ta sama wartość skrótu.
- Łańcuch rozwiązuje kolizje, tworząc połączone listy.
- Sondowanie rozwiązuje kolizję, znajdując puste miejsca w tabeli skrótów.
- Sondowanie liniowe wyszukuje następną wolną szczelinę, aby zapisać wartość, zaczynając od szczeliny, w której wystąpiła kolizja.
- Sondowanie kwadratowe wykorzystuje wyrażenia wielomianowe do znalezienia następnego wolnego miejsca w przypadku wystąpienia kolizji.
- Double hashowanie wykorzystuje algorytm dodatkowej funkcji mieszającej do znalezienia następnego wolnego miejsca w przypadku wystąpienia kolizji.
- Tabele mieszające mają lepszą wydajność w porównaniu do innych struktur danych.
- Średnia złożoność czasowa tablic skrótów wynosi O (1)
- Słownikowy typ danych w Pythonie jest przykładem tablicy mieszającej.
- Tablice skrótów obsługują operacje wstawiania, wyszukiwania i usuwania.
- Wartości null nie można użyć jako wartości indeksu.
- W funkcjach skrótu nie da się uniknąć kolizji. Dobra funkcja skrótu minimalizuje liczbę kolizji, które występują, aby poprawić wydajność.
