Samouczek struktury danych tabeli skrótu
Załóżmy, że jesteś właścicielem dużego sklepu z przepisami w hrabstwie, w którym mieszkasz. Załóżmy, że mieszkasz w dużym obszarze, który nie jest obszarem komercyjnym. Nie jesteś jedynym, który ma sklep rezerwowy w okolicy; Masz kilku konkurentów. A potem przychodzi ci to, że powinieneś zapisać numery telefonów swoich klientów w książce ćwiczeń. Oczywiście książka ćwiczeń jest niewielka i nie można zapisać wszystkich numerów telefonów dla wszystkich swoich klientów.
Dlatego decydujesz się na rejestrowanie tylko numerów telefonów stałych klientów. I masz tabelę z dwiema kolumnami. Kolumna po lewej ma nazwy klientów, a kolumna po prawej stronie ma odpowiednie numery telefonów. W ten sposób istnieje mapowanie między nazwami klientów a numerami telefonów. Prawą kolumnę tabeli można uznać za podstawową tabelę skrótów. Nazwy klientów są teraz nazywane klawiszami, a numery telefonów nazywane są wartościami. Zauważ, że kiedy klient przejdzie do transferu, będziesz musiał anulować jego wiersz, umożliwiając opróżnianie wiersza lub zastąpienie nowemu regularnemu klientowi. Zauważ również, że z czasem liczba zwykłych klientów może zwiększyć lub zmniejszyć się, a więc stół może rosnąć lub kurczyć się.
Jako kolejny przykład mapowania, załóżmy, że w hrabstwie jest klub rolników. Oczywiście nie wszyscy rolnicy będą członkami klubu. Niektórzy członkowie klubu nie będą zwykłymi członkami (obecni i wkładu). Bar-Man może zdecydować o zapisaniu nazwisk członków i wyboru drinka. Opracowuje tabelę dwóch kolumn. W lewej kolumnie pisze nazwiska członków klubu. W prawej kolumnie pisze odpowiedni wybór napoju.
Jest tutaj problem: w prawej kolumnie są duplikaty. To znaczy ta sama nazwa drinka znajduje się więcej niż raz. Innymi słowy, różni członkowie piją ten sam słodki napój lub ten sam napój alkoholiczny, podczas gdy inni członkowie piją inny napój słodki lub alkoholowy. Bar-Man decyduje się rozwiązać ten problem, wkładając wąską kolumnę między dwiema kolumnami. W tej środkowej kolumnie, zaczynając od góry, liczy rzędy od zera (i.mi. 0, 1, 2, 3, 4 itp.), Zejście, jeden indeks na rząd. Dzięki temu jego problem jest rozwiązany, ponieważ nazwa członka mapuje teraz indeks, a nie do nazwy drinka. Tak więc, ponieważ napój jest identyfikowany przez indeks, nazwa klienta jest mapowana na odpowiedni indeks.
Sama kolumna wartości (napojów) tworzy podstawową tabelę skrótów. W tabeli zmodyfikowanej kolumna wskaźników i powiązane z nimi wartości (z duplikatami lub bez) tworzą normalną tabelę skrótów - pełna definicja tabeli skrótów podano poniżej. Klucze (pierwsza kolumna) niekoniecznie stanowią część tabeli skrótów.
Jako kolejny przykład, rozważ serwer sieciowy, w którym użytkownik z jego komputera klienta może dodać informacje, usunąć niektóre informacje lub zmodyfikować niektóre informacje. Jest wielu użytkowników serwera. Każda nazwa użytkownika odpowiada hasłem przechowywanym na serwerze. Ci, którzy utrzymują serwer, mogą zobaczyć nazwy użytkowników i odpowiednie hasło, a zatem móc uszkodzić pracę użytkowników.
Więc właściciel serwera postanawia stworzyć funkcję, która szyfruje hasło przed jego przechowywaniem. Użytkownik loguje się na serwerze, z jego normalnym rozumianym hasłem. Jednak teraz każde hasło jest przechowywane w zaszyfrowanej formie. Jeśli ktokolwiek widzi zaszyfrowane hasło i próbuje go zalogować, nie zadziała, ponieważ logowanie się, otrzymuje rozumiane hasło przez serwer, a nie zaszyfrowane hasło.
W takim przypadku hasło rozumiane jest kluczem, a zaszyfrowane hasło jest wartością. Jeśli zaszyfrowane hasło znajduje się w kolumnie zaszyfrowanych haseł, to ta kolumna jest podstawową tabelą skrótów. Jeśli ta kolumna jest poprzedzona inną kolumną z indeksami zaczynającymi się od zera, aby każde zaszyfrowane hasło jest powiązane z indeksem, zarówno kolumna indeksów, jak i szyfrowane hasło, uformuj normalną tabelę skrótów. Klucze niekoniecznie są częścią tabeli hasz.
Zwróć uwagę na to, że każdy klucz, który jest hasłem rozumianym, odpowiada nazwie użytkownika. Istnieje więc nazwa użytkownika, która odpowiada kluczowi odwzorowanemu na indeks, który jest powiązany z wartością, która jest zaszyfrowanym kluczem.
Definicja funkcji skrótu, pełna definicja tabeli skrótów, znaczenie tablicy i inne szczegóły podano poniżej. Musisz mieć wiedzę na temat wskaźników (referencje) i powiązanych list, aby docenić resztę tego samouczka.
Znaczenie funkcji skrótu i tabeli skrótów
Szyk
Tablica to zestaw kolejnych lokalizacji pamięci. Wszystkie lokalizacje są tego samego rozmiaru. Wartość w pierwszej lokalizacji jest dostępna z indeksem, 0; Wartość w drugiej lokalizacji jest dostępna z indeksem, 1; Trzecia wartość jest dostępna z indeksem, 2; czwarte z indeksem, 3; i tak dalej. Tablica zwykle nie może się zwiększyć ani kurczyć. Aby zmienić rozmiar (długość) tablicy, należy utworzyć nową tablicę, a odpowiednie wartości skopiowane do nowej tablicy. Wartości tablicy są zawsze tego samego typu.
Funkcja HASH
W oprogramowaniu funkcja skrótu jest funkcją, która przyjmuje klucz i tworzy odpowiedni wskaźnik dla komórki tablicy. Tablica ma stały rozmiar (stała długość). Liczba kluczy ma dowolną wielkość, zwykle większą niż wielkość tablicy. Indeks wynikający z funkcji skrótu nazywa się wartością skrótu lub trawieniem lub kodem skrótu lub po prostu skrótu.
Tabela hash
Tabela skrótu jest tablicą z wartościami, do których wskaźników, klucze są odwzorowane. Klucze są pośrednio mapowane na wartości. W rzeczywistości mówi się, że klucze są odwzorowane na wartości, ponieważ każdy indeks jest powiązany z wartością (z duplikatami lub bez). Jednak funkcja, która ma mapowanie (i.mi. mieszanie) odnosi klucze do wskaźników tablicy i nie do wartości, ponieważ mogą istnieć duplikaty wartości. Poniższy schemat ilustruje tabelę skrótów dla nazwisk ludzi i ich numerów telefonów. Komórki macierzy (szczeliny) nazywane są wiadrami.
Zauważ, że niektóre wiadra są puste. Tabela skrótów niekoniecznie może mieć wartości we wszystkich swoich wiadrach. Wartości w wiadrach niekoniecznie muszą być w kolejności rosnącej. Jednak wskaźniki, z którymi są powiązane, są w kolejności rosnącej. Strzałki wskazują mapowanie. Zauważ, że klucze nie są w tablicy. Nie muszą być w żadnej strukturze. Funkcja skrótu przyjmuje dowolny klucz i wymyśla indeks dla tablicy. Jeśli nie ma wartości w wiadrze powiązanym z indeksem, w tym wiadrze można wprowadzić nową wartość. Zależność logiczna jest między kluczem a indeksem, a nie między kluczem a wartością powiązaną z indeksem.
Wartości tablicy, podobnie jak ta z tej tabeli skrótów, są zawsze tego samego typu danych. Tabela skrótów (wiadra) może łączyć klucze z wartościami różnych typów danych. W takim przypadku wszystkie wartości tablicy są wskaźnikami, wskazującymi na różne typy wartości.
Tabela skrótów to tablica z funkcją skrótu. Funkcja przyjmuje klucz i skróty odpowiedni wskaźnik, a zatem łączy klucze z wartościami, w tablicy. Klucze nie muszą być częścią tabeli skrótów.
Dlaczego tablica i nie połączona lista dla tabeli HASH
Tablicę tabeli skrótów można zastąpić podłączoną strukturą danych listy, ale byłby problem. Pierwszy element połączonej listy jest naturalnie na indeksie, 0; Drugi element jest naturalnie na indeksie, 1; Trzeci jest naturalnie na indeksie, 2; i tak dalej. Problem z powiązaną listą polega na tym, że aby odzyskać wartość, lista musi zostać iterowana, a to wymaga czasu. Dostęp do wartości w tablicy odbywa się po losowym dostępie. Po znaniu indeksu wartość jest uzyskiwana bez iteracji; Ten dostęp jest szybszy.
Kolizja
Funkcja skrótu przyjmuje klucz i skróty odpowiedni wskaźnik, czytanie powiązanej wartości lub wstawienie nowej wartości. Jeśli celem jest odczytanie wartości, jak dotąd nie ma problemu (bez problemu). Jeśli jednak celem jest wstawienie wartości, indeks osłonowy może już mieć powiązaną wartość i to jest kolizja; Nowej wartości nie można umieścić tam, gdzie jest już wartość. Istnieją sposoby rozwiązania zderzenia - patrz poniżej.
Dlaczego pojawia się zderzenie
W powyższym przykładzie sklepu z przepisami nazwy klientów to klucze, a nazwy napojów są wartościami. Zauważ, że klienci są zbyt wielu, podczas gdy tablica ma ograniczony rozmiar i nie może zabrać wszystkich klientów. Tak więc w tablicy są przechowywane tylko napoje stałych klientów. Zderzenie nastąpiłaby, gdy klient nieregularny staje się regularny. Klienci do sklepu tworzą duży zestaw, a liczba wiader dla klientów w tablicy jest ograniczona.
Z tabelami skrótu, są to wartości dla kluczy, które są bardzo prawdopodobne, rejestrowane są. Kiedy klucz, który nie był prawdopodobny, staje się prawdopodobny, prawdopodobnie nastąpi kolizja. W rzeczywistości kolizja zawsze występuje z tabelami skrótów.
Podstawy rozwiązywania zderzeń
Dwa podejścia do rozdzielczości kolizji nazywane są osobnym łączeniem i otwarciem adresowania. Teoretycznie klucze nie powinny znajdować się w strukturze danych lub nie powinny być częścią tabeli skrótów. Jednak oba podejścia wymagają, aby kluczowa kolumna poprzedzała tabelę skrótów i stała się częścią ogólnej struktury. Zamiast kluczy w kolumnie kluczy, wskaźniki do kluczy mogą znajdować się w kolumnie kluczy.
Praktyczna tabela skrótów zawiera kolumnę klawiszy, ale ta kolumna kluczowa nie jest oficjalnie częścią tabeli skrótów.
Każde podejście do rozwiązywania może mieć puste wiadra, niekoniecznie na końcu tablicy.
Oddzielne łączenie
W oddzielnym łączeniu, gdy nastąpi kolizja, nowa wartość jest dodawana w prawo (nie powyżej lub poniżej) kolidowanej wartości. Tak więc dwie lub trzy wartości mają ten sam indeks. Rzadko więcej niż trzy powinny mieć ten sam indeks.
Czy więcej niż jedna wartość może naprawdę mieć ten sam indeks w tablicy? - NIE. Tak więc w wielu przypadkach pierwszą wartością dla indeksu jest wskaźnik do połączonej struktury danych, która zawiera jedną, dwie lub trzy zderzone wartości. Poniższy schemat jest przykładem tabeli skrótu do osobnego łączenia klientów i ich numerów telefonów:
Puste wiadra są oznaczone literą x. Reszta automatów ma wskazówki do powiązanych list. Każdy element połączonej listy ma dwa pola danych: jeden dla nazwy klienta, a drugi dla numeru telefonu. Konflikt występuje w przypadku kluczy: Peter Jones i Suzan Lee. Odpowiednie wartości składają się z dwóch elementów jednej połączonej listy.
W przypadku sprzecznych kluczy kryterium wstawienia wartości jest tym samym kryterium, które używa się do zlokalizowania (i odczytu) wartości.
Otwarte adresowanie
Z otwartym adresem wszystkie wartości są przechowywane w tablicy wiadra. Gdy wystąpi konflikt, nowa wartość jest wstawiana do pustego wiadra Nowa odpowiednia wartość konfliktu, zgodnie z pewnym kryterium. Kryterium użyte do wstawienia wartości w konflikcie jest tym samym kryterium użytym do zlokalizowania (wyszukiwania i odczytania) wartości.
Poniższy schemat ilustruje rozdzielczość konfliktu z otwartym adresem:
Funkcja skrótu bierze klucz, Peter Jones i Hashes indeks 152 i przechowuje swój numer telefonu w powiązanym wiadrze. Po pewnym czasie funkcja skrótu ma ten sam wskaźnik, 152 z klucza, Suzan Lee, zderzając się z indeksem dla Petera Jonesa. Aby to rozwiązać, wartość Suzan Lee jest przechowywana w wiadrze następnego indeksu, 153, który był pusty. Funkcja skrótu ma indeks, 153 dla klucza, Robin Hood, ale ten indeks został już użyty do rozwiązania konfliktu dla poprzedniego klucza. Tak więc wartość Robin Hood jest umieszczona w następnym pustym wiadrze, którym jest wartość indeksu 154.
Metody rozwiązywania konfliktów dla oddzielnego łączenia i otwarcia adresowania
Oddzielne łączenie ma swoje metody rozwiązywania konfliktów, a otwarte adresowanie ma również własne metody rozwiązywania konfliktów.
Metody rozwiązywania osobnych konfliktów łączenia
Metody oddzielnych tabel skrótów łączącej są teraz krótko wyjaśnione:
Oddzielne łączenie z powiązanymi listami
Ta metoda jest jak wyjaśniona powyżej. Jednak każdy element połączonej listy niekoniecznie może mieć pole kluczowe (e.G. Pole Nazwa klienta powyżej).
Oddzielne łączenie z komórek głównych listy
W tej metodzie pierwszy element listy połączonej jest przechowywany w wiadrze tablicy. Jest to możliwe, jeśli typ danych dla tablicy jest elementem połączonej listy.
Oddzielne łączenie z innymi strukturami
Każda inna struktura danych, taka jak samodzielne binarne drzewo wyszukiwania, które obsługuje wymagane operacje, można użyć zamiast linkowanej listy - patrz później.
Metody rozwiązywania otwartych konfliktów
Metoda rozwiązywania konfliktów w otwartym adresie nazywa się sekwencją sondy. Teraz wyjaśniono trzy znane sekwencje sondy:
Sondowanie liniowe
W przypadku sondowania liniowego, gdy wystąpi konflikt, szukano najbliższego pustego wiadra poniżej wiadra w konflikcie. Ponadto, w przypadku sondowania liniowego, zarówno klucz, jak i jego wartość są przechowywane w tym samym wiadrze.
Sondowanie kwadratowe
Załóżmy, że konflikt ma miejsce w indeksie H. Następne puste gniazdo (wiadro) w indeksie H + 12 Jest używane; Jeśli jest to już zajęte, to następny pusty przy H + 22 jest używany, jeśli jest to już zajęte, wówczas następny pusty przy H + 32 jest używany i tak dalej. Są do tego warianty.
Podwójne mieszanie
W przypadku podwójnego mieszania istnieją dwie funkcje skrótu. Pierwszy oblicza (skróty) indeks. Jeśli wystąpi konflikt, drugi używa tego samego klucza, aby ustalić, jak daleko należy włożyć wartość. Jest w tym coś więcej - patrz później.
Idealna funkcja skrótu
Idealna funkcja skrótu jest funkcją skrótu, która nie może spowodować żadnego zderzenia. Może się to zdarzyć, gdy zestaw klawiszy jest stosunkowo mały, a każdy klucz mapuje się na konkretną liczbę całkowitą w tabeli skrótów.
W zestawie znaków ASCII znaki górnego obudowy można zmapować na odpowiadające im dolne litery za pomocą funkcji skrótu. Litery są reprezentowane w pamięci komputera jako liczby. W zestawie znaków ASCII A wynosi 65, B wynosi 66, C to 67 itp. a a to 97, b wynosi 98, c to 99 itp. Do mapowania od A do A, dodaj 32 do 65; do mapy od B do B, dodaj 32 do 66; Aby mapować od C do C, dodaj 32 do 67; i tak dalej. Tutaj górne litery to klawisze, a dolne litery obudowy są wartościami. Tabela skrótu dla tego może być tablicą, której wartości to powiązane wskaźniki. Pamiętaj, że wiadra tablicy mogą być puste. Więc wiadra w tablicy od 64 do 0 mogą być puste. Funkcja skrótu po prostu dodaje 32 do górnego numeru kodu kodu, aby uzyskać indeks, a zatem litera dolnej skrzynki. Taka funkcja jest idealną funkcją skrótu.
Mieszanie od liczby całkowitej do wskaźników liczb całkowitych
Istnieją różne metody mieszania liczby całkowitej. Jeden z nich nazywa się metodą podziału modulo (funkcja).
Funkcja mieszania podziału modulo
Funkcja oprogramowania komputerowego nie jest funkcją matematyczną. W obliczeniach (oprogramowaniu) funkcja składa się z zestawu stwierdzeń poprzedzonych argumentami. W przypadku funkcji podziału modulo klucze są liczbami całkowite i są odwzorowane na wskaźniki tablicy wiader. Zestaw kluczy jest duży, więc tylko klucze, które mogą wystąpić w aktywności, zostałyby zmapowane. Więc zderzenia występują, gdy należy zmapować mało prawdopodobne klucze.
W oświadczeniu,
20 /6 = 3R2
20 to dywidenda, 6 to dzielnik, a 3 pozostałe 2 to iloraz. Pozostała część 2 nazywa się również modulo. Uwaga: Możliwe jest posiadanie modulo 0.
W przypadku tego haszu rozmiar tabeli jest zwykle mocą 2, e.G. 64 = 26 lub 256 = 28, itp. Dzielnik tej funkcji mieszania jest liczbą pierwszą zbliżoną do rozmiaru tablicy. Ta funkcja dzieli klucz przez dzielnika i zwraca modulo. Modulo jest wskaźnikiem tablicy wiader. Powiązana wartość w wiadrze jest wartością wybraną (wartość dla klucza).
Klawisze o zmiennej długości mieszania
Tutaj klucze z zestawu są teksty o różnych długościach. Różne liczby całkowite można przechowywać w pamięci za pomocą tej samej liczby bajtów (rozmiar postaci angielskiej to bajt). Kiedy różne klucze są o różnych rozmiarach bajtów, mówi się, że mają zmienną długość. Jedna z metod do haszowania zmiennych długości nazywa się mieszanie konwersji Radix.
Haszowanie konwersji Radix
W ciągu każdego znaku na komputerze jest liczbą. W tej metodzie,
Kod skrótu (indeks) = x0AK -1+X1AK -2+… +XK -2A1+XK -1A0
Gdzie (x0, x1,…, xk -.G. 29 (patrz później). K to liczba znaków w ciągu. Jest w tym coś więcej - patrz później.
Klucze i wartości
W pary klucza/wartości wartością niekoniecznie może być liczba lub tekst. To może być również rekord. Płyta to lista napisana w poziomie. W pary klucza/wartości każdy klucz może faktycznie odnosić się do innego tekstu lub liczby lub rekordów.
Tablica asocjacyjna
Lista to struktura danych, w której elementy listy są powiązane, a na liście znajduje się zestaw operacji. Każda lista może składać się z pary elementów. Ogólna tabela skrótów z jego klawiszami można uznać za strukturę danych, ale jest to bardziej system niż struktura danych. Klucze i ich odpowiednie wartości nie są od siebie zależne. Nie są ze sobą zbyt powiązane.
Z drugiej strony tablica asocjacyjna jest podobną rzeczą, ale klucze i ich wartości są od siebie bardzo zależne; Są bardzo ze sobą powiązane. Na przykład możesz mieć asocjacyjny zestaw owoców i ich kolorów. Każdy owoc ma naturalnie swój kolor. Nazwa owocu jest kluczem; Kolor to wartość. Podczas wstawienia każdy klucz jest wstawiany do swojej wartości. Podczas usunięcia każdy klucz jest usuwany z jego wartości.
Tablica asocjacyjna to struktura danych tabeli skrótu złożonej z par kluczy/wartości, w której nie ma duplikatu dla klawiszy. Wartości mogą mieć duplikaty. W tej sytuacji klucze są częścią struktury. Oznacza to, że klucze muszą być przechowywane, podczas gdy przy stole ogólnym Hast klucze nie muszą być przechowywane. Problem zduplikowanych wartości jest naturalnie rozwiązywany przez wskaźniki tablicy wiader. Nie myl między zduplikowanymi wartościami a zderzeniem przy indeksie.
Ponieważ tablica asocjacyjna jest strukturą danych, ma przynajmniej następujące operacje:
Operacje tablic asocjacyjnych
Wstaw lub dodaj
To wprowadza nową parę klucza/wartości do kolekcji, mapując klucz do jej wartości.
ponowne złożenie
Ta operacja zastępuje wartość konkretnego klucza do nowej wartości.
usunąć lub usuń
To usuwa klucz plus jego odpowiednia wartość.
spojrzeć w górę
Ta operacja wyszukuje wartość konkretnego klucza i zwraca wartość (bez jej usuwania).
Wniosek
Struktura danych tabeli skrótów składa się z tablicy i funkcji. Funkcja nazywa się funkcją skrótu. Funkcja mapuje klucze do wartości w tablicy przez wskaźniki tablicy. Klucze niekoniecznie muszą być częścią struktury danych. Zestaw kluczy jest zwykle większy niż wartości przechowywane. Gdy nastąpi kolizja, jest ona rozwiązywana przez oddzielne podejście do łączenia lub podejście do otwartego adresowania. Tablica asocjacyjna jest szczególnym przypadkiem struktury danych tabeli skrótu.