Phenquestions
Załóżmy, że jesteś właścicielem dużego sklepu z prowiantem w hrabstwie, w którym mieszkasz. Załóżmy, że mieszkasz na dużym obszarze, który nie jest obszarem komercyjnym. Nie jesteś jedyną osobą, która ma w okolicy sklep z prowiantem; masz kilku konkurentów. A potem przychodzi ci do głowy, że powinieneś zapisać numery telefonów swoich klientów w zeszycie. Oczywiście zeszyt jest mały i nie można zapisać wszystkich numerów telefonów dla wszystkich klientów.
Postanawiasz więc nagrywać tylko numery telefonów swoich stałych klientów. A więc masz stół z dwiema kolumnami. Kolumna po lewej stronie zawiera nazwiska klientów, a kolumna po prawej 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ę mieszającą. Nazwy klientów są teraz nazywane kluczami, a numery telefonów nazywane są wartościami. Zwróć uwagę, że gdy klient przejdzie na transfer, będziesz musiał anulować jego wiersz, pozwalając na jego opróżnienie lub zastąpienie go nowym stałym klientem. Pamiętaj też, że z czasem liczba stałych klientów może się zwiększać lub zmniejszać, a więc tabela może się powiększać lub zmniejszać.
Jako kolejny przykład mapowania załóżmy, że w hrabstwie istnieje klub rolników. Oczywiście nie wszyscy rolnicy będą członkami klubu. Niektórzy członkowie klubu nie będą stałymi członkami (w frekwencji i wkładzie). Barman może zdecydować się na zarejestrowanie nazwisk członków i ich wyboru napoju. Opracowuje tabelę dwóch kolumn. W lewej kolumnie wpisuje nazwiska członków klubu. W prawej kolumnie wpisuje odpowiedni wybór napoju.
Tu jest problem: w prawej kolumnie są duplikaty. Oznacza to, że ta sama nazwa napoju występuje więcej niż raz. Innymi słowy, różni członkowie piją ten sam słodki napój lub ten sam napój alkoholowy, podczas gdy inni członkowie piją inny słodki lub alkoholowy napój. Barman postanawia rozwiązać ten problem, wstawiając wąską kolumnę między dwie kolumny. W tej środkowej kolumnie, zaczynając od góry, numeruje wiersze zaczynając od zera (i.mi. 0, 1, 2, 3, 4 itd.), schodząc, jeden indeks w wierszu. Dzięki temu jego problem został rozwiązany, ponieważ nazwa członka jest teraz odwzorowywana na indeks, a nie na nazwę napoju. Tak więc, gdy napój jest identyfikowany przez indeks, nazwa klienta jest mapowana do odpowiedniego indeksu.
Sama kolumna wartości (napoje) tworzy podstawową tablicę haszującą. W zmodyfikowanej tabeli kolumna indeksów i skojarzone z nimi wartości (z duplikatami lub bez) tworzą normalną tablicę mieszającą - pełna definicja tablicy mieszającej znajduje się poniżej. Klucze (pierwsza kolumna) niekoniecznie stanowią część tablicy mieszającej.
Jako kolejny przykład rozważmy serwer sieciowy, na którym użytkownik ze swojego komputera klienckiego może dodać pewne informacje, usunąć niektóre informacje lub zmodyfikować niektóre informacje. Na serwerze jest wielu użytkowników. Każda nazwa użytkownika odpowiada hasłu przechowywanemu na serwerze. Ci, którzy zarządzają serwerem, mogą zobaczyć nazwy użytkowników i odpowiadające im hasła, a tym samym mogą uszkodzić pracę użytkowników.
Więc właściciel serwera decyduje się stworzyć funkcję, która szyfruje hasło przed jego zapisaniem. Użytkownik loguje się do serwera za pomocą swojego normalnego, zrozumiałego hasła. Jednak teraz każde hasło jest przechowywane w postaci zaszyfrowanej. Jeśli ktoś zobaczy zaszyfrowane hasło i spróbuje się z niego zalogować, to nie zadziała, ponieważ logując się, serwer otrzymuje zrozumiałe hasło, a nie zaszyfrowane hasło.
W tym przypadku zrozumiałe hasło 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, tak że każde zaszyfrowane hasło jest powiązane z indeksem, to zarówno kolumna indeksów, jak i kolumna zaszyfrowanego hasła tworzą normalną tablicę skrótów. Klucze niekoniecznie są częścią tablicy mieszającej.
Zauważ, że w tym przypadku każdy klucz, który jest zrozumiałym hasłem, odpowiada nazwie użytkownika. Tak więc istnieje nazwa użytkownika odpowiadająca kluczowi mapowanemu na indeks, który jest powiązany z wartością, która jest zaszyfrowanym kluczem.
Poniżej podano definicję funkcji mieszającej, pełną definicję tablicy mieszającej, znaczenie tablicy i inne szczegóły. Aby docenić resztę tego samouczka, musisz znać się na wskaźnikach (referencjach) i listach z linkami.
Znaczenie funkcji haszującej i tablicy haszującej
Szyk
Tablica to zbiór kolejnych lokalizacji w pamięci. Wszystkie lokalizacje mają ten sam rozmiar. Dostęp do wartości w pierwszej lokalizacji uzyskuje się za pomocą indeksu 0; wartość w drugiej lokalizacji jest odczytywana z indeksem, 1; trzecia wartość jest dostępna z indeksem, 2; czwarty z indeksem, 3; i tak dalej. Tablica nie może normalnie zwiększać się ani zmniejszać. Aby zmienić rozmiar (długość) tablicy, należy utworzyć nową tablicę, a odpowiednie wartości skopiować do nowej tablicy. Wartości tablicy są zawsze tego samego typu.
Funkcja skrótu
W oprogramowaniu funkcja skrótu to funkcja, która pobiera klucz i tworzy odpowiedni indeks dla komórki tablicy. Tablica ma stały rozmiar (stałą długość). Liczba kluczy ma dowolny rozmiar, zwykle większy niż rozmiar tablicy. Indeks wynikający z funkcji skrótu nazywa się wartością skrótu, skrótem, kodem skrótu lub po prostu haszem.
Tablica haszująca
Tablica mieszająca to tablica z wartościami, do których indeksów odwzorowywane są klucze. Klucze są pośrednio mapowane na wartości. W rzeczywistości mówi się, że klucze są mapowane na wartości, ponieważ każdy indeks jest powiązany z wartością (z duplikatami lub bez). Jednak funkcja, która wykonuje mapowanie (i.mi. haszowanie) wiąże klucze z indeksami tablicy, a nie z wartościami, ponieważ mogą występować duplikaty w wartościach. Poniższy diagram ilustruje tablicę mieszającą z nazwiskami osób i ich numerami telefonów. Komórki tablicy (sloty) nazywane są kubełkami.
Zauważ, że niektóre wiadra są puste. Tablica mieszająca niekoniecznie musi zawierać wartości we wszystkich swoich segmentach. Wartości w wiadrach niekoniecznie muszą być w porządku rosnącym. Jednak indeksy, z którymi są powiązane, są w porządku rosnącym. Strzałki wskazują mapowanie. Zauważ, że klucze nie znajdują się w tablicy. Nie muszą być w żadnej strukturze. Funkcja haszująca pobiera dowolny klucz i haszuje indeks tablicy. Jeśli nie ma wartości w wiadrze powiązanym z haszowanym indeksem, można w nim umieścić nową wartość. Logiczna relacja zachodzi między kluczem a indeksem, a nie między kluczem a wartością powiązaną z indeksem.
Wartości tablicy, podobnie jak te z tej tablicy mieszającej, są zawsze tego samego typu danych. Tablica mieszająca (wiadra) może łączyć klucze z wartościami różnych typów danych. W tym przypadku wartości tablicy są wskaźnikami, wskazującymi na różne typy wartości value.
Tablica mieszająca to tablica z funkcją mieszającą. Funkcja pobiera klucz i haszuje odpowiadający mu indeks, a więc łączy klucze z wartościami w tablicy. Klucze nie muszą być częścią tablicy mieszającej.
Dlaczego tablica, a nie połączona lista dla tablicy mieszającej
Tablicę dla tablicy mieszającej można zastąpić połączoną strukturą danych listy, ale byłby problem there. Pierwszy element listy połączonej znajduje się naturalnie pod indeksem, 0; drugi element jest naturalnie w indeksie, 1; trzeci jest naturalnie przy indeksie, 2; i tak dalej. Problem z połączoną listą polega na tym, że aby pobrać wartość, lista musi być iterowana, a to wymaga czasu. Dostęp do wartości w tablicy jest dostęp losowy is. Gdy indeks jest znany, wartość jest uzyskiwana bez iteracji; ten dostęp jest szybszy.
Kolizja
Funkcja haszująca pobiera klucz i haszuje odpowiedni indeks, aby odczytać powiązaną wartość lub wstawić nową wartość. Jeśli celem jest odczytanie wartości, na razie nie ma problemu (nie ma problemu). Jeśli jednak celem jest wstawienie wartości, indeks zaszyfrowany może już mieć skojarzoną wartość i jest to kolizja; nowa wartość nie może być umieszczona tam, gdzie już jest wartość. Istnieją sposoby na rozwiązanie kolizji - patrz poniżej.
Dlaczego dochodzi do kolizji
W powyższym przykładzie sklepu z prowiantem nazwy klientów są kluczami, a nazwy napojów są wartościami. Zauważ, że klientów jest zbyt wielu, a tablica ma ograniczony rozmiar i nie może przyjąć wszystkich klientów. Tak więc w tablicy przechowywane są tylko napoje stałych klientów. Kolizja miałaby miejsce, gdy nieregularny klient stałby się regularnym. Klienci dla sklepu tworzą duży zestaw, natomiast liczba wiader dla klientów w tablicy jest ograniczona.
W przypadku tablic mieszających zapisywane są wartości kluczy, które są bardzo prawdopodobne. Kiedy klucz, który nie był prawdopodobny, staje się prawdopodobny, prawdopodobnie dojdzie do kolizji. W rzeczywistości kolizja zawsze występuje z tablicami mieszającymi.
Podstawy rozwiązywania kolizji
Dwa podejścia do rozwiązywania kolizji są nazywane oddzielnymi łańcuchami i otwartym adresowaniem. Teoretycznie klucze nie powinny znajdować się w strukturze danych ani nie powinny być częścią tablicy mieszającej. Jednak oba podejścia wymagają, aby kolumna klucza poprzedzała tabelę mieszającą i stała się częścią ogólnej struktury. Zamiast kluczy znajdujących się w kolumnie kluczy, wskaźniki do kluczy mogą znajdować się w kolumnie kluczy.
Praktyczna tabela mieszająca zawiera kolumnę kluczy, ale ta kolumna kluczy nie jest oficjalnie częścią tabeli mieszającej.
Każde podejście do rozwiązania może mieć puste wiadra, niekoniecznie na końcu tablicy.
Oddzielne łączenie
W oddzielnym łańcuchowaniu, gdy wystąpi kolizja, nowa wartość jest dodawana po prawej stronie (nie powyżej ani poniżej) wartości kolizji. 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 mieć naprawdę ten sam indeks w tablicy?? - Nie. Tak więc w wielu przypadkach pierwsza wartość indeksu jest wskaźnikiem do połączonej struktury danych listy, która zawiera jedną, dwie lub trzy kolidujące wartości. Poniższy diagram jest przykładem tablicy mieszającej do oddzielnego łączenia klientów i ich numerów telefonów:
Puste wiadra oznaczone są literą x. Pozostałe sloty mają wskaźniki do połączonych list. Każdy element połączonej listy ma dwa pola danych: jedno na nazwę klienta, a drugie na numer telefonu. Konflikt o klucze: 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 wstawiania wartości jest tym samym kryterium, które służy do lokalizowania (i odczytywania) wartości.
Otwórz adresowanie
Przy otwartym adresowaniu wszystkie wartości są przechowywane w tablicy wiader. Gdy wystąpi konflikt, nowa wartość jest wstawiana do pustego wiadra, nowa odpowiednia wartość konfliktu, zgodnie z pewnym kryterium. Kryterium używane do wstawiania wartości będącej w konflikcie jest tym samym kryterium, które służy do lokalizowania (wyszukiwania i odczytywania) wartości.
Poniższy diagram ilustruje rozwiązywanie konfliktów z otwartym adresowaniem:
Funkcja haszująca pobiera klucz Peter Jones i haszuje indeks 152 oraz przechowuje jego numer telefonu w powiązanym zasobniku. Po pewnym czasie funkcja haszująca haszuje ten sam indeks, 152 z klucza Suzan Lee, kolidując z indeksem dla Petera Jonesa. Aby rozwiązać ten problem, wartość Suzan Lee jest przechowywana w pojemniku następnego indeksu, 153, który był pusty. Funkcja haszująca haszuje 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 Hooda jest umieszczana w następnym pustym wiadrze, o indeksie 154.
Metody rozwiązywania konfliktów dla oddzielnego tworzenia łańcuchów i otwartego adresowania
Oddzielne tworzenie łańcuchów ma swoje metody rozwiązywania konfliktów, a otwarte adresowanie ma również własne metody rozwiązywania konfliktów.
Metody rozwiązywania oddzielnych konfliktów łańcuchowych
Poniżej pokrótce wyjaśniono metody tworzenia oddzielnych tabel skrótów łańcuchowych:
Oddzielne tworzenie łańcuchów z połączonymi listami
Ta metoda jest jak wyjaśniono powyżej. Jednak każdy element połączonej listy niekoniecznie musi mieć pole kluczowe (e.sol. pole nazwy klienta powyżej).
Oddzielne tworzenie łańcucha z komórkami nagłówka listy
W tej metodzie pierwszy element połączonej listy jest przechowywany w kubełku tablicy. Jest to możliwe, jeśli typ danych dla tablicy jest elementem połączonej listy.
Oddzielne łączenie z innymi strukturami
Dowolna inna struktura danych, taka jak samobalansujące drzewo wyszukiwania binarnego, które obsługuje wymagane operacje, może zostać użyta zamiast połączonej listy - patrz dalej.
Metody rozwiązywania otwartych konfliktów adresowania
Metoda rozwiązywania konfliktów w otwartym adresowaniu nazywana jest sekwencją sondy. Trzy dobrze znane sekwencje sond zostały teraz pokrótce wyjaśnione:
Sondy liniowe
W przypadku sondowania liniowego, gdy wystąpi konflikt, szukany jest najbliższy pusty kubeł poniżej kubełka, w którym występuje konflikt. Ponadto w przypadku sondowania liniowego zarówno klucz, jak i jego wartość są przechowywane w tym samym kubełku.
Sondowanie kwadratowe
Załóżmy, że konflikt występuje przy indeksie H. Następne puste miejsce (wiadro) o indeksie H + 12 Jest używane; jeśli jest już zajęty, to następny pusty w H + 22 jest używany, jeśli jest już zajęty, to następny pusty w H + 32 jest używany i tak dalej. Istnieją warianty tego.
Podwójne haszowanie
W przypadku podwójnego haszowania istnieją dwie funkcje haszowania. Pierwszy oblicza (hashe) indeks. Jeśli wystąpi konflikt, drugi używa tego samego klucza do określenia, jak daleko w dół należy wstawić wartość value. Jest w tym coś więcej - zobacz później.
Doskonała funkcja skrótu
Doskonała funkcja mieszająca to funkcja mieszająca, która nie może powodować kolizji. Może się to zdarzyć, gdy zestaw kluczy jest stosunkowo mały, a każdy klucz jest mapowany na konkretną liczbę całkowitą w tablicy mieszającej.
W zestawie znaków ASCII duże znaki można odwzorować na odpowiadające im małe litery za pomocą funkcji skrótu. Litery są reprezentowane w pamięci komputera jako liczby. W zestawie znaków ASCII A to 65, B to 66, C to 67 itd. a a to 97, b to 98, c to 99 itd. Aby mapować od A do a, dodaj 32 do 65; aby mapować od B do b, dodaj 32 do 66; aby odwzorować od C do c, dodaj 32 do 67; i tak dalej. Tutaj duże litery to klawisze, a małe litery to wartości. Tablica mieszająca może być tablicą, której wartościami są powiązane indeksy. 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 dużej liczby kodu w celu uzyskania indeksu, a więc małej litery. Taka funkcja to idealna funkcja mieszająca.
Hashowanie od liczb całkowitych do indeksów liczb całkowitych
Istnieją różne metody mieszania liczb całkowitych. Jednym z nich jest metoda podziału modulo (funkcja).
Funkcja haszująca dywizji Modulo
Funkcja w oprogramowaniu komputerowym nie jest funkcją matematyczną. W informatyce (oprogramowaniu) funkcja składa się ze zbioru instrukcji poprzedzonych argumentami. W przypadku funkcji podziału modulo klucze są liczbami całkowitymi i są mapowane na indeksy tablicy kubełków. Zestaw kluczy jest duży, więc mapowane będą tylko te klucze, które z dużym prawdopodobieństwem wystąpią w działaniu activity. Tak więc kolizje występują, gdy trzeba zmapować mało prawdopodobne klucze.
W oświadczeniu,
20/6 = 3R2
20 to dywidenda, 6 to dzielnik, a 3 pozostałe 2 to iloraz. Reszta 2 jest również nazywana modulo. Uwaga: możliwe jest posiadanie modulo 0.
W przypadku tego haszowania rozmiar tabeli to zwykle potęga 2, e.sol. 64 = 26 lub 256 = 28, itp. Dzielnikiem tej funkcji mieszającej jest liczba pierwsza zbliżona do rozmiaru tablicy array. Ta funkcja dzieli klucz przez dzielnik i zwraca modulo. modulo jest indeksem tablicy wiader. Powiązana wartość w zasobniku to wybrana przez Ciebie wartość (wartość klucza).
Haszowanie kluczy o zmiennej długości
Tutaj klucze zestawu kluczy są tekstami o różnej długości. Różne liczby całkowite mogą być przechowywane w pamięci przy użyciu tej samej liczby bajtów (wielkość znaku angielskiego to bajt). Kiedy różne klucze mają różne rozmiary, mówi się, że mają zmienną długość. Jedna z metod haszowania zmiennych długości nazywa się haszowaniem konwersji Radix.
Hashowanie konwersji Radix
W łańcuchu każdy znak w komputerze jest liczbą. W tej metodzie,
Kod skrótu (indeks) = x0zak−1+x1zak−2+… +xk−2za1+xk−1za0
Gdzie (x0, x1,… , xk−1) to znaki ciągu wejściowego, a a to podstawa, e.sol. 29 (patrz dalej). k to liczba znaków w łańcuchu. Jest w tym coś więcej - zobacz później.
Klucze i wartości
W parze klucz/wartość wartość niekoniecznie musi być liczbą lub tekstem. Może też być rekordem. Rekord to lista pisana poziomo. W parze klucz/wartość każdy klucz może w rzeczywistości odnosić się do innego tekstu, liczby lub rekordu.
Tablica asocjacyjna
Lista jest strukturą danych, w której elementy listy są ze sobą powiązane i istnieje zestaw operacji, które operują na liście. Każdy element listy może składać się z pary elementów. Ogólna tablica mieszająca z jej kluczami może być uważana za strukturę danych, ale jest ona bardziej systemem niż strukturą danych. Klucze i odpowiadające im wartości nie są bardzo od siebie zależne. Nie są ze sobą bardzo spokrewnieni.
Z drugiej strony tablica asocjacyjna jest podobna, ale klucze i ich wartości są bardzo od siebie zależne; są ze sobą bardzo spokrewnieni. Na przykład możesz mieć skojarzoną tablicę owoców i ich kolorów. Każdy owoc naturalnie ma swój kolor. Kluczem jest nazwa owocu; kolor jest wartością. Podczas wstawiania każdy klucz jest wstawiany ze swoją wartością. Podczas usuwania każdy klucz jest usuwany wraz z jego wartością.
Tablica asocjacyjna to struktura danych tabeli mieszającej złożona z par klucz/wartość, w której nie ma duplikatów kluczy. Wartości mogą mieć duplikaty. W tej sytuacji klucze są częścią struktury. Oznacza to, że klucze muszą być przechowywane, podczas gdy w przypadku ogólnej tablicy hast klucze nie muszą być przechowywane. Problem zduplikowanych wartości w naturalny sposób rozwiązują indeksy tablicy kubełków. Nie pomyl zduplikowanych wartości i kolizji w indeksie.
Ponieważ tablica asocjacyjna jest strukturą danych, ma co najmniej następujące operacje:
Operacje na tablicach asocjacyjnych
wstaw lub dodaj
Spowoduje to wstawienie nowej pary klucz/wartość do kolekcji, mapując klucz na jego wartość.
zmienić przypisanie
Ta operacja zastępuje wartość określonego klucza nową wartością.
usuń lub usuń
Usuwa klucz i odpowiadającą mu wartość.
wyszukiwanie
Ta operacja wyszukuje wartość określonego klucza i zwraca wartość (bez jej usuwania).
Wniosek
Struktura danych tablicy mieszającej składa się z tablicy i funkcji. Funkcja nazywa się funkcją haszującą. Funkcja mapuje klucze do wartości w tablicy poprzez indeksy tablicy. Klucze niekoniecznie muszą być częścią struktury danych. Zestaw kluczy jest zwykle większy niż zapisane wartości. Gdy wystąpi kolizja, jest ona rozwiązywana za pomocą podejścia oddzielnego łączenia lub otwartego podejścia adresowania . Tablica asocjacyjna jest szczególnym przypadkiem struktury danych tablicy mieszającej.
