[MUZYKI] DOUG LLOYD: Przez teraz dużo wiedzieć o tablicach, i wiele o powiązanych list wiedzieć. I mamy dyskutować plusy i minusy, mamy omówione, że związane list można uzyskać większe i mniejsze, ale zajmują więcej wielkości. Tablice są znacznie bardziej proste do używać, ale są restrykcyjne w tyle jak mamy się ustawić rozmiar matryca na początku a potem utknęliśmy z nim. 

Ale to, mamy dość dużo wyczerpane wszystkie nasze tematy o powiązanych list i tablic. Mogą też my? Może uda nam się coś zrobić jeszcze bardziej kreatywne. I tego rodzaju nadaje pomysł tabeli mieszania. 

Tak więc w tabeli mieszania mamy zamiar spróbować połączyć tablicę z połączonej listy. Jedziemy do podjęcia zalety tablicy, na przykład jednostka dostępowa, będąc w stanie po prostu pójść do tablicy Element 4 lub element tablicy 8 bez konieczności iteracji w poprzek. To dość szybko, prawda? 

Ale my także chcemy mieć nasze dane Struktura w stanie rozwijać się i kurczyć. Nie potrzebujemy, my nie chcą być ograniczone. I chcemy, aby móc do dodawania i usuwania rzeczy bardzo łatwo, która, jeśli przypomnieć, jest bardzo złożone z tablicą. I możemy nazwać Nowością tabeli mieszania. 

A jeśli realizowane prawidłowo, jesteśmy jakby biorąc Zalety obu dane Struktury już widziałem, tablice i związane listy. Wprowadzające może zacząć tendencję w kierunku theta z 1. Theta tak naprawdę nie wspomniano, ale theta jest tylko średnia przypadku, co się faktycznie zdarzy. Nie zawsze będziemy mają najgorszy scenariusz, a ty nie zawsze będzie mieć najlepszy scenariusz, więc co to średni scenariusz? 

Cóż średnio wstawiania w tabeli mieszania może rozpocząć się zbliżyć do stałej czasu. I usuwanie może uzyskać blisko stałym czasie. I wyszukiwania mogą uzyskać blisko stałym czasie. That's-- nie ma danych Struktura jednak, że może to zrobić, i tak to brzmi jak całkiem wielkiej rzeczy. Mamy naprawdę złagodziły wady każdego z nich na własną rękę. 

Aby uzyskać ten występ uaktualnić chociaż, my należy zastanowić się, jak możemy dodać dane w strukturze. W szczególności chcemy Same dane nam powiedzieć gdzie powinien iść w strukturze. A jeśli to konieczne, aby zobaczyć, czy to w struktura, jeśli musimy go znaleźć, chcemy spojrzeć na dane jeszcze raz i być w stanie skutecznie, wykorzystując dane losowo do niego dostęp. Po prostu patrząc na Dane powinniśmy mieć pomysł na to, gdzie dokładnie jesteśmy będzie go znaleźć w tabeli mieszania. 

Teraz minusem hash Stół jest to, że są naprawdę całkiem nieźle zamawiania lub sortowania danych. I rzeczywiście, jeśli zaczniesz wykorzystać je do zamówienia lub rodzaju Dane można stracić wszystkie z Zalety wcześniej miał w zakresie wstawiania i usuwania. Czas staje się bliższy theta n, i mamy w zasadzie regres w połączonej listy. A więc chcemy używać tylko hash tabele, jeśli nie dbają o czy dane są sortowane. Dla sytuacji, w której będziesz ich używać w CS50 prawdopodobnie nie obchodzi że dane są sortowane. 

Więc tabeli mieszania jest połączeniem z dwóch różnych kawałków z którymi jesteśmy zaznajomieni. Pierwszym z nich jest funkcją, która zwykle nazywamy funkcji skrótu. I że funkcja skrótu będzie powrót trochę nieujemną liczbę całkowitą, która zwykle nazywamy hashcode, OK? Drugi element jest tablicą, która jest zdolny do przechowywania danych typu my chcą umieścić w strukturze danych. Będziemy trzymać się na powiązany element listy do teraz i po prostu zacząć od podstaw o charakterze tablica mieszająca dostać głowę wokół niego, a następnie będziemy może wiać twój umysł nieco, kiedy łączyć macierze i listy linków razem. 

