Cześć, Habr! Przedstawiam wam tłumaczenie artykułu
"Jak działa baza danych relacyjna?".

Myśląc o bazach danych relacyjnych, mam wrażenie, że czegoś brakuje. Są one stosowane wszędzie. Istnieje wiele różnych baz danych: od małego i użytecznego SQLite po potężną Teradata. Jednak jest tylko kilka artykułów, które wyjaśniają, jak działa baza danych. Możesz poszukać samodzielnie hasła "jakdziałaBazadanychRelacyjnych", aby zobaczyć, jak niewiele wyników znajdziesz. Co więcej, te artykuły są krótkie. Jeżeli więc interesują Cię najnowsze modne technologie (BigData, NoSQL czy JavaScript), znajdziesz więcej szczegółowych artykułów, które tłumaczą, jak one działają.

Czy bazy danych relacyjne są zbyt stare i zbyt nudne, by tłumaczyć je poza kursami uniwersyteckimi, pracami badawczymi i książkami?

Jako programista nienawidzę używać rzeczy, których nie rozumiem. A jeśli bazy danych są używane od ponad 40 lat, musi być tego powód. Przez te lata spędziłem setki godzin, aby naprawdę zrozumieć te dziwne czarne skrzynki, które wykorzystuję na co dzień. Bazy danych relacyjne są bardzo interesujące, ponieważ opierają się na użytecznych i wielokrotnie wykorzystywanych koncepcjach.Jeśli interesuje Cię zrozumienie bazy danych, ale nigdy nie miałeś czasu ani chęci zgłębiać ten szeroki temat, powinno Ci się spodobać ten artykuł.

Chociaż tytuł tego artykułu jest oczywisty, celem tego artykułu nie jest zrozumienie, jak używać bazy danych.W związku z tym, już powinieneś wiedzieć, jak napisać prosty zapytanie o połączenie i podstawowe zapytania CRUD; inaczej możesz nie zrozumieć tego artykułu. To jedyna rzecz, którą musisz znać, wyjaśnię wszystko inne.

Zacznę od podstaw informatyki, takich jak złożoność czasowa algorytmów (BigO). Wiem, że niektórzy z was nienawidzą tej koncepcji, ale bez niej nie będziecie w stanie zrozumieć subtelności wewnątrz bazy danych. Ponieważ to ogromny temat, skoncentruję się na tym, co uważam za ważne,: jak baza danych przetwarza SQL zapytanie.Przedstawię tylko podstawowe koncepcje bazy danych,aby pod koniec artykułu mieć pojęcie, co się dzieje na zapleczu.

Ponieważ jest to długi i techniczny artykuł, który zawiera wiele algorytmów i struktur danych, nie spiesz się, aby go przeczytać. Niektóre koncepcje mogą być trudne do zrozumienia; możesz je pominąć i wciąż uzyskać ogólne pojęcie.

Dla bardziej obeznanych z tematem, artykuł jest podzielony na 3 części:

Przegląd komponentów niskiego i wysokiego poziomu bazy danych
Przegląd procesu optymalizacji zapytań
Przegląd zarządzania transakcjami i buforami

Wracając do podstaw

Wiele lat temu (w odległej, odległej galaktyce...) programiści musieli dokładnie wiedzieć, ile operacji kodują. Znali na pamięć swoje algorytmy i struktury danych, ponieważ nie mogli sobie pozwolić na marnowanie CPU i pamięci w swoich wolnych komputerach.

W tej części przypomnę niektóre z tych koncepcji, ponieważ są one niezbędne do zrozumienia bazy danych. Wprowadzę również pojęcie indeksu bazy danych.

O(1) vs O(n2)

Obecnie wielu programistów nie przejmuje się złożonością czasową algorytmów… i mają rację!

Ale gdy masz do czynienia z dużymi zbiorami danych (nie mówię o tysiącach) lub walczysz o milisekundy, zrozumienie tej koncepcji staje się krytycznie ważne. Jak możesz się domyślić, bazy danych muszą radzić sobie z obiema sytuacjami! Nie zmuszę cię do spędzenia więcej czasu niż to konieczne, aby uchwycić sedno. To pomoże nam później zrozumieć koncepcję optymalizacji opartą na kosztach (koszt oparty optymalizacja).

