Haszowanie to podstawowa struktura danych, która skutecznie przechowuje i pobiera dane w sposób umożliwiający szybki dostęp. Polega na mapowaniu danych na określony indeks w tabeli skrótów za pomocą a funkcja skrótu który umożliwia szybkie odnalezienie informacji na podstawie jej klucza. Metoda ta jest powszechnie stosowana w bazach danych, C systemy bolące oraz różne aplikacje programistyczne optymalizujące operacje wyszukiwania i odzyskiwania.
Struktury danych – haszowanie
pętla do i while w Javie
Spis treści
- Funkcja skrótu
- Co to jest kolizja skrótu?
- Techniki rozwiązywania kolizji
- Zastosowania haszowania
- Łatwy problem z haszowaniem
- Średni problem z haszowaniem
- Trudny problem z haszowaniem
Jak to działa:
- Funkcja skrótu: Podajesz elementy danych do funkcji skrótu.
- Kod skrótu: Funkcja skrótu przetwarza dane i podaje unikalny kod skrótu.
- Tabela mieszająca: Kod skrótu wskazuje następnie konkretną lokalizację w tabeli skrótów.
Funkcja skrótu
The funkcja skrótu jest funkcją, która przyjmuje a klucz i zwraca indeks w tablica mieszająca . Celem funkcji skrótu jest równomierne rozmieszczenie kluczy w tablicy mieszającej, minimalizując kolizje (gdy dwa klucze są mapowane na ten sam indeks).
Typowe funkcje skrótu obejmują:
- Metoda podziału: Kluczowy % Rozmiar tabeli mieszającej
- Metoda mnożenia: (Klucz * Stała) % Rozmiar tablicy mieszającej
- Uniwersalne haszowanie: Rodzina funkcji skrótu zaprojektowana w celu minimalizacji kolizji
Co to jest kolizja skrótu?
Kolizja skrótu ma miejsce, gdy dwa różne klucze są mapowane na ten sam indeks w tabeli skrótów. Może się to zdarzyć nawet przy dobrej funkcji skrótu, szczególnie jeśli tablica mieszająca jest pełna lub klucze są podobne.
Przyczyny kolizji skrótów:
- Słaba funkcja skrótu: Funkcja mieszająca, która nie rozdziela kluczy równomiernie w tablicy mieszającej, może prowadzić do większej liczby kolizji.
- Wysoki współczynnik obciążenia: Wysoki współczynnik obciążenia (stosunek kluczy do rozmiaru tablicy mieszającej) zwiększa prawdopodobieństwo kolizji.
- Podobne klucze: Klucze o podobnej wartości lub strukturze częściej kolidują.
Techniki rozwiązywania kolizji
Istnieją dwa rodzaje technik rozwiązywania kolizji:
- Otwarte adresowanie:
- Sondowanie liniowe: Wyszukaj kolejno puste miejsce
- Sondowanie kwadratowe: Wyszukaj puste miejsce za pomocą funkcji kwadratowej
- Zamknięte adresowanie:
- Łańcuch: Przechowuj kolidujące klucze na połączonej liście lub drzewie wyszukiwania binarnego w każdym indeksie
- Mieszanie z kukułką: Użyj wielu funkcji skrótu do dystrybucji kluczy
Zastosowania haszowania
Tabele skrótów są używane w wielu różnych zastosowaniach, w tym:
- Bazy danych: Przechowywanie i pobieranie danych w oparciu o unikalne klucze
- Buforowanie: Przechowywanie często używanych danych w celu szybszego ich wyszukiwania
- Tabele symboli: Mapowanie identyfikatorów na ich wartości w językach programowania
- Routing sieciowy: Wyznaczanie najlepszej ścieżki dla pakietów danych
Co to jest haszowanie?
Łatwy problem z haszowaniem
- Sprawdza, czy tablica jest podzbiorem innej tablicy
- Suma i przecięcie dwóch połączonych list
- Mając tablicę A[] i liczbę x, sprawdź parę w A[] z sumą jako x
- Maksymalna odległość między dwoma wystąpieniami tego samego elementu w tablicy
- Policz maksymalną liczbę punktów na tej samej linii
- Najczęstszy element tablicy
- Znajdź jedyny powtarzający się element pomiędzy 1 a n-1
- Jak sprawdzić, czy dwa dane zbiory są rozłączne?
- Nienakładająca się suma dwóch zbiorów
- Sprawdź, czy dwie tablice są równe, czy nie
- Znajdź brakujące elementy zakresu
- Minimalna liczba podzbiorów z odrębnymi elementami
- Usuń minimalną liczbę elementów, tak aby w obu tablicach nie istniał żaden wspólny element
- Znajdź pary o podanej sumie tak, aby elementy pary znajdowały się w różnych wierszach
- Policz pary o podanej sumie
- Policz czwórki z czterech posortowanych tablic, których suma jest równa danej wartości x
- Sortuj elementy według częstotliwości
- Znajdź wszystkie pary (a, b) w tablicy takiej, że a % b = k
- Grupuj słowa z tym samym zestawem znaków
- k-ty odrębny (lub niepowtarzający się) element tablicy.
Średni problem z haszowaniem
- Znajdź Plan Podróży na podstawie podanej listy biletów
- Znajdź liczbę pracowników pod każdym pracownikiem
- Najdłuższa podtablica z sumą podzielną przez k
- Znajdź największą podtablicę o sumie 0
- Najdłuższy rosnący kolejny podciąg
- Policz różne elementy w każdym oknie o rozmiarze k
- Znajdź podtablicę z podaną sumą | Zestaw 2 (obsługuje liczby ujemne)
- Implementacja naszej własnej tabeli skrótów z oddzielnym łańcuchem w Javie
- Implementacja własnej tablicy mieszającej z sondowaniem liniowym z otwartym adresowaniem w C++
- Minimalne wstawki tworzące palindrom z dozwolonymi permutacjami
- Maksymalna możliwa różnica dwóch podzbiorów tablicy
- Sortowanie za pomocą trywialnej funkcji skrótu
- Najmniejsza podtablica zawierająca k różnych liczb
Trudny problem z haszowaniem
- Klonuj drzewo binarne za pomocą losowych wskaźników
- Największa podtablica z równą liczbą zer i jedynek
- Wszystkie unikalne trójki, które sumują się do określonej wartości
- Zapytania o podciągi palindromu
- Zapytania o zakres dla częstotliwości elementów tablicy
- Elementy, które należy dodać, aby wszystkie elementy zakresu były obecne w tablicy
- Cuckoo Hashing – najgorszy przypadek wyszukiwania O(1)!
- Policz podtablice posiadające łącznie różne elementy takie same jak oryginalna tablica
- Maksymalna tablica z dwóch podanych tablic, zachowująca tę samą kolejność
- Znajdź sumę wszystkich unikalnych sum podtablicy dla danej tablicy.
- Sekwencja Recamana
- Długość najdłuższego ścisłego podciągu bitonicznego
- Znajdź wszystkie zduplikowane poddrzewa
- Znajdź, czy w macierzy binarnej istnieje prostokąt z narożnikami o wartości 1
Szybkie linki :
- „Zadania praktyczne” dotyczące haszowania
- 20 najważniejszych pytań do wywiadu opartych na technice haszowania
- „Filmy” na temat haszowania
Zalecana:
- Naucz się struktury danych i algorytmów | Poradnik DSA