Podstawową ideą, choć to bierzemy jakieś dane. Prowadzimy tych danych poprzez funkcja skrótu. I tak dane są przetwarzane i to wypluwa numer, OK? A następnie z tej liczby po prostu przechowywania danych chcemy przechowywać w Tablica w tej lokalizacji. Tak na przykład mamy może tabela hash łańcuchów. Ma 10 elementów w niej, tak, możemy zmieścić 10 strun w nim. 

Powiedzmy, że chcemy hash John. Więc Jana jak dane chcemy wstawić w tej tabeli mieszania gdzieś. Gdzie możemy umieścić go? Cóż zazwyczaj ze związkiem Tablica do tej pory prawdopodobnie by umieścić go w miejscu tablicy 0. Ale teraz mamy tę nową funkcję skrótu. 

I powiedzmy, że prowadzimy Jana dzięki tej funkcji skrótu i to wypluwa 4. No to gdzie jesteśmy będzie chciał umieścić John. Chcemy postawić Jana w miejscu tablicy 4, bo jeśli hash Jana again-- powiedzmy później Aby wyszukać i zobaczyć jeśli istnieje w tym John hash table-- wszystkim musimy zrobić prowadzony jest to przez samego hash Funkcja, uzyskać numer na 4, i być w stanie znaleźć Jana natychmiast w naszej strukturze danych. To dość dobre. 

Powiedzmy, że teraz to zrobić znowu, chcemy hash Paul. Chcemy, aby dodać Paul w tej tabeli hash. Powiedzmy, że tym razem możemy uruchomić Paweł dzięki funkcji skrótu, hashCode, który jest generowany 6. No to teraz możemy umieścić Pawła w miejscu tablicy 6. A jeśli musimy przyjrzeć się, czy Paweł jest w tej tabeli mieszania, wszystko, co musisz zrobić, to uruchomić Paul dzięki funkcji skrótu ponownie a my będziemy się 6 ponownie. 

A potem po prostu patrzeć w miejscu tablicy 6. Czy Paweł nie? Jeśli tak, jest w tabeli mieszania. Czy Paweł nie istnieje? Nie ma go w tabeli mieszania. To całkiem proste. 

Teraz jak można zdefiniować funkcję skrótu? No naprawdę nie ma ograniczeń co do Liczba możliwych funkcji skrótu. W rzeczywistości istnieje wiele naprawdę, naprawdę dobrzy w Internecie. Jest kilka naprawdę, bardzo złych w Internecie. Jest to także dość łatwe napisać zły. 

Więc to, co składa się na dobre funkcja skrótu, prawda? No dobra funkcja skrótu powinna używać tylko dane są zakodowane, oraz wszystkie dane są zaszyfrowane. Więc nie chcemy używać anything-- nie wiemy nic włączenia jeszcze inny niż dane. I chcemy wykorzystać wszystkie dane. Nie chcemy po prostu użyć kawałek o tym, chcemy wykorzystać wszystkie. Funkcja skrótu powinna być deterministyczny. Co to znaczy? Cóż to oznacza, że ​​za każdym razem, mijają dokładnie ten sam kawałek danych do funkcji mieszającej zawsze uzyskać ten sam hashcode się. Jeśli mijam Jana Into the funkcja skrótu wyjdę 4. Powinienem być w stanie to zrobić 10000 razy i zawsze będę dostać 4. Więc nie ma liczb losowych skutecznie mogą być zaangażowane w naszej hash tables-- w naszych funkcji skrótu. 

Funkcja skrótu powinien również równomiernie rozprowadzić danych. Jeśli przy każdym uruchomieniu danych poprzez funkcja skrótu masz hashcode 0, to chyba nie tak wielki, prawda? Prawdopodobnie chcesz duże zakres kodów cebulą. Również rzeczy mogą być rozłożone na całym stole. A także, że byłoby wspaniale, jeśli naprawdę podobne dane, jak John i Jonatana, Może były rozłożone zważyć różne miejsca w tabeli mieszania. To byłoby miłe zaletą. 