Koncepcja

Złożoność czasowa algorytmu jest używana do określenia, ile czasu zajmie wykonanie algorytmu dla danej ilości danych.. Aby opisać tę złożoność, stosuje się matematyczne oznaczenia dużego O. To notacja, która jest używana z funkcją, która opisuje, ile operacji potrzebuje algorytm dla określonej liczby danych wejściowych.

Na przykład, gdy mówię "ten algorytm ma złożoność O (some_function() )", oznacza to, że przetwarzanie określonej ilości danych wymaga some_function(a_certain_amount_of_data) operacji.

W tym przypadku ważne jest, aby nie mówić o ilości danych,ale o tym, jak rośnie liczba operacji przy zwiększaniu objętości danych.Złożoność czasowa nie podaje dokładnej liczby operacji, ale jest dobrym sposobem na oszacowanie czasu wykonania.

Na tym wykresie możesz zobaczyć zależność liczby operacji od objętości danych wejściowych dla różnych typów złożoności czasowych algorytmów. Użyłem skali logarytmicznej, aby je przedstawić. Innymi słowy, ilość danych szybko rośnie od 1 do 1 miliarda. Możemy zauważyć, że:

O(1) lub złożoność stała pozostaje stała (inaczej nie nazywano by jej złożonością stałą).
O(log(n)) pozostaje niska nawet przy miliardach danych.
Najgorsza złożoność to — O(n2), gdzie liczba operacji szybko rośnie.
Dwie pozostałe złożoności również rosną szybko.

Przykłady

Dla małej ilości danych różnica między O(1) a O(n2) jest nieznaczna. Na przykład załóżmy, że masz algorytm, który musi przetworzyć 2000 elementów.

Algorytm O(1) wymaga 1 operacji
Algorytm O(log(n)) wymaga 7 operacji
Algorytm O(n) wymaga 2000 operacji
Algorytm O(n * log(n)) wymaga 14 000 operacji
Algorytm O(n2) wymaga 4 000 000 operacji

Różnica między O(1) a O(n2) wydaje się duża (4 miliony operacji), ale stracisz maksymalnie 2 ms, czyli czas na mrugnięcie okiem. W rzeczywistości nowoczesne procesory mogą przetwarzać setki milionów operacji na sekundę. Dlatego wydajność i optymalizacja nie są problemem w wielu projektach IT.

Jak już wspomniałem, nadal ważne jest, aby znać tę koncepcję przy pracy z ogromną ilością danych. Jeśli tym razem algorytm ma przetworzyć 1 000 000 elementów (co nie jest zbyt dużo dla bazy danych):

Algorytm O(1) wymaga 1 operacji
Algorytm O(log(n)) wymaga 14 operacji
Algorytm O(n) wymaga 1 000 000 operacji
Algorytm O(n * log(n)) wymaga 14 000 000 operacji
Algorytm O(n2) wymaga 1 000 000 000 000 operacji

Nie robiłem obliczeń, ale powiedziałbym, że używając algorytmu O(n2) masz czas na kawę (nawet dwie!). Jeśli dodasz jeszcze 0 do ilości danych, będziesz mieć czas na drzemkę.

Idziemy głębiej

Dla informacji:

Wyszukiwanie w dobrej tablicy haszującej znajduje element w O(1).
Wyszukiwanie w dobrze zbalansowanym drzewie daje wynik w O(log(n)).
Wyszukiwanie w tablicy daje wynik w O(n).
Najlepsze algorytmy sortowania mają złożoność O(n * log(n)).
Zły algorytm sortowania ma złożoność O(n2).

Uwaga: w następnych częściach zobaczymy te algorytmy i struktury danych.

Istnieje kilka typów złożoności czasowej algorytmu:

scenariusz średniego przypadku
najlepszy możliwy scenariusz
i najgorszy scenariusz

Złożoność czasowa często odnosi się do najgorszego scenariusza.

Mówiłem tylko o złożoności czasowej algorytmu, ale złożoność odnosi się również do:

