[NOISE]. Przed nurkowaniem w tablicach hash, niech Pierwszy przegląd zalet i wad niektórych prostszych struktur danych, począwszy tablice. Przypomnijmy, że tablice pozwalają na przechowywanie elementów jednego typu danych sposób ciągły w pamięci. Ponieważ każdy element jest związane z Indeks, lub lokalizacja, mamy swobodny dostęp do wszystkich elementów w tablicy. Innymi słowy, możemy uzyskać dostęp do dowolnego elementu w jednym etapie przez indeksowanie do tablica. To jest wielka sprawa, ponieważ algorytmy jak poszukiwania binarnego zależy od losowych dostępu. Minusem jest to, że tablice na ich wielkość jest stała. Ponieważ tablice przechowują dane w sposób zwarty pamięci, należy określić rozmiar tablicy Kiedy deklarujesz tablicę. Jesteś operacyjną skutecznie prosząc System zarezerwować odpowiednią ilość pamięci na elementy tablicy. Nie ma gwarancji, że więcej pamięci, przylegające do tablicy, będą dostępne do wykorzystania później. Tablice nie mogą tak łatwo rozwijać. Przypomnijmy, że dowiedzieliśmy się o związane Listy, które mogą rosnąć, ponieważ ich Elementy nie są ciągłe w pamięci. Każdy węzeł w połączonej listy zawiera element, który chcemy zapisać, jak również Wskaźnik na następny element lista. Niestety, cena, jaką zapłaciłeś za dynamiczny wielkość jest przypadkowa dostęp elementy. W celu uzyskania dostępu do jakiegoś elementu, konieczne jest przejście przez całą do czasu aż pożądany pierwiastek osiągnięta. Tak więc, jeśli szukam numeru 9, ja bym przestrzegać wskazówek od węzła do węzła, sprawdzenie czy wartość każdego węzła jest równa 9. Jako takie, w najgorszym przypadku, patrzeć jest O (n), co jest dalekie od skuteczny. Możemy to zrobić lepiej niż O (n), a jednocześnie pozwalając nasza struktura danych rośnie ponad czas? Tabele Hash zaoferować rozwiązanie. Tabele Hash są stosowane, gdy szybki wstawianie, usuwanie i wyszukiwanie z elementy jest priorytetem. W teorii, wstawianie, usuwanie i wyszukiwanie Nawet może być realizowane w stałym czas. Tak, to jest tabela hash tak? Tabela mieszania jest tylko tablica w połączeniu z funkcji, które my nazywamy hash funkcja. Funkcja mieszająca przyjmuje element danych jako wejście, nazwijmy to klucz, a wysyła liczbę całkowitą, nazywane jako wartości hash. Wartość skrótu odwzorowuje nasz klucz do szczególności indeks w tabeli mieszania. Że początkowo użyć funkcji skrótu do określić, gdzie w tabeli mieszania do przechowywać dany klawisz. Później można użyć tej samej funkcji skrótu określić, gdzie w tabeli mieszania do sprawdzić dla danego klucza. Z tego powodu, jest to istotne, że hash Funkcja zachowuje się konsekwentnie i wyjścia samą wartość skrótu dla tych samych klawiszy. Wiem, że tabele mieszania może być używany do przechowują dane wszystkich typów. Ale dla uproszczenia rzeczy, będziemy koncentrować się na Struny do teraz. Oto prosta funkcja skrótu ciągów. Funkcja ta oblicza hash hash Funkcja na podstawie pierwszej litery klucz. "Jabłko" zaczyna się na literę "A", więc jest to odwzorowane na indeksie 0 w tabeli mieszania. Podobnie, "banana" są odwzorowywane na indeksie 1 i "kot" jest odwzorowywany na indeksie 2. Jeśli przyjaciel pyta, czy słowo "pies" jest w Stół, będziemy psa "wejścia" do mieszania Funkcja, które wyjście będzie wartość skrótu 3. Od "pies" nie jest przechowywany w indeksie 3, my może powiedzieć z pewnością, że "pies" nie jest w tabeli mimo, że mamy tylko jeden sprawdzony hash tabeli na 26 indeksów. Czas wyrzucić klucz do rzeczy. Co jeśli chcemy przechowywać "mrówka" na Stół, jak również? "Mrówka" Sumy na indeksie 0, tak jak "apple" nie. Jest to przykład kolizji wynikiem dwóch kluczy haszowania same Indeks. Nawet jeśli tabeli mieszania jest większa niż ustawić dane i wybrałeś dobre funkcji skrótu, trzeba jeszcze do czynienia z planu kolizje, czy i kiedy się pojawią. Porozmawiajmy o plusy i minusy z dwóch Typowe sposoby rozwiązywania kolizji: liniowy sondowania i oddzielne łańcuchowym. Z adresowania liniowego, jeśli klucz skróty do sam wskaźnik jak wcześniej zapisane Klucz jest przypisany następny dostępny Szczelina w tabeli. Tak więc, "mrówka" jest obecnie przechowywany w indeksie 3, od indeksy 0, 1 i 2 były już w użyciu. A jeśli staramy się zapisać trzecie słowo, które zaczyna się na literę "A", to jest przypisane do wskaźnika 4 od indeksy 0, 1, 2 i 3. są pełne. Jak widać, nawet z tej prostej Na przykład, po kolizji występuje, ci znacznie zwiększyć szanse, że kolejna kolizja nastąpi w samo obszar. To się nazywa klastrów, i to Poważną wadą liniowego sondowania. Co więcej, najgorszy wstawiania, kasowania, i zostały przekazane czasy odnośników do O (n), jako następny wolny slot może mieć potencjalnie był ostatnio gniazdo w tabeli. Może osobna oferta zostanie Łańcuchy więcej atrakcyjne rozwiązanie. W oddzielnym modelu łańcuchowym, hash Stół jest w rzeczywistości tablica wskaźników do związane listy. W przypadku wystąpienia kolizji, może być kluczem umieszczony w stałym czasie w nagłówku odpowiednia lista powiązana. Co się dzieje teraz, kiedy szukamy "apple" w tabeli mieszania? W najgorszym przypadku, musimy przemierzać Cała lista powiązana, zaczynając od indeksu 0. Czas wyszukiwania najgorszy dla mieszania Stół, który wykorzystuje oddzielny łańcuchowych jest Dlatego O (n / k), gdzie k jest rozmiar tabeli mieszania. Chwileczkę, k jest stałą. Tak O (n / k) jest w rzeczywistości O (n) której czas wyszukiwania dla najgorszego przypadku powiązana lista. Czy my naprawdę przeszedł wszystkie Kłopot z nauki o tablicach hash tylko do końca się tam, gdzie zaczęliśmy? To może być sprawa z teoretycznym perspektywicznym, lecz w rzeczywistym świecie O (n / k) może być ogromna poprawa w stosunku O (n). Pomyśl o tym w ten sposób: zakładamy, że k jest 10 - czy raczej poczekać 100 sekund lub 100 / k? 10 sekund od programu Microsoft Word, aby zakończyć sprawdzanie pisowni dokumentu. Jak tylko zobaczyłem, rozwiązywania kolizji pociąga za sobą jeden rodzaj wyszukiwania liniowego lub inny, który spowalnia rzeczy w dół znacznie. Dlatego będziemy chcieli, aby wybrać skrót Funkcja, która minimalizuje ryzyko Kolizje występujące w pierwszym miejscu. Oto niektóre właściwości dobrego mieszania funkcje o których warto pamiętać. Dobra funkcja skrótu powinna korzystać z wszystkie informacje przekazane przez danego klucza W celu zmaksymalizowania liczby Możliwe wartości hash. Na przykład, gdybyśmy mieli dwa ciągi, "kot" i "gąsienica", że chcemy, aby hash do różnych miejsc w tabeli. Jeśli funkcja skrótu wziął pod uwagę tylko Pierwszy z nich, dwie lub nawet trzy listy strun, kolizja nie występuje, ponieważ obydwa słowa rozpocząć same trzy litery. Wartości mieszania powinny być rozłożone równomiernie całej tabeli mieszania. Zmniejszy to długość związana Listy powinny wystąpić kolizje. Jest to także dobry znak, czy wartość skrótu jest zdolny do tworzenia bardzo różny hash wartości dla podobnych kluczy, podejmowania kolizji znacznie mniej prawdopodobne. Naszym celem jest szybka wstawianie, usuwanie, i wyszukiwania. Funkcja skrótu odgrywa kluczową rolę w każdy z tych sposobów i będzie nazywa się bardzo często. Dlatego upewnij się, że zatrudnia tylko bardzo Prosty, szybki przebieg operacji, aby zminimalizować czas. Mam nadzieję, że podobał mi się ten krótki Wprowadzenie do mieszania tabele. Nazywam się Laura, i to jest CS50.