Oto przykład z funkcji skrótu. Napisałem ten jeden się wcześniej. To nie jest szczególnie dobra funkcja skrótu z powodów, że tak naprawdę nie ponosić będzie w tej chwili. Ale widzisz, co tu się dzieje? Wydaje się, że jesteśmy deklarowanie zmiennej zwana suma i ustawienie go równa 0. A potem widocznie robię coś tak długo, jak strstr [j] nie jest równa interpretacja odwrotnego ukośnika 0. Co ja tam robi? 

Jest to w zasadzie tylko kolejny sposób realizacji [? strl?] i wykrywanie, kiedy masz osiągnął koniec łańcucha. Więc nie mam faktycznie obliczyć długość łańcucha, Jestem po prostu za pomocą, kiedy uderzył w backslash 0 znak wiem I już dobiega końca łańcucha. A potem mam zamiar utrzymać iteracja tego łańcucha, dodanie strstr [J], aby podsumować, a następnie na Koniec dnia powróci suma mod HASH_MAX. 

W zasadzie to wszystko hash Funkcja robi jest dodanie wszystkie wartości ASCII mój ciąg, i to jest to powrót trochę hashcode modded przez HASH_MAX. To chyba rozmiar mojej tablicy, prawda? Nie chcę, aby być coraz hash Kody jeśli tablica ma rozmiar 10, Nie chcę być coraz spośród kody hash 11, 12, 13, nie mogę umieścić rzeczy w te lokalizacje tablicy, że byłoby nielegalne. Chciałbym ponieść winy segmentacji. 

Teraz tu jest inny szybkie bok. Generalnie jesteś prawdopodobnie nie będzie chcą pisać własne funkcje skrótu. To jest rzeczywiście trochę sztuką, a nie nauką. I jest wiele, że idzie do nich. Internet, jak powiedziałem, jest pełna naprawdę dobrych funkcji skrótu, i należy korzystać z internetu do znaleźć funkcje skrótu, bo to jest naprawdę po prostu rodzaj niepotrzebne strata czasu, aby utworzyć własne. 

Możesz napisać prostych do celów testowych. Ale kiedy rzeczywiście będziemy rozpoczęcie mieszania danych i przechowywania go w tabeli mieszania jesteś prawdopodobnie będzie chciał używać niektórych funkcji, które zostały wygenerowane dla Ciebie, który istnieje w Internecie. Jeśli nie po prostu mieć pewność, przytoczyć swoje źródła. Nie ma powodu, aby plagiat cokolwiek tutaj. 

Społeczność informatyka jest zdecydowanie rośnie, a tak naprawdę wartości open source, i to jest bardzo ważne przytoczyć swoje źródła tak, że ludzie może uzyskać przypisanie do praca, że ​​są one robi dla dobra wspólnoty. Więc zawsze sure-- a nie tylko hash funkcje, ale na ogół, gdy używać kodu z zewnętrznego źródła zawsze cytują źródło. Podajesz autorstwo osoby zrobił niektóre prace, więc nie trzeba. 

OK, więc niech to ponownie to tablica mieszająca na sekundę. To jest, gdy wyszliśmy się po tym włożona Jana i Pawła w tej tabeli hash. Czy widzisz tu problem? Można zobaczyć dwa. Ale przede wszystkim, prawda zobacz ten możliwy problem? 

Co zrobić, jeśli hash Ringo, i to Okazuje się, że po przetworzeniu że dane za pomocą funkcji skrótu Ringo generowane również hashcode 6. Mam już dane na hashcode-- lokalizacja tablicy 6. Więc to chyba będzie nieco problem dla mnie teraz, prawda? 

Nazywamy to kolizja. I kolizji występuje wtedy, gdy dwa kawałki danych prowadzony przez ten sam hash Funkcja dają ten sam hashcode. Prawdopodobnie nadal chcemy się zarówno kawałki danych do tabeli hash, w przeciwnym razie nie będzie uruchomiony Ringo arbitralnie za pośrednictwem funkcji skrótu. My prawdopodobnie chcą się Ringo do tej tablicy. 