zużycia pamięci przez algorytm
zużycia dyskowego wejścia/wyjścia przez algorytm

Oczywiście, istnieją złożoności gorsze niż n2, na przykład:

n4: to jest straszne! Niektóre z wspomnianych algorytmów mają taką złożoność.
3n: to jeszcze gorsze! Jeden z algorytmów, które zobaczymy w połowie tego artykułu, ma tę złożoność (i naprawdę jest używany w wielu bazach danych).
silnia n: nigdy nie uzyskasz wyników nawet z niewielką ilością danych.
nn: jeśli napotkasz tę złożoność, musisz zapytać siebie, czy to naprawdę jest twoja działka …

Uwaga: podałem ci nie rzeczywistą definicję oznaczenia „duże O”, a tylko pomysł. Możesz przeczytać ten artykuł w Wikipedii dla rzeczywistej (asymptotycznej) definicji.

MergeSort (Sortowanie przez scalanie)

Co robisz, gdy musisz posortować kolekcję? Co? Wywołujesz funkcję sort () … Ok, dobra odpowiedź … Ale w przypadku bazy danych musisz zrozumieć, jak działa ta funkcja sort ().

Istnieje kilka dobrych algorytmów sortowania, więc skupię się na najważniejszym: sortowaniu przez scalanie. Być może teraz nie rozumiesz, dlaczego sortowanie danych jest przydatne, ale musisz to zrozumieć po części poświęconej optymalizacji zapytań. Co więcej, zrozumienie sortowania przez scalanie pomoże nam później zrozumieć ogólną operację łączenia baz danych, zwaną merge join (łączenie przez scalanie).

Merge (scalanie)

Jak wiele użytecznych algorytmów, sortowanie przez scalanie opiera się na sprytnym pomyśle: scalanie 2 posortowanych tablic o wielkości N / 2 w posortowaną tablicę o N elementach wymaga tylko N operacji. Ta operacja nazywa się scalaniem.

Zobaczmy, co to oznacza na prostym przykładzie:

Na tym rysunku widać, że aby zbudować końcową posortowaną tablicę z 8 elementów, trzeba wykonać tylko jedną iterację w 2x 4-elementowych tablicach. Ponieważ obie tablice 4-elementowe są już posortowane:

1) porównujesz oba bieżące elementy w dwóch tablicach (na początku obecny = pierwszemu)
2) następnie weź najmniejszy, aby umieścić go w tablicy z 8 elementami
3) a następnie przejdź do następnego elementu w tablicy, gdzie wziąłeś najmniejszy element
i powtarzaj 1,2,3, aż dojdziesz do ostatniego elementu jednej z tablic.
Następnie bierzesz pozostałe elementy drugiej tablicy, aby umieścić je w tablicy z 8 elementami.

To działa, ponieważ oba 4-elementowe tablice są posortowane, więc nie musisz 'wracać' w tych tablicach.

Teraz, gdy zrozumieliśmy ten trik, oto mój pseudokod na merge:

array mergeSort(array a)
   if(length(a)==1)
      return a[0];
   end if

   //wywołania rekurencyjne
   [left_array right_array] := split_into_2_equally_sized_arrays(a);
   array new_left_array := mergeSort(left_array);
   array new_right_array := mergeSort(right_array);

   //łączenie 2 małych posortowanych tablic w jedną dużą
   array result := merge(new_left_array,new_right_array);
   return result;

Sortowanie przez scalanie dzieli zadanie na mniejsze zadania, a następnie znajduje wyniki mniejszych zadań, aby uzyskać wynik zadania wyjściowego (uwaga: ten typ algorytmu nazywa się dziel i rządź). Jeśli nie rozumiesz tego algorytmu, nie martw się; ja też nie zrozumiałem tego za pierwszym razem, gdy to zobaczyłem. Jeśli to może ci pomóc, widzę ten algorytm jako algorytm dwufazowy:

Faza dzielenia, gdzie tablica jest dzielona na mniejsze tablice
Faza sortowania, gdzie małe tablice są łączone (używając scalania), aby utworzyć większą tablicę.

