[موسیقی]
>> داگ لوید: در حال حاضر شما می دانم که بسیاری در مورد آرایه ها،
و شما می دانید که بسیاری در مورد لیست های پیوندی.
و ما بحث در مورد جوانب مثبت و منفی، ما
بحث که لیست های پیوندی می توانید بزرگتر و کوچکتر،
اما آنها را تا اندازه است.
آرایه ها خیلی بیشتر ساده به استفاده کنید، اما آنها به عنوان بسیار محدود است
به عنوان ما به مجموعه ای از اندازه آرایه در همان ابتدا
و پس از آن ما با آن گیر کرده است.
>> اما این، ما بسیار خسته همه از مباحث ما
در مورد لیست های پیوندی و آرایه ها.
یا ما باید؟
شاید ما می توانیم چیزی را انجام دهید حتی بیشتر خلاق.
و آن نوع از می آورد به این ایده از یک جدول هش.
>> بنابراین در یک جدول هش ما قصد داریم به تلاش ترکیب یک آرایه با یک لیست پیوندی.
ما در حال رفتن به مزایای استفاده از آرایه، مانند دسترسی تصادفی،
قادر بودن به فقط به آرایه عنصر 4 یا آرایه عنصر 8
بدون نیاز به تکرار در سراسر.
که بسیار سریع، درست است؟
>> اما ما همچنین می خواهم به داده های ما ساختار قادر به رشد و کوچک باشد.
ما لازم نیست، ما نمی می خواهم به محدود شود.
و ما می خواهم که قادر برای اضافه کردن و حذف چیزهای
به راحتی، که اگر شما به یاد، بسیار پیچیده با یک آرایه است.
و ما می توانیم این پاسخ چیز جدید یک جدول هش.
>> و اگر به درستی اجرا شود، ما در حال مرتب کردن بر اساس در نظر گرفتن
مزایای استفاده از هر دو داده ساختارهای شما در حال حاضر دیده می شود،
آرایه ها و لیست های پیوندی.
درج می توانید شروع به تمایل به سمت تتا، از مجموع 1
تتا ما واقعا مورد بحث نیست، اما تتا فقط در مورد به طور متوسط،
آنچه در واقع اتفاق خواهد افتاد.
شما همیشه به بدترین سناریو مورد،
و شما همیشه رفتن به بهترین حالت، پس چه
سناریوی به طور متوسط؟
>> خب یک درج متوسط به یک جدول هش
می توانید شروع به نزدیک شدن به زمان ثابت است.
و حذف می توانید نزدیک به زمان ثابت است.
و مراجعه می توانید نزدیک به زمان ثابت است.
That's-- ما یک داده ندارد ساختار در عین حال که می توانید انجام این کار،
و به همین ترتیب این در حال حاضر برای تلفن های موبایل مانند یک چیز بسیار بزرگ است.
ما واقعا کاهش ام معایب هر یک از خود را دارد.
>> برای دریافت این عملکرد ارتقاء هر چند، ما
نیاز به تجدید نظر چگونه اضافه کنید ما داده ها را به ساختار.
به طور خاص ما می خواهیم داده های خود را به ما بگویید
که در آن باید در ساختار است.
و اگر ما پس از آن نیاز به دیدن اگر آن را در این ساختار، اگر ما نیاز به پیدا کردن آن،
ما می خواهیم به دادهها نگاه دوباره و به طور موثر قادر به،
با استفاده از داده ها، به طور تصادفی آن دسترسی داشته باشید.
فقط با نگاه کردن به داده ما باید
ایده که در آن دقیقا ما رفتن به پیدا کردن آن را در جدول هش.
>> در حال حاضر حرکت نزولی از یک رشته هش جدول است که آنها واقعا
خیلی بد در سفارش و یا مرتب سازی داده ها.
و در واقع، اگر شما شروع به برای استفاده از آنها به سفارش و یا مرتب سازی بر
شما داده همه از دست بدهند مزایای شما قبلا
از نظر درج و حذف بود.
ساعت هم نزدیک تر می شود به تتا از n، و ما اساسا
پسرفت به یک لیست پیوندی.
و بنابراین ما فقط مایل به استفاده هش جداول اگر ما در مورد مراقبت از
آیا داده های طبقه بندی شده اند است.
برای زمینه که در شما آنها را در CS50 استفاده
شما احتمالا نمی که داده طبقه بندی شده اند است.
>> بنابراین یک جدول هش ترکیبی است دو قطعه مجزا
که ما با آن آشنا هستید.
برای اولین بار یک تابع است که ما معمولا یک تابع هش پاسخ.
و تابع هش است برای رفتن به بازگشت برخی از عدد صحیح غیر منفی، که
ما معمولا یک hashcode پاسخ، خوب است؟
قطعه دوم آرایه ای است، که قادر به ذخیره سازی داده ها از نوع ما در
می خواهم به جای به ساختار داده ها.
ما بر روی دست نگه دارند مرتبط لیست عنصر برای
و فقط با اصول اولیه یک شروع جدول هش برای دریافت سر خود را در اطراف آن،
و پس از آن شاید که توی ضربه ذهن خود را کمی هنگامی که ما
ترکیب آرایه و لیست های پیوندی با هم.
>> ایده اصلی هر چند این است که ما به برخی از داده ها.
ما اجرای که داده ها از طریق تابع هش.
و به این ترتیب داده های پردازش شده است و تف کردن یک عدد، OK؟
و سپس با شماره ما فقط ذخیره داده ها
ما می خواهیم برای ذخیره در آرایه در آن محل.
بنابراین برای مثال ما شاید این جدول هش از رشته ها.
آن را به 10 عنصر در آن، پس ما می توانیم 10 رشته در آن جا داد.
>> بیایید می گویند ما می خواهیم به هش جان.
بنابراین جان به عنوان داده های ما خواهید برای وارد کردن به این جدول هش جایی.
که در آن ما آن را قرار داده است؟
خوب به طور معمول با آرایه تا کنون ما احتمالا
آن را در محل آرایه 0 قرار داده است.
اما در حال حاضر ما باید این تابع هش جدید.
>> و اجازه دهید بگویم که ما اجرا جان از طریق این تابع هش
و آن را تف 4.
خوب است که در آن ما به رفتن به خواهید برای قرار دادن جان.
ما می خواهیم به قرار دادن جان در محل آرایه 4، چرا که اگر ما هش جان again--
اجازه دهید بعد می گویند ما می خواهید برای جستجو و ببینید
اگر جان در این هش وجود دارد table-- همه ما باید انجام دهیم
است آن را از طریق هش همان اجرا تابع، بدست آوردن شماره 4،
و قادر به پیدا کردن جان بلافاصله در ساختار داده است.
این خیلی خوب است.
>> بیایید می گویند ما در حال حاضر انجام این کار دوباره، ما می خواهیم به هش پل.
ما می خواهیم به اضافه پل به این جدول هش.
اجازه دهید بگویم که این زمان ما اجرا پل از طریق تابع هش،
hashcode است که تولید 6 است.
خوب در حال حاضر ما می توانیم پل قرار در محل آرایه 6.
و اگر ما نیاز به نگاه کردن آیا پل در این جدول هش،
همه ما باید انجام دهیم این است که اجرای پل از طریق تابع هش دوباره
و ما در حال رفتن به 6 دوباره.
>> و سپس ما فقط نگاه در محل آرایه 6.
است پل وجود دارد؟
اگر چنین است، او در جدول هش است.
است پل وجود ندارد؟
او در جدول هش است.
این بسیار سر راست است.
>> در حال حاضر چگونه یک تابع هش تعریف می کنید؟
خب واقعا هیچ محدودیتی برای وجود دارد تعدادی از توابع هش امکان پذیر است.
در واقع تعدادی از وجود دارد واقعا، آنهایی که واقعا خوب بر روی اینترنت.
یک تعداد از واقعا وجود دارد، آنهایی که واقعا بد در اینترنت می باشد.
آن را نیز بسیار آسان به یک بد.
>> بنابراین چه چیزی باعث شده تا خوب تابع هش، درست است؟
خب یک تابع هش خوب باید استفاده از تنها داده های در حال درهم،
و همه داده های در حال درهم.
بنابراین ما نمی خواهیم به استفاده از anything-- ما هیچ چیز را ترکیب نمی
دیگری به غیر از داده ها.
و ما می خواهیم برای استفاده از تمام داده ها.
ما نمی خواهیم که فقط با استفاده از یک قطعه از آن، ما می خواهیم برای استفاده از تمام آن را.
یک تابع هش باید همچنین قطعی است.
معنی آن چیست؟
خوب به این معنی است که هر زمان که ما تصویب همان قطعه دقیق از داده ها
به تابع هش ما همیشه دریافت hashcode همان است.
اگر من عبور جان به تابع هش من خارج 4.
من باید قادر به انجام این کار می تواند 10،000 زمان و من همیشه می خواهید 4.
بنابراین هیچ اعداد تصادفی به طور موثر را می توان در هش ما نقش دارند tables--
در توابع هش ما است.
>> یک تابع هش نیز باید یکنواخت توزیع داده ها.
اگر هر بار که اطلاعات شما اجرا از طریق تابع هش شما در hashcode 0 را دریافت کنید،
که احتمالا نه چندان بزرگ، درست است؟
شما احتمالا به بزرگ می خواهند طیف وسیعی از کد هش.
همچنین چیزهایی می تواند به گسترش از سراسر جدول.
و همچنین آن را بزرگ خواهد بود اگر واقعا داده های مشابه، مانند جان و جاناتان،
شاید بیرون پخش شد به وزن مکان های مختلف در جدول هش.
این امر می تواند یک مزیت خوب است.
>> در اینجا یک مثال از یک تابع هش است.
من این یکی نوشت: تا پیش از آن.
این یک خصوص تابع هش خوب
به دلایل است که واقعا نمی تحمل رفتن به در حال حاضر.
اما شما ببینید که چه خبر است اینجا؟
به نظر می رسد مانند ما در حال تعریف متغیر به نام جمع و تنظیم آن را برابر با 0.
و پس از آن ظاهرا من انجام کاری تا زمانی که strstr [J] برابر نیست
به بک اسلش 0.
چه من انجام وجود دارد؟
>> این است که اساسا فقط یک راه اجرای [؟ STRL؟]
و تشخیص زمانی که شما در پایان از رشته رسیده است.
بنابراین من به واقع ندارد محاسبه طول رشته،
من فقط با استفاده وقتی که من ضربه بک اسلش 0 شخصیت من می دانم
من از پایان رشته رسیدهاید.
و سپس من رفتن به نگه داشتن تکرار از طریق این رشته،
اضافه کردن strstr [J] به طور خلاصه، و پس از آن در پایان روز به بازگشت به جمع MOD
HASH_MAX.
>> در واقع تمام این هش تابع انجام شده است اضافه کردن
تمام ارزش ASCII از رشته من، و سپس آن را
بازگشت برخی hashcode کامپیوتر های HASH_MAX.
این احتمالا به اندازه آرایه من، درست است؟
من نمی خواهم به گرفتن هش کد اگر آرایه من است اندازه 10،
من نمی خواهم به گرفتن کد رشته هش از 11، 12،
13، من می توانم همه چیز را به قرار داده نشده آن مکان از آرایه،
خواهد بود که غیر قانونی است.
من می خواهم یک گسل تقسیم رنج می برند.
>> حالا در اینجا یکی دیگر از سریع کنار است.
به طور کلی شما احتمالا به رفتن نیست می خواهم برای نوشتن توابع هش خود را.
این است که در واقع یک بیت از یک هنر است، نه یک علم است.
و در بسیاری که می رود به آنها وجود دارد.
اینترنت، مثل من گفت، کامل است از توابع هش واقعا خوب است،
و شما باید به اینترنت برای استفاده پیدا توابع هش دلیل آن را واقعا
فقط نوع غیر ضروری اتلاف وقت خود را ایجاد کنید.
>> شما می توانید آنهایی که ساده ارسال برای آزمایش.
اما زمانی که شما در واقع در حال رفتن به شروع هش کردن داده ها و ذخیره سازی آن
به یک جدول هش شما احتمالا می خواهید
برای استفاده از برخی تابع است که ایجاد شد برای شما، که در اینترنت وجود دارد.
اگر شما فقط مطمئن شوید که به استناد منابع خود را.
هیچ دلیلی برای وجود دارد خوشه چینی کردن هر چیزی در اینجا.
>> جامعه علم کامپیوتر است قطعا در حال رشد، و واقعا ارزش
منبع باز، و این واقعا مهم به استناد منابع خود را به طوری که مردم
می توانید برای دریافت اسناد کار است که آنها
انجام به نفع جامعه است.
بنابراین همیشه sure-- شود و نه فقط برای هش
توابع، اما به طور کلی زمانی که شما استفاده از کد از منبع خارج از،
همیشه منبع خود را استناد.
دادن اعتبار به شخصی که برخی از کار، بنابراین شما لازم نیست که.
>> OK بنابراین اجازه دهید این دوباره جدول هش برای یک ثانیه.
این جایی است که ما به سمت چپ بعد از ما قرار داده
جان و پل به این جدول هش.
آیا شما یک مشکل است؟
شما ممکن است دو را مشاهده کنید.
اما به طور خاص، شما باید انجام دهید این مشکل ممکن را ببینید.
>> اگر من هش رینگو، و آن معلوم است که پس از پردازش
که داده ها از طریق تابع هش رینگو همچنین تولید hashcode 6.
من در حال حاضر داده ها در کردم محل آرایه hashcode-- 6.
پس از آن احتمالا برای رفتن به یک بیت از یک مشکل برای من در حال حاضر، درست است؟
>> ما این را یک برخورد.
و برخورد رخ می دهد که دو قطعه از داده ها از طریق هش همان اجرا
عملکرد تابع hashcode است.
احتمالا ما هنوز هم می خواهید به دریافت هر دو قطعه از داده ها را به جدول هش،
در غیر این صورت ما نمی شود در حال اجرا رینگو خودسرانه از طریق تابع هش.
ما احتمالا می خواهید برای دریافت رینگو به که آرایه.
>> چگونه ما آن را انجام هر چند، اگر او و پل هر دو عملکرد hashcode 6؟
ما نمی خواهیم به بازنویسی پل، ما می خواهیم به پل وجود دارد بیش از حد.
بنابراین ما نیاز به پیدا کردن یک راه برای به دست آوردن عناصر به جدول هش که
هنوز هم سریع ما را حفظ درج و سریع نگاه کردن.
و یک راه برای مقابله با آن است به انجام چیزی به نام کاوش خطی.
>> با استفاده از این روش اگر ما یک برخورد، خب، چه کار کنیم؟
خوب ما می توانید او را در محل آرایه قرار داده نشده 6، و یا هر hashcode ایجاد شد،
اجازه دهید او را در hashcode به علاوه 1 قرار داده است.
و در صورتی که اجازه کامل او در hashcode به علاوه 2 قرار داده است.
بهره مند از این که اگر او نمی دقیقا همان جایی که ما فکر می کنیم او است،
و ما باید برای شروع به جستجو، شاید ما لازم نیست که به بیش از حد.
شاید ما مجبور به جستجو همه عناصر N از جدول هش.
شاید ما باید به جستجو یک زن و شوهر از آنها.
>> و بنابراین ما هنوز هم نسبت به رسیدگی که به طور متوسط ​​مورد نزدیک شدن به 1 مقابل
نزدیک به N، تا شاید که کار می کنند.
بنابراین اجازه دهید که چگونه این را ببینید ممکن است در واقعیت کار کند.
و بیایید ببینید که اگر ما می توانیم تشخیص شاید مشکل این است که در اینجا ممکن است رخ دهد.
>> بیایید می گویند ما هش بارت.
بنابراین در حال حاضر ما در حال رفتن به اجرای یک مجموعه جدید از رشته از طریق تابع هش،
و ما بارت از طریق هش اجرا تابع، ما hashcode 6.
ما را نگاه کنیم، می بینیم 6 خالی، بنابراین ما می توانیم بارت وجود دارد قرار داده است.
>> در حال حاضر ما هش لیزا و همچنین تولید hashcode 6.
خوب در حال حاضر که ما در حال استفاده از این خطی روش ما در 6 شروع پروبینگ،
ما می بینیم که 6 پر است.
ما می توانیم لیزا در 6 قرار داده است.
پس از کجا می رویم؟
بیایید تا 7.
7 خالی، به طوری که کار می کند.
بنابراین اجازه دهید لیزا وجود دارد.
>> در حال حاضر ما هش هومر و ما 7.
OK خوبی می دانیم که 7 کامل در حال حاضر، بنابراین ما می توانیم هومر قرار داده نشده است.
بنابراین اجازه دهید به 8 است.
است 8 در دسترس است؟
آره، و نزدیک به 7 8 است، بنابراین اگر ما شروع به جستجو ما
قصد ندارم به به بیش از حد.
و بنابراین اجازه دهید هومر را در 8.
>> در حال حاضر ما هش مگی و را برمی گرداند 3، خدا را شکر
ما قادر به فقط با قرار دادن مگی وجود دارد.
ما لازم نیست که برای انجام هر گونه مرتب کردن بر اساس کاوش برای آن است.
در حال حاضر ما هش حاشیه، و حاشیه نیز باز می گردد 6.
>> خوب 6 پر است، پر است 7، 8 پر است، 9، همه حق خدا را شکر، 9 خالی است.
من می توانم حاشیه در 9 قرار داده است.
در حال حاضر ما می توانید ببینید که ما در حال شروع به این مشکل که در آن در حال حاضر ما
شروع به کشش همه چیز نوع از دور از کد هش است.
و تتا 1، که به طور متوسط مورد بودن زمان ثابت،
شروع به گرفتن یک کمی more-- شروع به تمایل کمی بیشتر
به سمت تتا از n.
ما در حال شروع به از دست دادن که استفاده از جداول هش.
>> این مشکل این است که ما فقط دیدم چیزی به نام خوشه است.
و آنچه واقعا در مورد بد خوشه بندی است که هنگامی که شما در حال حاضر
دو عنصر که طرف توسط سمت آن را می سازد آن را حتی بیشتر احتمال دارد،
شما دو برابر شانس، که شما در حال رفتن
به یکی دیگر از برخورد با خوشه ای،
و خوشه توسط یک رشد می کنند.
و شما را به رشد و در حال رشد احتمال شما را از داشتن یک برخورد.
و در نهایت آن را فقط به عنوان بد عنوان مرتب سازی نه داده در همه.
>> مشکل دیگر هر چند که ما است هنوز هم، و تا کنون تا به این نقطه،
ما فقط از شده درک آنچه یک جدول هش،
ما هنوز هم تنها 10 اتاق برای رشته داشته باشد.
اگر ما می خواهیم به به هش شهروندان اسپرینگفیلد،
ما فقط می توانیم 10 نفر از آنها را در وجود دارد.
و اگر ما را امتحان کنید و یا اضافه کردن یک 11TH تاریخ 12th، ما یک محل برای قرار دادن آنها ندارد.
ما فقط می تواند در حال چرخش به دور محافل تلاش برای پیدا کردن یک نقطه خالی،
و ما شاید گیر در یک حلقه بی نهایت.
>> بنابراین این نوع از آشنایی به این ایده از چیزی به نام زنجیری.
و این جایی است که ما قصد داریم به لیست های پیوندی را به تصویر.
چه می شود اگر به جای ذخیره سازی تنها اطلاعات خود را در آرایه،
هر عنصر از آرایه توانست چند داده را نگه دارید؟
خوب است که معنی ندارد، درست است؟
ما می دانیم که یک آرایه می تواند تنها hold-- هر عنصر از یک آرایه
می تواند تنها یک قطعه را نگه دارید از اطلاعات مربوط به آن نوع داده.
>> اما اگر که نوع داده یک لیست پیوندی است، درست است؟
بنابراین اگر هر عنصر از آرایه بود
یک اشاره گر به سر از یک لیست پیوندی؟
و ما می توانیم ساخت کسانی که لیست های پیوندی
و رشد آنها را خودسرانه، چون اجازه می دهد لیست های پیوندی
ما را به رشد و کوچک خیلی بیشتر انعطاف پذیری از یک آرایه می کند.
بنابراین اگر ما در حال حاضر استفاده کنید، ما این اهرم، درست است؟
ما شروع به رشد این زنجیره از این مکان آرایه.
>> در حال حاضر ما می توانید بی نهایت جا مقدار داده ها، و یا بی نهایت نیست،
هر مقدار دلخواهی داده ها، به جدول هش ما
تا کنون که بدون در حال اجرا را مشکل برخورد.
ما همچنین حذف خوشه بندی با انجام این کار.
و به خوبی می دانیم که وقتی ما وارد به یک لیست پیوندی، اگر شما به خاطر
از ویدیو های ما در لیست های پیوندی، به تنهایی لیست های پیوندی و لیست مضاعف مرتبط،
این یک عملیات زمان ثابت است.
ما فقط اضافه کردن به جلو است.
>> و برای نگاه کردن، خوب ما نمی دانیم که نگاه کردن در یک لیست پیوندی
می تواند یک مشکل، درست است؟
ما به جستجو از طریق آن را از ابتدا تا انتها.
هیچ تصادفی وجود دارد دسترسی در یک لیست پیوندی.
اما اگر به جای داشتن یک مرتبط لیست که در آن مراجعه می O از n باشد،
ما در حال حاضر 10 لیست های پیوندی، یا 1،000 لیست های پیوندی،
در حال حاضر آن O از N تقسیم بر 10، و یا O از N تقسیم 1،000.
>> و در حالی که ما صحبت می کردند از لحاظ نظری در مورد پیچیدگی
ما ثابت نادیده، در واقعی جهان این چیزها در واقع ماده،
درست؟
ما در واقع متوجه خواهید شد که این اتفاق می افتد
به اجرا 10 برابر سریع تر، و یا 1،000 بار سریع تر،
چرا که ما توزیع یکی از طولانی زنجیره ای در سراسر 1،000 زنجیره های کوچکتر.
و به این ترتیب هر زمان که ما به جستجو از طریق یکی از آن زنجیر ما می توانیم
چشم پوشی از 999 زنجیره ما اهمیتی نمی در مورد، و فقط جستجو که یکی.
>> که است که به طور متوسط ​​به شود 1،000 بار کوتاه تر است.
و بنابراین ما هنوز هم هستند مرتب کردن بر اساس رسیدگی نسبت به این مورد به طور متوسط
بودن زمان ثابت، اما فقط به این دلیل که ما در حال اعمال نفوذ
تقسیم توسط برخی از عوامل بزرگ ثابت است.
بیایید ببینید که چگونه این ممکن است در واقع نگاه کرد.
بنابراین این جدول هش ما بود قبل از جدول هش ما اعلام کرد که
قادر به ذخیره سازی 10 رشته بود.
ما قصد داریم برای انجام این کار نیست.
ما در حال حاضر می دانیم که محدودیت آن روش است.
در حال حاضر جدول هش ما را برای رفتن به آرایه ای از 10 گره، اشاره گر
به سر از لیست های پیوندی.
>> و در حال حاضر آن را تهی.
هر یک از این 10 اشاره گر تهی است.
هیچ چیز در ما جدول هش در حال حاضر.
>> حالا اجازه دهید شروع به قرار دادن برخی از چیزها را به این جدول هش.
و بیایید ببینید که چگونه این روش این است رفتن به نفع ما یک کمی.
اکنون بیایید هش جوی.
ما در رشته جوی از طریق شما را اجرا خواهد کرد یک تابع هش و ما بازگشت 6.
خب چه چیزی ما در حال حاضر؟
>> خوب در حال حاضر با لیست های پیوندی کار، ما با آرایه کار نمی کند.
و هنگامی که ما در حال کار با ما لیست های پیوندی
می دانیم که ما نیاز به شروع به صورت پویا تخصیص فضای ساختمان و زنجیر.
که مرتب سازی بر اساس how-- کسانی هستند که هسته عناصر ساخت یک لیست پیوندی.
بنابراین اجازه دهید به صورت پویا اختصاص فضا برای جوی،
و سپس اجازه دهید او را به زنجیره اضافه کنید.
>> بنابراین در حال حاضر نگاه آنچه که ما انجام داده ایم.
هنگامی که ما هش جوی ما در hashcode 6 است.
در حال حاضر در محل اشاره گر آرایه 6 اشاره به سر از یک لیست پیوندی،
و در حال حاضر آن را تنها عنصر از یک لیست پیوندی.
و گره در لیست پیوندی جوی است.
>> بنابراین اگر ما نیاز به نگاه کردن جوی بعد، ما فقط جوی هش دوباره،
ما 6 بار دیگر به دلیل ما تابع هش قطعی است.
و سپس ما در شروع به سر از لیست پیوندی اشاره
به محل آرایه 6، و ما می توانیم تکرار
که در سراسر تلاش برای پیدا کردن جوی.
و اگر ما ساخت ما جدول هش به طور موثر،
و تابع هش ما به طور موثر برای توزیع داده خوب،
به طور متوسط ​​هر یک از کسانی که در ارتباط لیست در هر مکان آرایه
خواهد بود 1/10 اندازه اگر ما فقط آن را به عنوان یک بزرگ بود
لیست پیوندی با همه چیز در آن است.
>> اگر ما توزیع است که بزرگ مرتبط لیست 10 لیست های پیوندی در سراسر
هر یک از لیست خواهد 1/10 اندازه.
و به این ترتیب 10 برابر سریعتر برای جستجو از طریق.
بنابراین اجازه دهید این کار را دوباره انجام.
اکنون بیایید هش راس.
>> و اجازه دهید بگویم راس، زمانی که ما این کار را کد هش ما تماس 2 است.
خوب در حال حاضر ما به صورت پویا اختصاص گره جدید، ما در راس آن گره قرار داده است،
و ما اکنون می گویند مکانهای آرایه 2، به جای اشاره به تهی،
اشاره به سر یک مرتبط لیست که تنها گره راس است.
و ما می توانیم این را یک بار دیگر انجام دهید، ما می توانید راشل هش و hashcode 4.
از malloc یک گره جدید، قرار دادن راشل در گره، و می گویند یک محل آرایه
4 در حال حاضر به سر اشاره از یک لیست پیوندی که
تنها عنصر اتفاق می افتد به راشل.
>> OK اما اگر ما یک برخورد؟
بیایید ببینید که چگونه ما رسیدگی برخورد با استفاده از روش زنجیره جداگانه.
بیایید هش قمر.
ما باید با hashcode 6.
در مثال قبلی ما ما فقط ذخیره سازی رشته در آرایه.
این یک مشکل بود.
>> ما نمی خواهیم به کتک زدن جوی و ما در حال حاضر
دیده می شود که ما می توانیم برخی خوشه گرفتن مشکلات اگر ما سعی می کنیم و گام به گام
از طریق و پروب.
اما اگر ما فقط نوع درمان این همان راه، درست است؟
این درست مثل اضافه کردن یک عنصر به سر از یک لیست پیوندی.
بیایید فضا فقط از malloc برای قمر.
>> ما می گویند نقطه اشاره گر قمر به سر های قدیمی از لیست پیوندی،
و سپس 6 فقط به نقاط رئیس جدید لیست پیوندی.
و در حال حاضر نگاه کنید، ما قمر در تغییر است.
ما هم اکنون می توانید دو فروشگاه عناصر با hashcode 6،
و ما هیچ مشکلی ندارد.
>> که تقریبا همه است به زنجیره وجود دارد.
و زنجیری است که قطعا روش که
رفتن به ترین برای شما اگر موثر شما در حال ذخیره سازی داده ها در یک جدول هش.
اما این ترکیب از آرایه ها و لیست های پیوندی
هم به صورت یک جدول هش واقعا به طور چشمگیری بهبود توانایی خود را
برای ذخیره مقادیر زیادی از داده ها و بسیار به سرعت و کارآمد جستجو
از طریق آن داده است.
>> هنوز هم یکی بیشتر وجود دارد ساختار داده ها در خارج وجود دارد
که حتی ممکن است کمی باشد از نظر تضمین بهتر
که ما درج، حذف، و نگاه کردن بار هستند حتی سریع تر.
و خواهیم دید که در یک ویدیو در تلاش می کند.
من داگ لوید هستم، این CS50.