Jak mamy to zrobić jednak, jeśli i Paul zarówno wydajność hashCode 6? Nie chcemy, aby zastąpić Pawła, chcemy Paweł tam być też. Więc musimy znaleźć sposób, aby uzyskać elementów w tablicy mieszającej, że nadal zachowuje nasze szybkie wstawiania i szybkie spojrzenie w górę. A jednym ze sposobów radzenia sobie z nim jest zrobić coś o nazwie liniowa sondowania. 

Korzystając z tej metody, jeśli mamy kolizji, dobrze, co mamy robić? Cóż, nie można umieścić go w miejscu tablicy 6, lub cokolwiek hashCode został wygenerowany, postawmy go w hashcode plus 1. A jeśli to pełna Miejmy umieścić go w hashcode plus 2. Zaletą tej istoty, czy on nie dokładnie tam, gdzie uważamy, że jest, i musimy rozpocząć wyszukiwanie, może nie trzeba iść za daleko. Być może nie musimy szukać wszystkie elementy n z tabeli mieszania. Być może mamy do wyszukiwania kilka z nich. 

I tak my wciąż zmierza w kierunku że średnia Sprawa jest blisko do 1 vs blisko n, więc może, że będzie działać. Zobaczmy więc, jak to Może pracować w rzeczywistości. I zobaczmy, czy może uda nam się wykryć problem, który może pojawić się tutaj. 

Powiedzmy, że hash Bart. Więc teraz mamy zamiar uruchomić nowy zestaw strun poprzez funkcji skrótu, i prowadzimy Bart przez hash Funkcja, mamy hashcode 6. Przyjrzymy, zobaczymy 6 pusta, więc możemy umieścić Bart tam. 

Teraz hash Lisa i że również generuje hashcode 6. No to teraz, że używamy tego liniowa sondowania metody zaczynamy na 6, widzimy, że 6 jest pełna. Nie możemy umieścić Lisa w 6. Więc gdzie pójdziemy? Chodźmy do 7. 7 jest pusta, tak, że działa. Więc postawmy Lisa tam. 

Teraz hash Homera i mamy 7. OK, dobrze wiemy, że 7 jest pełne teraz, więc nie możemy umieścić Homer istnieje. Więc chodźmy do 8. Czy 8 dostępne? Tak, i 8, niedaleko 7, więc jeśli musimy rozpocząć wyszukiwanie jesteśmy nie będzie musiał iść za daleko. A więc postawmy Homera na 8. 

Teraz hash Maggie i zwraca 3, dzięki Bogu jesteśmy w stanie po prostu umieścić Maggie tam. Nie mamy zrobić dowolny rodzaj sondowania za to. Teraz hash Marge, a Marge zwraca również 6. 

Cóż 6 jest pełna, 7 jest pełna, 8 jest pełna, 9, w porządku dziękuję Bogu, 9 jest pusty. Mogę umieścić Marge na 9. Już widzimy, że zaczynamy mieć ten problem, gdzie teraz jesteśmy zaczynają się rozciągać rzeczy rodzaj z dala od swoich kodeksów z cebulą. I że theta 1, że średnie Sprawa jest stała czasowa, zaczyna się trochę more-- zaczyna się zwykle trochę więcej do teta n. Zaczynamy tracić, że Zaletą tablic hash. 

To problem, który właśnie zobaczył jest coś, co nazywa klastrów. A co jest naprawdę źle klastrów jest to, że po ciebie mają dwa elementy, znajdujące się obok bok, to sprawia, że ​​nawet bardziej prawdopodobne, masz dwa razy szansa, że ​​masz zamiar mieć inną kolizję z tego klastra, a klaster wzrośnie o jeden. I będziesz trzymać rośnie i rośnie Twój prawdopodobieństwo konieczności kolizji. I w końcu to tylko tak źle jako nie sortowanie danych w ogóle. 