Faza dzielenia (Division phase)

Na etapie dzielenia tablica jest dzielona na jedynkowe tablice w 3 krokach. Formalna liczba kroków to log(N) (ponieważ N=8, log(N) = 3).

Skąd to wiem?

Jestem geniuszem! Krótko mówiąc — matematyka. Idea polega na tym, że każdy krok dzieli rozmiar oryginalnej tablicy na 2. Liczba kroków to liczba razy, które możesz podzielić oryginalną tablicę na dwa. To dokładne określenie logarytmu (o podstawie 2).

Faza sortowania (Sorting phase)

Na etapie sortowania zaczynasz od jedynkowych (jednoelementowych) tablic. W ciągu każdego etapu stosujesz kilka operacji scalania, a całkowity koszt wynosi N = 8 operacji:

Na pierwszym etapie masz 4 scalania, które kosztują 2 operacje każde
Na drugim kroku masz 2 scalania, które kosztują 4 operacje każde
Na trzecim kroku masz 1 scalanie, które kosztuje 8 operacji

Ponieważ istnieje log(N) kroków, całkowity koszt N * log(N) operacji.

Zalety sortowania przez scalanie

Dlaczego ten algorytm jest tak potężny?

Ponieważ:

Możesz go zmienić, aby zmniejszyć zużycie pamięci, tak aby nie tworzyć nowych tablic, a bezpośrednio modyfikować tablicę wejściową.

Uwaga: ten typ algorytmów nazywa się in—place (sortowanie bez dodatkowej pamięci).

Możesz go zmienić, aby równocześnie używać przestrzeni dyskowej i niewielkiej ilości pamięci bez znacznych kosztów operacji dyskowych. Idea polega na ładowaniu do pamięci tylko tych części, które aktualnie są przetwarzane. Jest to ważne, gdy musisz posortować tabelę o rozmiarze kilku gigabajtów z buforem pamięci wynoszącym tylko 100 megabajtów.

Uwaga: ten typ algorytmów nazywa się sortowanie zewnętrzne.

Możesz go zmienić, aby działał na wielu procesach / wątkach / serwerach.

Na przykład, sortowanie rozdzielcze przy pomocy scalania jest jednym z kluczowych komponentów Hadoop (który jest strukturą w Big Data).

Ten algorytm może zamienić ołów w złoto (to prawda!).

Ten algorytm sortowania jest używany w większości (jeśli nie we wszystkich) bazach danych, ale nie jest jedynym. Jeśli chcesz dowiedzieć się więcej, możesz przeczytać tę pracę badawczą, która omawia zalety i wady powszechnych algorytmów sortowania w bazach danych.

Tablica, Drzewo i Tablica haszowa

Teraz, gdy rozumiemy ideę złożoności czasowej i sortowania, muszę opowiedzieć ci o 3 strukturach danych. To ważne, ponieważ one stanowią podstawę nowoczesnych baz danych. Wprowadzę też pojęcie indeksu bazy danych.

Tablica

Tablica dwuwymiarowa to najprostsza struktura danych. Tabelę można traktować jako tablicę. Na przykład:

Ta tablica 2-wymiarowa przedstawia tabelę z wierszami i kolumnami:

Każdy wiersz reprezentuje byt.
Kolumny przechowują właściwości opisujące byt.
Każda kolumna przechowuje dane określonego typu (całkowity, ciąg, data …).

To bardzo wygodne do przechowywania i wizualizacji danych, jednak gdy potrzebujesz znaleźć określoną wartość, nie jest to odpowiednie.

Na przykład, jeśli chcesz znaleźć wszystkich facetów, którzy pracują w Wielkiej Brytanii, musisz przejrzeć każdy wiersz, aby określić, czy ten wiersz należy do Wielkiej Brytanii. Będzie to kosztować N operacji, gdzie N — liczba wierszy jest niezła, ale czy jest szybsza droga? Teraz nadszedł czas, aby zapoznać się z drzewami.

