[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.