Innym problemem jest jednak, że wciąż, i tak daleko do tego punktu, mamy właśnie rodzaj rozumiejąc, co się tabela mieszania jest, wciąż mamy tylko miejsce na 10 strun. Jeśli chcemy, aby kontynuować do mieszania mieszkańcy Springfield, możemy dostać tylko 10 z nich tam. A jeśli spróbujemy dodać na 11 lub na 12, nie mamy miejsca, aby je umieścić. Moglibyśmy być wiruje wokół w kręgi próbują znaleźć puste miejsce, i może utknąć w nieskończonej pętli. 

Więc tego rodzaju nadaje się do idei coś zwane łańcuchowym. I to jest, gdy mamy zamiar wnieść związane z powrotem do listy obrazu. Co zrobić, jeśli zamiast przechowywać tylko Sam dane w tablicy, każdy element tablicy mógł posiadają wiele elementów danych? Dobrze, że nie ma sensu, prawda? Wiemy, że tablica może tylko hold-- każdy element tablicy może posiadać tylko jeden kawałek danych tego typu danych. 

Ale co, jeśli typ danych Jest to związane lista, prawda? Co z tego, co element macierz wskaźnik na czele połączonej listy? A potem możemy budować te związane listy i rozwijać je w sposób arbitralny, ponieważ związane listy pozwalają nam rosną i kurczą się dużo więcej elastycznie niż tablica ma. Co z tego, że teraz używać, możemy wykorzystać to, prawda? Zaczynamy rozwijać te łańcuchy z tych lokalizacji tablicy. 

Teraz możemy zmieścić nieskończona Ilość danych, czy nie nieskończona, dowolna ilość Dane, na naszej tablicy mieszającej nigdy nie działa w problem kolizji. Mamy również Usunęliśmy klastrów w ten sposób. I dobrze wiemy, że gdy wstawiamy w połączonej listy, jeśli przypomnieć z połączonych wideo na naszej liście, pojedynczo związane listy i podwójnie związane listy, to ciągła praca razem. Jesteśmy po prostu dodając do przodu. 

A dla patrzeć, jak wiemy, że wygląda się w połączonej listy może być problem, prawda? Musimy przeszukać to od początku do końca. Nie ma losowo dostęp w połączonej listy. Jeśli jednak zamiast jednego połączonego Lista odnośników gdzie byłoby O n, teraz mamy 10 związane listy, lub 1000 związane listy, teraz to wy n dzieli się przez 10, lub O n dzieli się przez 1000. 

I kiedy rozmawialiśmy teoretycznie o złożoności pominąć stałe, w prawdziwym Świat te rzeczy naprawdę ważne, dobrze? My faktycznie zauważy że tak się stanie uruchomić 10 razy szybciej, lub 1000 razy szybciej, ponieważ jesteśmy dystrybucji jeden długi Łańcuch całym 1000 mniejszych łańcuchów. I tak za każdym razem mamy do wyszukiwania przez jeden z tych łańcuchów możemy ignorować 999 łańcuchy nie dbamy o, i po prostu szukać tego. 

Które jest średnio być 1000 razy krótszy. I tak nadal są rodzajem zmierzające do tego przeciętnego przypadku bycia stałą czasu, ale tylko dlatego, że wykorzystują podzielenie przez jakiś ogromny stały współczynnik. Zobaczmy, jak to może faktycznie wygląda jakby. Więc to był tabeli mieszania mieliśmy zanim oświadczył tabeli mieszania, które był zdolny do przechowywania 10 strun. Nie będziemy tego robić więcej. My już wiemy, że Ograniczenia tej metody. Teraz nasz tabeli mieszania będzie tablica z 10 węzłów, wskaźników do szefów połączonych listach. 

A teraz to jest wartość null. Każdy z tych 10 wskaźników jest null. Nie ma nic w naszej tablica mieszająca teraz. 

Teraz zacznijmy umieścić niektóre rzeczy w tej tabeli hash. I zobaczmy, jak ta metoda jest zamierza skorzystać nam trochę. Załóżmy teraz hash Joey. Będziemy uruchomi łańcuch Joey przez funkcja mieszania i wracamy 6. No i co teraz zrobimy? 