Uwaga: większość nowoczesnych baz danych oferuje zaawansowane tablice do efektywnego przechowywania danych: tabele zorganizowane w kopcu i tabele zorganizowane w indeksie. To jednak nie rozwiązuje problemu szybkiego wyszukiwania określonego warunku w grupie kolumn.

Drzewo i indeks bazy danych

Drzewo binarne wyszukiwania to drzewo binarne z specjalną właściwością, klucz w każdym węźle musi być:

większy niż wszystkie klucze przechowywane w lewym poddrzewie
mniejszy niż wszystkie klucze przechowywane w prawym poddrzewie

Zobaczmy, co to oznacza wizualnie

Idea

To drzewo ma N = 15 elementów. Powiedzmy, że szukam 208:

Zaczynam od korzenia, którego klucz to 136. Ponieważ 136<208, patrzę na prawe poddrzewo węzła 136.
398>208, więc patrzę na lewe poddrzewo węzła 398
250>208, więc patrzę na lewe poddrzewo węzła 250
200<208, więc patrzę na prawe poddrzewo węzła 200. Ale 200 nie ma prawego poddrzewa, wartość nie istnieje (ponieważ, gdyby istniała, byłaby w prawym poddrzewie 200).

Teraz powiedzmy, że szukam 40

Zaczynam od korzenia, którego klucz to 136. Ponieważ 136 > 40, patrzę na lewe poddrzewo węzła 136.
80 > 40, więc patrzę na lewe poddrzewo węzła 80
40= 40, węzeł istnieje. Wydobywam identyfikator wiersza z węzła (tego nie ma na rysunku) i sprawdzam w tabeli dla danego identyfikatora wiersza.
Znajomość identyfikatora wiersza pozwala mi dowiedzieć się, gdzie dokładnie znajdują się dane w tabeli, dlatego mogę je uzyskać natychmiast.

Ostatecznie oba wyszukiwania kosztują mnie liczbę poziomów w drzewie. Jeśli uważnie przeczytałeś część o sortowaniu przez scalanie, powinieneś zauważyć, że jest tu log (N) poziomów. Zatem, koszt wyszukiwania log(N), nieźle!

Wracamy do naszego problemu

Ale to jest bardzo abstrakcyjne, więc wróćmy do naszego problemu. Zamiast prostego liczby całkowitej, wyobraź sobie ciąg, który reprezentuje kraj kogoś w poprzedniej tabeli. Załóżmy, że masz drzewo, które zawiera pole "country" (kolumna 3) tabeli:

Jeśli chcesz wiedzieć, kto pracuje w Wielkiej Brytanii
patrzysz na drzewo, aby uzyskać węzeł, który reprezentuje Wielką Brytanię
wewnątrz "UKnode" znajdziesz lokalizację pracowników w Wielkiej Brytanii.

To w wyszukiwaniu będzie kosztować log(N) operacji zamiast N, jeśli będziesz bezpośrednio używać tablicy. To, co właśnie przedstawiłeś – to było indeks bazy danych.

Możesz zbudować drzewo indeksowe dla dowolnej grupy pól (ciąg, liczba, 2 ciągi, liczba i ciąg, data…) pod warunkiem, że masz funkcję do porównywania kluczy (tzn. grup pól), aby móc ustalić kolejność kluczy (co ma miejsce dla wszystkich podstawowych typów w bazie danych).

B+DrzewoIndeksowe

Chociaż to drzewo dobrze działa dla uzyskania określonej wartości, istnieje DUŻY problem, gdy musisz uzyskać kilka elementów pomiędzy dwoma wartościami. Będzie to kosztować O(N), ponieważ musisz sprawdzić każdy węzeł w drzewie i sprawdzić, czy znajduje się pomiędzy tymi dwoma wartościami (na przykład, przy uporządkowanej traversji drzewa). Co więcej, ta operacja nie jest wygodna dla wejścia-wyjścia na dysku, ponieważ musisz odczytać całe drzewo. Musimy znaleźć sposób na skuteczne wykonanie zapytania o zakres. Aby rozwiązać ten problem, nowoczesne bazy danych używają zmodyfikowanej wersji poprzedniego drzewa, zwanej B+Tree. W drzewie B+Tree:

