a w Pythonie w drodze, lub w języku JavaScript. Array Associative w PHP, w C++. Mapy hash są wdrażane w praktycznie każdym języku programowania na wysokim poziomie. I są niesamowite! Kto nie chce przechowywać, a następnie uzyskać dostęp do danych w stałym czasie? Niezależnie od tego, czy pracujesz z dużymi zestawami danych, czy masz problemy z Leetcode, bardzo często ta struktura danych przychodzi na ratunek. Ale czym dokładnie są i jak działają pod kapturem? W tym artykule spróbujemy odpowiedzieć na te pytania. dict map Object Map Dictionary<TKey, TValue> Czym jest mapa hash? Na wysokim poziomie mapa haszowa lub tabela haszowa to struktura danych, która wdraża typ danych abstrakcyjnych array associative, strukturę, która może mapować klucze do wartości. Klucz służy do unikalnej identyfikacji wartości na mapie, a wartość to dane, które są przechowywane. In fact, the average time complexity for these operations is O(1), which means that they can be performed in constant time! This feature makes hash maps probably the most used data structure in programming, however, there are some caveats to this, as we will see later. Najgorsza złożoność czasu dla tych operacji to O(n), co może się zdarzyć w niektórych scenariuszach, a im więcej wiemy o wewnętrznych, tym bardziej prawdopodobne jest, że unikniemy tych scenariuszy. Zgodnie z : Artykuł Wikipedii Tabela haszowa jest strukturą danych, która wdraża matrycę asocjacyjną, nazywaną również słownikiem lub po prostu mapą; Tabela asocjacyjna jest abstrakcyjnym typem danych, który mapuje klucze do wartości. Tabela haszowa wykorzystuje funkcję haszowa do obliczania indeksu, nazywanego również kodem haszowym, w zestawie pudełek lub slotów, z których można znaleźć pożądaną wartość. Tabela haszowa jest strukturą danych, która wdraża matrycę asocjacyjną, nazywaną również słownikiem lub po prostu mapą; Tabela asocjacyjna jest abstrakcyjnym typem danych, który mapuje klucze do wartości. Tabela haszowa wykorzystuje funkcję haszowa do obliczania indeksu, nazywanego również kodem haszowym, w zestawie pudełek lub slotów, z których można znaleźć pożądaną wartość. Więc zróbmy krok wstecz i przyjrzyjmy się składnikom mapy hash. Czym jest funkcja hash? Funkcja hash jest funkcją, która bierze wejście (lub "klucz") i zwykle zwraca liczbę całkowitą, która jest używana do indeksowania danych na mapie hash. Dobra funkcja hash posiada następujące właściwości: Determinizm: ten sam wkład zawsze przynosi ten sam wynik. Jednolita dystrybucja: Funkcja hash powinna równomiernie rozprowadzać klucze w całej tabeli hash, aby zminimalizować kolizje. Szybkie obliczenia: Funkcja hash powinna być szybka do obliczenia, nawet przy dużych wejściach. Zminimalizuj kolizje: Przestrzeń możliwych kluczy jest zazwyczaj znacznie większa (często nieskończona) niż przestrzeń kodów hash. Oznacza to, że różne klucze mogą wytwarzać ten sam kod hash. Podczas gdy te kolizje są nieuniknione, dobra funkcja hash minimalizuje szanse dwóch różnych kluczy wytwarzania tego samego kodu hash. Prostym przykładem funkcji hash jest operacja modulo, która bierze klucz i zwraca resztę, gdy dzieli się przez rozmiar tabeli hash. Na przykład, jeśli mamy tabelę hash o rozmiarze 10 i klucz 23, kod hash byłby , co oznacza, że wartość skojarzona z kluczem 23 będzie przechowywana w indeksie 3 w podstawowym zestawie. również, co oznacza, że mamy zderzenie.W tym przypadku oba klucze będą mapować do tego samego indeksu w arenie. 23 % 10 = 3 33 % 10 = 3 Co to jest Bucket? W przypadku kolizji, w której dwa różne klucze wytwarzają ten sam kod hash, kubek może przechowywać wiele par kluczy-wartości. Ten wykres ilustruje, jak to wszystko działa: Tutaj możemy zobaczyć, w jaki sposób funkcja hash mapuje klucze do indeksów w podstawowej arenie. Klucze 23 i 33 wytwarzają ten sam kod hash 3, co oznacza, że są przechowywane w tej samej beczce. W beczce można następnie przechowywać obie pary wartości klucza, ale gdy odzyskujemy wartość, musimy sprawdzić klucze w beczce, aby znaleźć właściwy. Factor obciążenia Współczynnik obciążenia jest miarą tego, jak pełna jest tabela hash. Obliczana jest jako liczba elementów w tabeli hash podzielona przez liczbę beczek (lub gniazd) w podstawowym zestawie. Wyższy współczynnik obciążenia oznacza, że w tabeli hash jest więcej elementów w stosunku do liczby beczek, co może prowadzić do większych kolizji i wolniejszej wydajności. Rezolucja kolizji Gdy dwa klucze wytwarzają ten sam kod hash, mamy zderzenie. : In this method, each bucket contains a linked list (or another data structure) of all key-value pairs that hash to the same index. When a collision occurs, the new key-value pair is simply added to the list in the appropriate bucket. This is the most common method for handling collisions. Chaining : Average O(1) for all operations, worst-case O(n) if all keys hash to the same bucket Complexity : Simple to implement, handles high load factors well, deletion is straightforward Pros : Extra memory overhead for pointers, poor cache performance due to scattered memory access Cons Otwarte adresowanie: W tej metodzie, gdy dojdzie do kolizji, tabela hash wyszukuje następny dostępny slot w arenie, aby przechowywać nową parę wartości klucza. Jeśli dojdzie do kolizji, algorytm sprawdza następny slot w arenie, aż znajdzie pusty. Linear Probing Złożoność: Średnia O(1), najgorszy przypadek O(n) z powodu pierwotnego klasterowania Zalety: prosta implementacja, dobra wydajność pamięci podręcznej dla dostępów w pobliżu Wady: klasterowanie podstawowe (konsekutywne zajęcia), degradacja wydajności z klasterowaniem Zamiast sprawdzać następny slot, sprawdza automaty na coraz większych odległościach (1, 4, 9, itp.) od oryginalnego indeksu. Quadratic Probing Złożoność: Średnia O(1), lepsza niż sondowanie liniowe ze względu na zmniejszone gromadzenie Zalety: Zmniejsza klasterowanie podstawowe w porównaniu do sondowania liniowego, nadal przyjazny dla pamięci podręcznej Wady: klastrowanie wtórne (klucze z tym samym hashem podążają za tą samą sekwencją sondy), może nie odwiedzić wszystkich gniazdek : Używa drugiej funkcji hash, aby określić rozmiar kroku do sondowania. W przeciwieństwie do sondowania liniowego, które zawsze przenosi się do następnego gniazda, lub sondowania kwadratowego, które używa stałej sekwencji, podwójne hashowanie oblicza unikalny rozmiar kroku dla każdego klucza. gdzie jest numerem próby sondy. druga funkcja hash musi zwrócić wartość, która jest stosunkowo prymalna w stosunku do rozmiaru tabeli, aby upewnić się, że wszystkie gniazda można odwiedzić. i , a następnie badamy indeksy 7, 10, 13, 16 itp. Double Hashing index = (hash1(key) + i * hash2(key)) % table_size i hash1(key) = 7 hash2(key) = 3 : Average O(1), best performance among open addressing methods Complexity : Minimizes clustering, uniform distribution of probe sequences, visits all slots when properly implemented Pros : More complex implementation, requires computing two hash functions, and slightly more overhead per operation Cons : If the load factor becomes too high, the hash table can be resized and all existing key-value pairs can be rehashed into the new table. This helps to maintain efficient performance as the number of elements grows. Rehashing : O(n) for the rehashing operation itself, but amortizes to O(1) per insertion over time Complexity : Maintains optimal performance by keeping the load factor low, prevents performance degradation Pros : Temporary performance spike during rehashing, requires additional memory during the resize operation Cons Każda z tych metod ma swoje własne kompromisy pod względem złożoności, wydajności i wykorzystania pamięci.Wybór strategii rozwiązywania kolizji może mieć znaczący wpływ na ogólną wydajność mapy hash. Oto krótkie podsumowanie zalet i wad każdej metody rozwiązywania kolizji: Feature Chaining Linear Probing Quadratic Probing Double Hashing Average Time Complexity O(1) O(1) O(1) O(1) Worst-case Time Complexity O(n) O(n) O(n) O(n) Memory Overhead High (pointers) Low Low Low Cache Performance Poor Good Good Moderate Implementation Complexity Simple Simple Moderate Complex Clustering Issues None Primary clustering Secondary clustering Minimal Load Factor Tolerance High (>1.0) Low (<0.7) Low-Medium (<0.7) Medium (<0.8) Deletion Complexity Simple Complex (tombstones) Complex (tombstones) Complex (tombstones) Space Efficiency Lower Higher Higher Higher Performance Degradation Gradual Rapid at high load Moderate at high load Slow at high load Hash Function Requirements One One One Two Best Use Cases Unknown load factors, frequent deletions Cache-friendly applications, low load Better than linear, moderate load High performance, predictable load Average Time Complexity O (1) O (1) O (1) O (1) Worst-case Time Complexity O (n) O (n) O (n) O (n) Memory Overhead Wysokie punkty (pointers) niskiej niskiej niskiej Cache Performance Biedny Dobrze Dobrze Umiarkowany Implementation Complexity prosty prosty Umiarkowany Kompleksowy Clustering Issues Nikt Podstawowe klastry Klastry wtórne Minimalna Load Factor Tolerance Wysoki poziom (>1.0) Niski poziom (< 0,7) Niskie średnie (< 0,7) Średnia (< 0,8) Deletion Complexity prosty Kompleksy (grobne kamienie grobowe) Kompleksy (grobne kamienie grobowe) Kompleksy (grobne kamienie grobowe) Space Efficiency niżej wyższa wyższa wyższa Performance Degradation stopniowo Szybkie na wysokim obciążeniu Umiarkowany przy wysokim obciążeniu Powolne na wysokim obciążeniu Hash Function Requirements Jeden Jeden Jeden Dwie Best Use Cases Nieznane czynniki obciążenia, częste usunięcia Aplikacje cache-friendly, niskie obciążenie Lepsze niż liniowe, umiarkowane obciążenie Wysoka wydajność, przewidywalne obciążenie Przykłady świata rzeczywistego Wdrażanie języków programowania Wiele języków programowania ma wbudowane mapy hash. Te wdrożenia często wykorzystują kombinację technik opisanych powyżej, aby zapewnić wydajną wydajność i skutecznie radzić sobie z kolizjami. Dict Pythona wykorzystuje otwarte adresowanie z randomizowanym sondowaniem, rehashing, gdy współczynnik obciążenia przekracza około 0,66. HashMap Java wykorzystuje łańcuchowanie z powiązanymi listami (konwertując na zrównoważone drzewa dla dużych kubków w Java 8+), przyspiesza przy współczynniku obciążenia 0,75. Mapy nierozwiązane w C++ zazwyczaj używają łańcucha, ale wdrożenia mogą się różnić. Systemy baz danych Mapy hash są również szeroko stosowane w indeksowaniu baz danych. Wiele systemów baz danych używa indeksów hash, aby przyspieszyć odzyskiwanie danych. Indeksy te pozwalają na szybkie wyszukiwania poprzez hashowanie indeksowanych kolumn i przechowywanie powstałych par wartości klucza w tabeli hash. Niektóre popularne systemy baz danych, które wykorzystują indeksowanie hash, to: PostgreSQL: Obsługuje indeksy hash, ale nie są one tak powszechnie stosowane jak indeksy B-tree. MongoDB: Używa indeksów hash do rozdrabniania i obsługi zapytań równości w polach hash. Redis: Wdraża mapy hash jako podstawową strukturę danych, umożliwiając efektywne przechowywanie i odzyskiwanie par kluczowych wartości. Te wdrożenia często wykorzystują te same podstawowe zasady hashingu i rozwiązywania kolizji omówione wcześniej, ale mogą również uwzględniać dodatkowe optymalizacje specyficzne dla kontekstu bazy danych. Kontrola wersji Systemy kontroli wersji, takie jak Git, wykorzystują mapy hash, aby efektywnie zarządzać zmianami plików i śledzić wersje. Każdy kompromis w Git jest identyfikowany przez hash SHA-1 jego zawartości, który służy jako unikalny klucz dla obiektu kompromisów. To pozwala Gitowi szybko szukać kompromisów, gałęzi i innych obiektów w repozytorium. Łączenie wszystkiego razem: jak wdrażanie wiedzy ma znaczenie Zrozumienie, w jaki sposób mapy hash są wdrażane w wybranym języku programowania, może prowadzić do znacznych ulepszeń wydajności kodu. Na przykład w przypadku Pythona wykorzystuje otwarte adresowanie z zoptymalizowaną obsługą strun, zrozumienie tego może prowadzić do znacznie lepszej wydajności. dict Bad Implementation (walczy z Python's Dict) def count_words_bad(text): word_counts = {} words = text.split() for word in words: # This is inefficient with open addressing! if word in word_counts: # First lookup word_counts[word] += 1 # Second lookup + assignment else: word_counts[word] = 1 # Third lookup + assignment return word_counts Wejdź w tryb pełnego ekranu Wejdź w tryb pełnego ekranu Problems: Wiele hash lookupów na słowo (do 3!) Otwarte adresowanie sprawia, że brakujące czeki kluczy są drogie Nie wykorzystuje optymalizacji Pythona Dobra implementacja (pracuje z Python's Dict) from collections import defaultdict, Counter def count_words_good_v1(text): # defaultdict eliminates key existence checks word_counts = defaultdict(int) words = text.split() for word in words: word_counts[word] += 1 # Single operation! return dict(word_counts) def count_words_good_v2(text): # Counter is optimized specifically for Python's dict implementation words = text.split() return Counter(words) def count_words_good_v3(text): # dict.get() with default avoids the membership test word_counts = {} words = text.split() for word in words: word_counts[word] = word_counts.get(word, 0) + 1 # Single lookup return word_counts Wejdź w tryb pełnego ekranu Wejdź w tryb pełnego ekranu Why These Are Better: Pojedyncza operacja hash na słowo zamiast wielu Wykorzystuje optymalizację strun Pythona - klucze strun są obsługiwane bardzo efektywnie Praca z otwartym adresowaniem – potrzeba mniej operacji sondowania Używa wbudowanych optymalizacji, takich jak Counter, które są dostosowane do wdrożenia Pythona Różnice w wydajności Dobra implementacja jest często 2-3 razy szybsza, po prostu przez zrozumienie i pracę z implementacją Pythona, a nie przeciwko niemu! Typical Results: konkluzji Mapy hash należą do najbardziej podstawowych i potężnych struktur danych w dziedzinie informatyki, zapewniając niemal stały dostęp do danych, co czyni je nieodzownymi w nowoczesnym programowaniu.W całym tym głębokim nurkowaniu zbadaliśmy, w jaki sposób osiągają one niezwykłą średnią wydajność O(1) dzięki inteligentnemu wykorzystaniu funkcji hash, strategicznej rozdzielczości kolizji i starannemu zarządzaniu czynnikami obciążenia. Kluczowym wglądem jest to, że "magia" map haszowych nie jest w ogóle magia - jest wynikiem dobrze zaprojektowanych algorytmów i struktur danych, które współpracują ze sobą. Key Takeaways: Funkcje hash są podstawą – określają, w jaki sposób dane są równomiernie rozprowadzane i bezpośrednio wpływają na wskaźniki kolizji Strategie rozwiązywania kolizji mają odrębne kompromisy: łańcuchowanie dla prostoty i wytrzymałości, otwarte adresowanie dla wydajności pamięci i wydajności pamięci podręcznej Zarządzanie czynnikami obciążenia za pomocą rehashingu zapobiega degradacji wydajności w miarę wzrostu map hash Wiedza o wdrażaniu przekłada się na rzeczywiste zyski w wydajności – zrozumienie, czy Twój język używa łańcucha lub otwartego adresowania, może sprawić, że Twój kod będzie 2-3 razy szybszy Niezależnie od tego, czy optymalizujesz skrypt Python, debugujesz problemy z wydajnością w Java, czy podejmujesz decyzje architektoniczne dla systemu baz danych, to zrozumienie wewnętrznych HashMap daje narzędzia do dokonywania świadomych wyborów. , , lub Dowiesz się dokładnie, co dzieje się pod kapturem i jak wykorzystać te niesamowite struktury danych. dict HashMap unordered_map Mapy hash są naprawdę niesamowite – a teraz wiesz dlaczego!