No to teraz pracuje z połączonych listach, nie jesteśmy pracy z tablicami. A kiedy pracujemy z połączonych listach mamy wiem, musimy zacząć dynamicznie Alokacja przestrzeni i budowy sieci. To rodzaj how-- te są podstawą elementy budowy połączonej listy. Więc niech się dynamicznie przydzielić miejsca na Joey'a, a następnie dodajmy go do łańcucha. 

Tak teraz wygląda, co zrobiliśmy. Kiedy hash Joey mamy hashcode 6. Teraz kursor w miejscu tablicy 6 wskazuje na czele połączonej listy, a teraz jest to tylko element połączonego listy. Oraz węzeł że związane lista jest Joey. 

Więc jeśli musimy patrzeć Joey później, po prostu hash Joey znowu, mamy 6 ponownie, ponieważ nasze funkcja skrótu jest deterministyczny. I wtedy zaczynają się od głowy z połączonej listy wskazał się według lokalizacji tablicy 6, i możemy iteracji poprzek, że stara się znaleźć Joey. A jeśli budujemy skutecznie tablica mieszająca, a nasza funkcja skrótu skutecznie do dystrybucji danych oraz, średnio każda z nich połączona Listy w każdym miejscu tablicy będzie 1/10 wielkości, jeśli po prostu musiałem go jako jeden ogromny związane lista ze wszystkim w nim. 

Jeśli będziemy rozpowszechniać, że ogromna powiązane Lista w 10 połączonych list Każda lista będzie 1/10 wielkości. A więc 10 razy szybciej przeszukiwać. Więc zróbmy to jeszcze raz. Załóżmy teraz hash Ross. 

I powiedzmy, Ross, kiedy to zrobić kod skrótu wrócimy to 2. No to teraz mamy dynamicznie lokować nowy węzeł, kładziemy Ross w tym węźle, i mówimy teraz położenie tablicy 2, zamiast wskazywać na null, wskazuje na czele powiązane Lista których tylko węzeł jest Ross. I możemy zrobić to jeszcze raz, my może hash Rachel i uzyskać hashcode 4. malloc nowy węzeł, umieścić Rachel w węzeł, i powiedzieć lokalizację tablicy 4 teraz wskazuje na głowie z połączonej listy, której Jedynym elementem dzieje się Rachel. 

OK, ale co się stanie, jeśli mamy kolizję? Zobaczmy, jak obchodzimy kolizji użyciu osobnej metody łańcuchowym. Miejmy hash Phoebe. Dostajemy hashcode 6. W poprzednim przykładzie były tylko przechowywania ciągów w tablicy. To był problem. 

Nie chcemy, by sprać Joey, i już mam widać, że możemy trochę klastrów problemy, jeśli staramy się krok przez i sondy. Ale co, jeśli po prostu rodzaj traktować to w ten sam sposób, prawda? To tak jak dodanie elementu na czele połączonej listy. Miejmy tylko malloc przestrzeń dla Phoebe. 

Powiemy kolejne punkty pointer Phoebe do starego szefa połączonej listy, a następnie 6 prostu wskazuje na Nowy szef połączonej listy. A teraz spójrz, zmieniliśmy Phoebe. Możemy teraz zapisać dwa Elementy z hashcode 6 i nie mamy żadnych problemów. 

To dość dużo wszystko nie jest łańcuchowych. I łańcuchowym jest zdecydowanie metoda to będzie najbardziej skuteczne dla Ciebie, jeśli dane są przechowywane w tabeli mieszania. Ale to połączenie tablice i związane listy razem tworzą tabeli mieszania faktycznie znacznie poprawia zdolność do przechowywania dużych ilości danych, a bardzo szybko i sprawnie wyszukać za pośrednictwem tych danych. 

Jest jeszcze jeden Struktura danych tam że może być nawet nieco lepiej jeśli chodzi o zagwarantowanie że nasz wstawianie, usuwanie i patrzeć czasy w jeszcze szybciej. I zobaczymy, że w wideo na próbach. Jestem Doug Lloyd, to CS50.