tylko najniższe węzły (liście) przechowują informacje (lokalizacja wierszy w powiązanej tabeli)
pozostałe węzły są tutaj do routingu do odpowiedniego węzła podczas wyszukiwania.

Jak możesz zobaczyć, tutaj węzłów jest więcej (dwukrotnie). Faktycznie, masz dodatkowe węzły, „węzły decyzyjne”, które pomogą Ci znaleźć odpowiedni węzeł (który przechowuje lokalizację wierszy w powiązanej tabeli). Ale złożoność wyszukiwania wciąż wynosi O(log(N)) (jest tylko jeden dodatkowy poziom). Duża różnica polega na tym, że węzły na dolnym poziomie są powiązane z ich następcami.

Z tym B+Tree, jeśli szukasz wartości od 40 do 100:

Musisz tylko szukać 40 (lub najbliższej wartości po 40, jeśli 40 nie istnieje), tak jak zrobiłeś to w poprzednim drzewie.
Następnie zbierz następców 40, używając bezpośrednich odniesień do następców, aż osiągniesz 100.

Załóżmy, że znalazłeś M następców, a drzewo ma N węzłów. Wyszukiwanie konkretnego węzła kosztuje log(N) podobnie jak w poprzednim drzewie. Ale uzyskując ten węzeł, otrzymujesz M następców w M operacjach z odniesieniami do ich następców. To wyszukiwanie kosztuje tylko M+log(N) operacji w porównaniu do N operacji w poprzednim drzewie. Co więcej, nie musisz przeglądać całego drzewa (tylko M + log (N) węzłów), co oznacza mniejsze wykorzystanie dysku. Jeśli M jest małe (np. 200 wierszy) a N duże (1 000 000 wierszy), to będzie DUŻA różnica.

Ale tutaj pojawiają się nowe problemy (znowu!). Jeśli dodasz lub usuniesz wiersz w bazie danych (a zatem w powiązanym indeksie B+Tree):

musisz utrzymać porządek pomiędzy węzłami wewnątrz drzewa B+Tree, w przeciwnym razie nie będziesz mógł znaleźć węzłów w nieposortowanym drzewie.
musisz zachować minimalną możliwą liczbę poziomów w B+Tree, w przeciwnym razie złożoność czasowa w O (log (N)) stanie się O (N).

Innymi słowy, B+Tree musi być samordynujące i zrównoważone. Na szczęście jest to możliwe dzięki sprytnym operacjom usuwania i wstawiania. Ale to jest kosztowne: wstawienie i usunięcie w drzewie B+ kosztuje O (log (N)). Dlatego niektórzy z was słyszeli, że używanie zbyt dużej liczby indeksów nie jest najlepszym pomysłem. Rzeczywiście, spowalniasz szybkie wstawianie / aktualizację / usuwanie wiersza w tabeli, ponieważ baza danych musi zaktualizować indeksy tabeli kosztowną operacją O (log (N)) dla każdego indeksu. Co więcej, dodanie indeksów oznacza większe obciążenie dla menedżera transakcji (będzie opisany na końcu artykułu).

Aby uzyskać więcej informacji, możesz zajrzeć do artykułu na Wikipedii o B+Tree. Jeśli chcesz przykład implementacji B+Tree w bazie danych, spójrz ten artykuł i ten artykuł od czołowego dewelopera MySQL. Obaj koncentrują się na tym, jak InnoDB (silnik MySQL) obsługuje indeksy.

Uwaga: czytelnik powiedział mi, że z powodu niskopoziomowych optymalizacji drzewo B+ musi być całkowicie zrównoważone.

Hashtable (Tablica haszująca)

Nasza ostatnia ważna struktura danych to tablica haszująca. Jest bardzo przydatna, gdy potrzebujesz szybko wyszukiwać wartości. Co więcej, zrozumienie tablicy haszującej pomoże nam później zrozumieć ogólną operację łączenia z bazą danych, nazywaną złączeniem haszowym ( hash join). Ta struktura danych jest również używana przez bazę danych do przechowywania niektórych wewnętrznych rzeczy (np. tabela blokady lub bufor połączeń, zobaczymy obie te koncepcje później).

