[Mūzikas atskaņošanai]
>> Doug LLOYD: Tagad jums zina daudz par masīvu,
un jūs zināt daudz par saistītiem sarakstiem.
Un mēs esam apspriestu plusi un mīnusi, mēs esam
apsprieda, ka saistīti saraksti var iegūt lielāku un mazāku,
bet tie aizņem vairāk lielumu.
Masīvi ir daudz vienkāršāk izmantot, bet viņi ierobežojošs tik daudz
kā mums ir noteikt lielumu masīva pašā sākumā
un tad mēs esam iestrēdzis ar to.
>> Bet tas ir, mēs esam diezgan daudz izsmeltas visas mūsu tēmām
par saistītiem sarakstiem un masīvi.
Vai mēs esam?
Varbūt mēs varam kaut ko darīt vēl vairāk radošs.
Un ka veida aizdod ideja par hash tabulu.
>> Tātad hash tabulā mēs esam gatavojas izmēģināt apvienot masīvu ar saistītajā sarakstā.
Mēs ejam, lai ņemtu priekšrocības masīva, tāpat izlases pieejamību,
to var tikai iet uz masīva elements 4 vai masīva elements 8
bez atkārtot pāri.
Tas ir diezgan ātri, vai ne?
>> Bet mēs arī vēlamies, lai mūsu datiem struktūra varētu augt un sarauties.
Mums nevajag, mums nav vēlas, lai tiktu ierobežota.
Un mēs gribam, lai varētu pievienot un noņemt lietas
ļoti viegli, kas, ja jūs atceraties, ir ļoti komplekss ar masīvu.
Un mēs varam zvanīt šis jauna lieta hash tabulu.
>> Un, ja tos piemēro pareizi, mēs esam veida ņemot
priekšrocības gan datu struktūras jūs jau esat redzējuši,
bloki un saistīti saraksti.
Ievietošana var sākt tendence uz teta no 1.
Theta mēs neesam īsti apspriesti, bet teta ir tikai vidējā gadījums,
to, kas patiesībā notiek varētu notikt.
Jūs esat ne vienmēr būs ir sliktākajam scenārijam,
un jūs ne vienmēr nāksies Labākajā gadījumā, lai to, kas ir
vidējais scenārijs?
>> Nu vidēji ievietošanas uz hash tabulu
var sākt iegūt tuvu pastāvīgu laiku.
Un dzēšanu var iegūt aizvērt uz pastāvīgu laiku.
Un lookup var saņemt aizvērt uz pastāvīgu laiku.
That's-- mums nav datu struktūra vēl, ka var darīt,
un tāpēc tas jau izklausās kā diezgan liels lieta.
Mēs esam patiešām mazinājis trūkumi katra pati.
>> Lai iegūtu šo sniegumu uzlabot gan, mēs
ir jāpārdomā, kā mēs pievienot datus struktūru.
Konkrēti mēs vēlamies Paši dati, lai pastāstītu mums
ja tas būtu jāiet struktūrā.
Un, ja mēs, tad ir nepieciešams, lai redzētu, vai tas ir struktūra, ja mums ir nepieciešams, lai atrastu to,
mēs vēlamies apskatīt datus atkal un jāspēj efektīvi,
izmantojot datus, nejauši piekļūt.
Vienkārši aplūkojot dati mums ir jābūt
ideja par to, kur tieši mēs esam gatavojas atrast to hash tabulā.
>> Tagad negatīvie jaucējkoda Tabulā ir tas, ka viņi patiešām
diezgan slikti pasūtīšanu vai šķirošanas datus.
Un patiesībā, ja jūs sākat tos izmantot, lai pasūtītu vai kārtot
Datu jūs zaudējat visu iepriekš priekšrocības jūs iepriekš
bija ziņā ievietošanas un dzēšanu.
Laiks kļūst tuvāk teta n, un mēs esam būtībā
regresējusi uz saistītajā sarakstā.
Un tā mēs tikai vēlamies izmantot hash galdi, ja mēs nerūp
vai dati ir sakārtots.
Par kontekstu, kādā jūs tos izmantot CS50
Jūs, iespējams, nav jārūpējas ka dati ir sakārtots.
>> Tātad hash tabulu, ir kombinācija no diviem atšķirīgiem gabaliem
ar kuru mēs esam pazīstami.
Pirmais ir funkcija, kas mēs parasti saucam jaucējfunkciju.
Un tas hash funkcija ir gatavojas atgriešanās kādu nav negatīvs vesels skaitlis, kas
mēs parasti saucam hashcode, OK?
Otrais gabals ir masīvs, kas ir spēj uzglabāt datu tipa mēs
vēlas izvietot uz datu struktūru.
Mēs turēt off par saistīts saraksts elements tagad
un sāc ar pamatiem, tāda hash tabulu, lai saņemtu savu galvu ap to,
un tad mēs varbūt trieciens Jūsu prāts mazliet, kad mēs
apvienot bloki un saistīt sarakstus kopā.
>> Pamatideja though ir mēs dažus datus.
Mums ir, ka dati, izmantojot hash funkciju.
Un tā datus apstrādā un tas atklepo numuru, OK?
Un pēc tam ar šo numuru mēs tikai glabāt datus
mēs vēlamies Uzglabāt masīvs šajā vietā.
Tā, piemēram, mums ir varbūt šis hash tabulu stīgas.
Tas ir ieguvuši 10 elementi, tāpēc mēs varam fit 10 stīgas tajā.
>> Teiksim, mēs vēlamies, lai hash Jāni.
Tātad Jāņa kā datiem mēs gribam, lai ievietotu šajā hash tabulu kaut kur.
Kur mēs to?
Nu parasti ar masīvs Līdz šim mēs, iespējams,
nostāda to masīva atrašanās vietā 0.
Bet tagad mums ir šo jauno hash funkciju.
>> Un pieņemsim, ka mēs palaist Jāni izmantojot šo jaucējfunkciju
un tas ir atklepo 4.
Nu tas ir, ja mēs esam gatavojas vēlaties likt Jāni.
Mēs vēlamies, lai Jāni masīva vietā 4, jo, ja mēs hash Jāņa again--
teiksim vēlāk mēs vēlaties meklēt un redzēt
ja John pastāv šajā hash table-- viss, kas mums jādara,
ir palaist to caur to pašu hash funkcija, saņemt skaits 4,
un jāspēj atrast Jāni Nekavējoties mūsu datu struktūra.
Tas ir diezgan labs.
>> Teiksim, mēs tagad to izdarītu atkal, mēs vēlamies, lai hash Pāvilu.
Mēs vēlamies, lai pievienotu Paul šajā hash tabulā.
Teiksim, ka šoreiz mēs palaist Paul caur hash funkciju,
hashcode kas tiek radīts, ir 6.
Nu tagad mēs varam likt Pāvilu masīvā vietā 6.
Un, ja mums ir nepieciešams meklēt, vai Paul ir šajā hash tabulu,
viss, kas mums jādara, ir palaist Paul caur hash funkciju atkal
un mēs esam gatavojas saņemt 6 no jauna.
>> Un tad mēs vienkārši skatīties pie masīva vietā 6.
Vai Pāvils tur nokļūt?
Ja tā, tad viņš ir hash tabulā.
Vai Pāvils ne tur?
Viņš nav hash tabulā.
Tas ir diezgan vienkārši.
>> Tagad, kā jūs definētu jaucējfunkciju?
Nu tur tiešām nav ierobežojumu vairāki iespējamie hash funkciju.
Patiesībā tur ir vairāki patiešām, tiešām labs tiem internetā.
Tur ir vairāki patiešām, tiešām slikti tiem internetā.
Tas ir arī diezgan viegli uzrakstīt slikti vienu.
>> Tātad, kas veido labu hash funkciju, vai ne?
Nu labs hash funkcija būtu izmantot tikai tiek sajaukts dati,
un visi dati tiek sajaukts.
Tāpēc mēs nevēlamies izmantot anything-- mums nav iekļaut neko
cits citu kā datus.
Un mēs vēlamies izmantot visus datus.
Mēs nevēlamies, lai tikai izmantot kādu par to, mēs vēlamies izmantot visu to.
Hash funkcija būtu arī deterministisko.
Ko tas nozīmē?
Nu tas nozīmē, ka katru reizi, kad mēs iet tieši to pašu datu vienība
uz hash funkciju, mēs vienmēr saņemt tādu pašu hashcode out.
Ja es iet Jāni Into hash funkcija es izkļūt 4.
Man vajadzētu būt iespējai to darīt, 10000 reizes, un es vienmēr saņemsiet 4.
Līdz ar to nav izlases numuri efektīvi var iesaistīties mūsu hash tables--
mūsu hash funkcijas.
>> Hash funkcija būtu arī vienmērīgi izplatīt datus.
Ja katru reizi, kad jūs darbināt datus, izmantojot hash funkcija jums hashcode 0,
tas ir iespējams, nav tik liels, labi?
Jūs droši vien vēlaties liels diapazons hash kodu.
Arī lietas var izplatīties out visā tabulā.
Un arī tas būtu lieliski, ja patiešām līdzīgi dati, piemēram, Jāņa un Jonathan,
varbūt bija izklāt nosvērt dažādās vietās hash tabulā.
Tas būtu jauki priekšrocība.
>> Lūk, piemērs no hash funkciju.
Es uzrakstīju šo vienu agrāk.
Tas nav īpaši labs hash funkcija
iemeslu dēļ, kas nav tiešām ir sedz nonākšana tieši tagad.
Bet vai jūs redzat, kas notiek šeit?
Šķiet, tāpat kā mēs deklarējot mainīgo sauc summa un nosakot to vienāds ar 0.
Un tad acīmredzot es esmu dara kaut ko tik ilgi, kamēr strstr [j] nav vienāds
ar slīpsvītru 0.
Ko es daru tur?
>> Tas būtībā ir tikai vēl viens veids, kā īstenot [? STRL?]
un atklāšanā, kad esat sasnieguši virknes.
Tāpēc man nav reāli aprēķināt garumu no virknes,
Es esmu tikai izmantojot, kad es hit slīpsvītru 0 raksturs es zinu
Esmu sasnieguši virknes.
Un tad es esmu gatavojas glabāt atkārtojot caur šo auklu,
pievienojot strstr [J], lai apkopotu, un pēc tam pie dienas beigās gatavojas atgriezties summa mod
HASH_MAX.
>> Būtībā tas viss hash funkcija dara tiek saskaitot
visas ASCII vērtībām mans stīgu, un tad tas ir
atgriežoties kādu hashcode modded ar HASH_MAX.
Tas ir iespējams, izmērs mana masīvs, labi?
Es nevēlos iegūt hash kodi, ja mans masīvs izmēru 10,
Es nevēlos būt iegūt izrakstās hash kodus 11, 12,
13, es nevaru ielikt lietas šie vietām masīva,
ka būtu nelikumīga.
Es gribētu cieš segmentāciju vaina.
>> Tagad šeit ir vēl viens ātrs malā.
Parasti jūs, iespējams, nav gatavojas gribu uzrakstīt savu hash funkcijas.
Tas ir faktiski mazliet māksla, nevis zinātne.
Un tur ir daudz kas iet uz tiem.
Internets, kā jau teicu, ir pilna patiešām labas hash funkciju,
un jums vajadzētu izmantot internetu, lai atrast hash funkcijas, jo tas ir patiešām
tikko veida nevajadzīgs atkritumu laika, lai izveidotu savu.
>> Jūs varat uzrakstīt vienkāršu ones testēšanas nolūkos.
Bet, ja jūs tiešām gatavojas sākt sajaukšanai datus un uzglabājot
uz hash tabulu jūs esat droši vien vēlaties
izmantot dažas funkcijas, kas tika radīts jums, kas pastāv internetā.
Ja jūs vienkārši būt pārliecināti, citēt savus avotus.
Nav iemesla plagiarize kaut ko šeit.
>> Datorzinātņu kopiena ir noteikti pieaug, un tiešām vērtības
open source, un tas ir patiešām svarīgi citēt savus avotus, lai cilvēki
var saņemt par piedēvēšanu darbs, viņi
dara, lai labā sabiedrībā.
Tā vienmēr ir sure-- un ne tikai hash
funkcijas, bet kopumā, ja jums izmantot kodu no ārējiem avotiem,
vienmēr citēt savu avotu.
Jāpateicas personas, kura daži no darba, lai jums nav.
>> Labi, tāpēc pieņemsim pārskatīt šo hash tabulu par sekundi.
Tas ir, ja mēs pa kreisi off, kad mēs ievietots
Jānis un Pāvils šajā hash tabulā.
Vai jūs redzat problēmu šeit?
Jūs varētu redzēt divas.
Bet jo īpaši, vai ne skatīt šo problēmu?
>> Ko darīt, ja es hash Ringo, un tas Izrādās, ka pēc pārstrādes
ka dati caur hash funkciju Ringo arī radījusi hashcode 6.
Esmu jau ieguvuši datus hashcode-- masīvs vieta 6.
Tātad, tas droši vien būs nedaudz problēmu man tagad, vai ne?
>> Mēs to saucam par sadursmes.
Un sadursme notiek, ja divi gabali datu palaist caur to pašu hash
funkcija dot to pašu hashcode.
Jādomā, ka mēs joprojām vēlaties saņemt gan gabalus datus hash tabulu,
citādi mēs nebūtu darboties Ringo patvaļīgi izmantojot hash funkciju.
Mēs, iespējams, vēlas saņemt Ringo vērā, ka masīva.
>> Kā mēs to darām, lai gan, ja viņš un Paul gan raža hashcode 6?
Mēs nevēlamies pārrakstīt Pāvilu mēs gribam Paul būt tur pārāk.
Tāpēc mums ir jāatrod veids, kā iegūt elementus hash tabulu, kas
joprojām saglabā mūsu ātri ievietošanas un ātri uzmeklēt.
Un viens veids, kā cīnīties ar to ir darīt kaut ko sauc par lineāru zondēšana.
>> Izmantojot šo metodi, ja mums ir sadursme, labi, ko mēs darām?
Nu mēs nevaram likt viņam masīva vietā 6, vai kāds hashcode tika radīts,
Palūkosimies viņam hashcode plus 1.
Un, ja tas ir pilns pieņemsim ielika hashcode plus 2.
Šīs būtnes labums, ja viņš ir nav kur tieši mēs domāju, ka viņš ir,
un mums ir jāsāk meklēt, varbūt mums nav iet pārāk tālu.
Varbūt mums nav, lai meklētu visi n elementi hash tabulu.
Varbūt mums ir jāmeklē pāris no tiem.
>> Un tā mēs joprojām tiekšanās ka vidējais lieta ir tuvu 1 vs
tuvu n, tāpēc varbūt, ka būs darbs.
Tātad, pieņemsim redzēt, kā tas varētu izstrādāt realitātē.
Un pieņemsim redzēt, ja varbūt mēs varam atklāt problēma, kas varētu notikt šeit.
>> Teiksim mēs hash Bart.
Tāpēc tagad mēs esam gatavojas palaist jaunu komplektu Stīgu caur hash funkciju,
un mēs palaist Bart caur hash funkcija, mēs hashcode 6.
Mēs to apskatīt, mēs redzam, ir 6 tukšs, tāpēc mēs varam likt Bart tur.
>> Tagad mēs hash Lisa un ka arī rada hashcode 6.
Nu tagad, ka mēs esam, izmantojot šo lineārs zondēšanas metodi mēs sāktu 6,
mēs redzam, ka 6. ir pilna.
Mēs nevaram likt Lisa 6. punktā.
Tātad, ja mēs ejam?
Ejam uz 7.
7 ir tukša, tā ka strādā.
Tātad pieņemsim likts Lisa tur.
>> Tagad mēs hash Homērs un mēs 7.
Labi labi mēs zinām, ka 7 ir pilna tagad, tāpēc mēs nevaram likt Homer tur.
So iesim līdz 8.
Vai 8 ir pieejama?
Jā, un 8 ir tuvu 7, tādēļ, ja mums ir jāsāk meklēt, mēs esam
nav nāksies iet pārāk tālu.
Un tāpēc pieņemsim nodot Homer pēc 8.
>> Tagad mēs hash Maggie un atgriež 3, paldies dievam
mēs esam spējīgi tikai likt Maggie tur.
Mums nav jādara kādu veida zondēšana par to.
Tagad mēs hash Marge, un Marge arī atgriež 6.
>> Nu 6 ir pilna, 7 ir pilna, 8 ir pilna, 9, labi paldies Dievam, 9 ir tukšs.
Es varu likt Marge pie 9.
Jau mēs varam redzēt, ka mēs sākam lai šo problēmu, kur tagad mēs esam
sāk stiept lietas veida no tālu prom no saviem hash kodiem.
Un ka teta 1, ka vidējais gadījums ir nemainīgs laiks,
sāk saņemt mazliet more-- sāk tendence nedaudz vairāk
uz teta n.
Mēs sākam zaudēt, ka priekšrocība hash tabulu.
>> Šī problēma, ka mēs tikko redzējām ir kaut kas ko sauc par klasteru.
Un, kas ir patiešām slikti par sakopojums ir tas, ka jums tagad
ir divi elementi, kas atrodas blakus puses tas padara to vēl vairāk iespējams,
Jums ir dubults iespēja, ka jūs gatavojas
vēl vienu sadursmi ar šo kopu,
un klasteru pieaugs par vienu.
Un jūs pastāvīgi aug un aug Jūsu iespēja, ka tā sadursmes.
Un galu galā tas ir tikpat slikts kā nav šķirošanas datus vispār.
>> Otra problēma, lai gan ir mums vēl, un līdz šim līdz šim punktam,
mēs esam tikko veida saprastu, kas hash tabula ir,
mums vēl ir tikai telpa 10 stīgas.
Ja mēs vēlamies turpināt hash pilsoņi Springfield,
mēs varam tikai iegūt 10 no tiem tur.
Un, ja mēs mēģinātu pievienot 11th vai 12, mums nav vieta, kur nodot tos.
Mēs varētu vienkārši vērpšanas ap apļi mēģinot atrast tukšu vietu,
un mēs varbūt iestrēdzis bezgalīga cilpa.
>> Tātad šāda veida aizdod idejas par kaut ko sauc ķēžu rādītāju.
Un tas ir tas, kur mēs ejam, lai panāktu saistītie saraksti atpakaļ uz attēla.
Ko darīt, ja tā vietā, lai uzglabātu tikko datu pati masīva,
katrs masīva elements varētu turēt vairākus gabalus datu?
Labi, ka nav jēgas, vai ne?
Mēs zinām, ka masīvs var tikai hold-- katru masīva elements
var būt tikai viena gabala Datu šīs datu tipu.
>> Bet ko tad, ka datu tips ir saistīts saraksts, vai ne?
Tātad, ko tad, ja katrs masīva elements bija
rādītāju uz galvas saistītā saraksta?
Un tad mēs varētu veidot tie saistīti saraksti
un augt tos patvaļīgi, jo saistīti saraksti ļauj
mums augt un sarauties daudz vairāk elastīgi nekā masīvs dara.
Tātad, ko tad mēs tagad izmanto, mēs sviras šo, labi?
Sākam augt šīs ķēdes no šiem masīvu vietās.
>> Tagad mēs varam fit bezgalīgs datu apjoms, vai nav bezgalīgs,
patvaļīga summa dati, mūsu hash tabulu
nekad nokļūšanu problēma sadursmes.
Mēs esam arī likvidēta kopu, ko darīt.
Un labi mēs zinām, ka tad, kad mēs ievietotu stājas saistīta sarakstā, ja jūs atceraties
no mūsu video par saistītiem sarakstiem, atsevišķi saistīti saraksti un divkārt saistīti saraksti,
tas ir pastāvīgs laiks operācija.
Mēs esam tikai pievienojot uz priekšu.
>> Un uzmeklēt, arī mēs zinām, kas uzmeklēt kādā saistīta sarakstā
var būt problēma, vai ne?
Mums ir jāmeklē tas no sākuma līdz beigām.
Nav nejauši piekļuve saistītajā sarakstā.
Bet, ja tā vietā, viena saistīta saraksts kur lookup būtu O n,
mums tagad ir 10, kas saistītas saraksti, vai 1000 saistīti saraksti,
tagad tas ir O n dalīts ar 10, vai O n dalīts ar 1000.
>> Un, kamēr mēs runājām teorētiski par sarežģītību
mēs ignorēt konstantes, reālajā pasaule šīs lietas tiešām svarīgi,
labi?
Mēs faktiski ievērosiet ka tas notiek
palaist 10 reizes ātrāk, vai 1000 reizes ātrāk,
jo mēs esam izplata viena gara ķēde pāri 1000 mazākām ķēdēm.
Un tā katru reizi, kad mums ir jāmeklē izmantojot kādu no šīm ķēdēm mēs varam
ignorēt 999 ķēdes mēs vienalga par, un tikai meklēt, ka viens.
>> Kas ir vidēji līdz būt 1000 reizes īsāks.
Un tā mēs joprojām esam sava veida noslieci uz šo vidējo gadījumā
būt pastāvīgu laiku, bet tikai tāpēc, ka mums ir piesaistot
dalot ar kādu milzīgu nemainīgu koeficientu.
Let 's redzēt, kā tas varētu tiešām izskatās gan.
Tātad tas bija hash tabulu mums bija pirms mēs pasludināja hash tabulu, kas
bija spēj uzglabāt 10 stīgas.
Mēs nebrauksim darīt vairs.
Mēs jau zinām, ierobežojumi šī metode.
Tagad mūsu hash tabulu, būs masīvs 10 mezgliem, norādes
vadītājiem saistītas sarakstiem.
>> Un tagad tas ir null.
Katrs no tiem 10 norādes ir nulle.
Tur nekas Mūsu hash tabulu tieši tagad.
>> Tagad sāksim likt dažus lietas šajā hash tabulu.
Un pieņemsim redzēt, kā šī metode ir gatavojas labumu mums mazliet.
Pieņemsim tagad hash Joey.
Mēs darbosies virkne Joey caur hash funkciju un mēs atgriežamies 6.
Nu ko mēs darām tagad?
>> Nu tagad strādā ar saistītiem sarakstiem, mēs nedarbojas ar masīviem.
Un, kad mēs strādājam ar saistītiem sarakstiem mēs
zinām, mums ir nepieciešams, lai sāktu dinamiski piešķirot telpas un ēkas ķēdes.
Tas ir sava veida how-- tie ir galvenais elementus veidot saistīts sarakstu.
Tātad pieņemsim dinamiski piešķirt telpas Joey,
un tad pieņemsim pievienot viņu uz ķēdi.
>> Tāpēc tagad meklēt to, ko mēs esam darījuši.
Kad mēs hash Joey mēs saņēmām hashcode 6.
Tagad rādītājs pie masīva vietā 6 norāda uz galvas saistītā saraksta
un šobrīd tas ir vienīgais no saistītā saraksta elements.
Un mezglu, kas saistīts saraksts ir Joey.
>> Tātad, ja mums ir nepieciešams, lai uzmeklētu Joey vēlāk, mēs vienkārši hash Joey atkal,
mēs iegūstam 6 vēlreiz, jo mūsu hash funkcija ir determinēti.
Un tad mēs sākam pie galvas no saistītā saraksta norādīja
līdz ar masīvu vietu 6, un mēs varam atkārtot
pāri, kas cenšas atrast Joey.
Un, ja mēs veidojam mūsu efektīvi hash tabulu,
un mūsu hash funkciju efektīvi izplatīt datus labi,
vidēji par katru no tiem, kas saistīti saraksti uz katra masīva vietā
būs 1/10 izmēru, ja mēs tikko bija to kā vienu milzīgu
saistīts saraksts ar visu tajā.
>> Ja mēs izplatīt, ka milzīgs saistīta saraksts pāri 10, kas saistīti saraksti
katrs saraksts būs 1/10 izmērs.
Un tādējādi 10 reizes ātrāk lai meklētu, izmantojot.
Tātad, pieņemsim darīt atkal.
Pieņemsim tagad hash Ross.
>> Un teiksim Ross, kad mēs to darām hash kodu mēs saņemam atpakaļ, ir 2.
Nu tagad mēs dinamiski piešķir jaunu mezglu, mēs ieliekam Ross šajā mezglā,
un tagad mēs sakām masīvs vieta 2, tā vietā, norādot uz null,
norāda uz galvas saistītais sarakstu, kuru vienīgais mezgls ir Ross.
Un mēs varam darīt vēl vienu reizi, mēs var hash Rachel un saņemt hashcode 4.
malloc jaunu mezglu, ielieciet Rachel in mezglu, un teikt masīvs vietu
4. tagad norāda uz galvas par saistītu sarakstu, kuras
Vienīgais elements, notiek, ir Rachel.
>> OK, bet to, kas notiek, ja mums ir sadursmes?
Let 's redzēt, kā mēs risinām sadursmes izmantojot atsevišķu Ķēžu metodi.
Pieņemsim hash Phoebe.
Mēs saņemam hashcode 6.
Pēc mūsu iepriekšējo piemēru mēs bijām tikko uzglabājot stīgas masīvā.
Tas bija problēma.
>> Mēs nevēlamies, lai clobber Joey, un mēs esam jau
redzams, ka mēs varam dabūt klasteru problēmas, ja mēs mēģinātu solis
caur un zonde.
Bet ko tad, ja mēs tikai veida ārstēt tas tāpat, vai ne?
Tas ir tāpat kā pievienojot elementu uz galvas saistītā saraksta.
Pieņemsim tikai malloc telpu Fēbes.
>> Mēs sakām Phoebe nākamais rādītājs punktus uz veco galvas saistītā saraksta,
un pēc tam 6 tikai norāda uz jaunais vadītājs saistīts sarakstā.
Un tagad izskatās, mēs esam mainījušies Phoebe in.
Tagad mēs varam saglabāt divas elementi ar hashcode 6,
un mums nav nekādu problēmu.
>> Tas ir diezgan daudz viss tur ir Virknējuma.
Un virknes intervāli ir noteikti metode, kas ir
būs visefektīvākais jums, ja jums ir uzglabātu datus hash tabulā.
Bet šī kombinācija bloki un saistīti saraksti
kopā, lai veidotu hash tabulu patiešām ievērojami uzlabo savu spēju
uzglabāt lielu datu apjomu, un ļoti ātri un efektīvi meklēt
caur šiem datiem.
>> Tur ir vēl viens datu struktūra, kas tur
ka pat varētu būt nedaudz labāk ziņā garantējot
ka mūsu ievietošana, dzēšana, un Uzmeklēt laiki ir vēl ātrāk.
Un mēs redzam, ka ar video valstīs.
Es esmu Doug Lloyd, tas ir CS50.