Tabela haszująca to struktura danych, która szybko znajduje element na podstawie jego klucza. Aby zbudować tabelę haszującą, musisz określić:

klucz dla twoich elementów
funkcję haszującą dla kluczy. Obliczone hasze kluczy wskazują lokalizację elementów (zwanych segmentami ).
funkcję porównania kluczy. Gdy znajdziesz odpowiedni segment, musisz znaleźć element, którego szukasz wewnątrz segmentu, używając tego porównania.

Prosty przykład

Przyjrzyjmy się prostemu przykładowi:

Ta tabela haszująca ma 10 segmentów. Ponieważ jestem leniwy, narysowałem tylko 5 segmentów, ale wiem, że jesteś mądry, więc pozwolę ci wyobrazić sobie 5 pozostałych samodzielnie. Użyłem funkcji haszującej modulo 10 klucza. Innymi słowy, zachowując tylko ostatnią cyfrę klucza elementu, aby znaleźć jego segment:

jeśli ostatnia cyfra to 0, element trafia do segmentu 0,
jeśli ostatnia cyfra to 1, element trafia do segmentu 1,
jeśli ostatnia cyfra to 2, element trafia do obszaru 2,
…

Funkcja porównania, którą użyłem, to po prostu równość między dwoma liczbami całkowitymi.

Załóżmy, że chcesz uzyskać element 78:

Tabela haszująca oblicza kod haszujący dla 78, który wynosi 8.
Tabela haszująca przeszukuje segment 8, a pierwszy element, który znajduje, to 78.
Zwraca ci element 78
Wyszukiwanie kosztuje tylko 2 operacje (jedna na obliczenie wartości funkcji haszującej, a druga na znalezienie elementu wewnątrz segmentu).

Teraz załóżmy, że chcesz uzyskać element 59:

Tabela haszująca oblicza kod haszujący dla 59, który wynosi 9.
Tabela haszująca przeszukuje w segmencie 9, a pierwszy znaleziony element to 99. Ponieważ 99!=59, element 99 nie jest poprawnym elementem.
Używając tej samej logiki, pobierany jest drugi element (9), trzeci (79), …, ostatni (29).
Element nie został znaleziony.
Wyszukiwanie kosztowało 7 operacji.

Dobra funkcja haszująca

Jak widzisz, w zależności od wartości, której szukasz, koszt nie jest taki sam!

Jeśli teraz zmienię funkcję haszującą na moduł 1 000 000 klucza (to znaczy biorąc ostatnie 6 cyfr), drugie wyszukiwanie będzie kosztować tylko 1 operację, ponieważ w segmencie 000059 nie ma elementów. Rzeczywisty problem to znalezienie dobrej funkcji haszującej, która tworzy segmenty zawierające bardzo niewielką liczbę elementów..

W moim przykładzie łatwo znaleźć dobrą funkcję haszującą. Ale to prosty przykład, znalezienie dobrej funkcji haszującej jest trudniejsze, gdy klucz:

ciąg (na przykład - nazwisko)
2 ciągi (na przykład - nazwisko i imię)
2 ciągi i data (na przykład - nazwisko, imię i data urodzenia)
…

Dzięki dobrej funkcji haszującej wyszukiwanie w tablicy haszującej odbywa się w O(1).

Tablica vs tablica haszująca

Dlaczego nie używać tablicy?

Hmmm, dobre pytanie.

Tablica haszująca może być częściowo załadowana w pamięci, a pozostałe segmenty mogą pozostawać na dysku.
Z tablicą musisz używać ciągłej przestrzeni w pamięci. Jeśli ładujesz dużą tabelę bardzo trudno znaleźć wystarczającą ciągłą przestrzeń.
Dla tablicy haszującej możesz wybrać odpowiedni klucz (na przykład kraj i nazwisko osoby).

Aby uzyskać dodatkowe informacje, możesz przeczytać artykuł o JavaHashMap, która jest efektywną implementacją tablicy haszującej; nie musisz rozumieć Javy, aby zrozumieć koncepcje przedstawione w tym artykule.

Źródło: habr.com