[השמעת מוסיקה] דאג LLOYD: עד עכשיו אתה יודע הרבה על מערכים, ואתה יודע הרבה על רשימות מקושרות. ויש לנו לדון ב יתרונות וחסרונות, יש לנו דנתי שחיברו רשימות יכול לקבל גדול יותר וקטן יותר, אבל הם תופסים יותר גודל. מערכים הם הרבה יותר פשוט ל להשתמש, אבל הם מגבילים באותה מידה כפי שאנו צריכים להגדיר את הגודל של המערך ממש בהתחלה ואז אנחנו תקועים עם זה. 

אבל זה, יש לנו פחות או יותר מיצה את כל הנושאים שלנו על רשימות ומערכים קשורים. או שיש לנו? אולי אנחנו יכולים לעשות משהו אפילו יותר יצירתיים. וזה סוג של משאילה הרעיון של שולחן חשיש. 

אז בטבלת חשיש אנחנו הולכים לנסות לשלב מערך עם רשימה מקושרת. אנחנו הולכים לקחת את היתרונות של המערך, כמו גישה אקראית, יכולת פשוט ללכת למערך אלמנט 4 או מערך אלמנט 8 מבלי לחזר על פני. זה די מהר, נכון? 

אבל אנחנו גם רוצים שנהיה לנו נתונים מבנה תוכל לגדול ולהתכווץ. אנחנו לא צריכים, אנחנו לא רוצה להיות מוגבל. ואנחנו רוצים להיות מסוגלים כדי להוסיף ולהסיר דברים מאוד בקלות, שאם אתה זוכר, הוא מאוד מורכב עם מערך. ואנחנו יכולים לקרוא לזה דבר חדש טבלת חשיש. 

ואם מיושם כהלכה, אנחנו סוג של לוקחים היתרונות של שניהם נתונים מבנים שכבר ראו, מערכים ורשימות מקושרות. הכנסה יכולה להתחיל נוטה לכיוון של תטא 1. תטא אנחנו לא באמת דנו, אבל תטא הוא רק המקרה הממוצע, מה בעצם הולך לקרות. אתה תמיד לא הולך יש תרחיש המקרה הגרוע ביותר, ואתה לא תמיד הולך לי במקרה הטוב, אז מה התרחיש הממוצע? 

ובכן הכנסה ממוצעת לשולחן חשיש יכול להתחיל להתקרב לזמן קבוע. ומחיקה יכולה לקבל לסגור לזמן קבוע. ובדיקה יכולה לקבל לסגור לזמן קבוע. That's-- אין לנו נתונים מבנה עדיין שיכול לעשות את זה, ואז זה כבר נשמע כמו דבר די גדול. באמת אנחנו כבר מיתנו חסרונות של כל אחת מעצמו. 

כדי לקבל ביצועים זה שדרוג אם כי, אנו צריך לחשוב מחדש איך אנו מוסיפים נתונים לתוך המבנה. במיוחד שאנחנו רוצים המידע עצמו כדי לספר לנו איפה שהוא צריך ללכת במבנה. ואם אנחנו אז צריכים לראות אם זה ב המבנה, אם אנחנו צריכים למצוא אותו, אנחנו רוצים להסתכל על הנתונים שוב ונוכל ביעילות, תוך שימוש בנתונים, באופן אקראי לגשת אליו. רק מלהסתכל על הנתונים שאנו צריכים רעיון של איפה בדיוק אנחנו הולך למצוא אותו בשולחן החשיש. 

עכשיו החסרון של חשיש שולחן הוא שהם באמת די רע בהזמנה או במיון נתונים. ולמעשה, אם אתה מתחיל להשתמש בם כדי להזמין או סוג הנתונים שאתה מאבד את כל יתרונותיך בעבר היה במונחים של הכנסה ומחיקה. הזמן הופך להיות קרוב יותר ל תטא של n, ויש לנו בעצם נסוג לרשימה מקושרת. וכך אנחנו רוצים רק להשתמש חשיש שולחנות אם לא אכפת לנו על אם הנתונים ממוינים. להקשר שבו אתה משתמש בם בCS50 כנראה לא אכפת לך כי הנתונים ממוינים. 

אז שולחן חשיש הוא שילוב משני חלקים נפרדים שבה אנו מכירים. הראשון היא פונקציה, ש אנחנו בדרך כלל קוראים לפונקצית חשיש. ושפונקצית החשיש הולכת להחזיר חלק מספר שלם שאינו שלילי, ש אנחנו בדרך כלל קוראים hashcode, בסדר? החתיכה השנייה היא מערך, שהוא מסוגלים נתוני אחסון שלנו הסוג רוצה למקם במבנה נתונים. אנחנו לדחות את קשור אלמנט רשימה לעת עתה ופשוט להתחיל עם היסודות של חשיש שולחן כדי לקבל את הראש שלך סביבו, ואז אולי לפוצץ דעתך קצת כש לשלב מערכים ורשימות קישור יחד. 

הרעיון הבסיסי אם כי הוא שאנחנו לוקחים חלק מנתונים. אנחנו רצים נתונים שדרך פונקצית החשיש. וכך הנתונים מעובדים וזה יורק את מספר, בסדר? ולאחר מכן עם מספר ש אנחנו רק לאחסן את הנתונים אנחנו רוצים לאחסן ב מערך במיקום זה. כך למשל יש לנו אולי שולחן חשיש זה של מחרוזות. יש לו 10 אלמנטים בזה, כל כך אנחנו יכולים להתאים 10 מיתרים בזה. 

נניח שאנחנו רוצים חשיש ג'ון. אז ג'ון כנתונים שאנחנו רוצים להכניס לשולחן חשיש זה איפשהו. איפה אנחנו שמים את זה? ובכן בדרך כלל עם מערך עד כה אנחנו כנראה היה לשים אותו במיקום מערך 0. אבל עכשיו יש לנו פונקצית חשיש חדשה. 

ונניח שאנחנו רצים ג'ון באמצעות פונקצית חשיש זה וזה יורק את 4. טוב, זה שבו אנו נמצאים הולך רוצה לשים ג'ון. אנחנו רוצים לשים את ג'ון במיקום מערך 4, כי אם חשיש ג'ון again-- נניח מאוחר יותר רוצה לחפש ולראות אם ג'ון קיים בחשיש זה table-- כל מה שאנחנו צריכים לעשות הוא להפעיל אותו דרך אותו החשיש פונקציה, תקבל את מספר 4, ותוכל למצוא את ג'ון מייד במבנה הנתונים שלנו. זה די טוב. 

בואו נגיד שעכשיו אנחנו עושים את זה שוב, אנחנו רוצים חשיש פול. אנחנו רוצים להוסיף פול לשולחן חשיש זה. בואו נגיד שזה זמן אנחנו רצים פול באמצעות פונקצית החשיש, hashcode שנוצר הוא 6. ובכן עכשיו אנחנו יכולים לשים פול במיקום המערך 6. ואם אנחנו צריכים להסתכל אם פול הוא בטבלת חשיש זה, כל מה שאנחנו צריכים לעשות הוא להפעיל את פול באמצעות פונקצית החשיש שוב ואנחנו הולכים לקבל 6 שוב. 

ואז אנחנו פשוט להסתכל במיקום מערך 6. האם פול שם? אם כן, הוא בשולחן החשיש. האם פול לא שם? הוא לא בשולחן החשיש. זה די פשוט. 

עכשיו איך אתה מגדיר פונקצית חשיש? ובכן באמת אין גבול ל מספר פונקציות חשיש אפשריים. למעשה יש מספר ממש, ממש טובים אלה באינטרנט. יש מספר ממש, ממש רעים אלה באינטרנט. זה גם די קל כדי לכתוב רע. 

אז מה עושה את טוב פונקצית חשיש, נכון? ובכן פונקצית חשיש טובה צריכה להשתמש רק בנתונים שhashed, ואת כל הנתונים שhashed. אז אנחנו לא רוצים להשתמש anything-- אנחנו לא לשלב כל דבר מלבד נתונים אחר. ואנחנו רוצים להשתמש בכל הנתונים. אנחנו לא רוצים רק כדי להשתמש בפיסה שלו, אנחנו רוצים להשתמש בכל זה. פונקצית חשיש צריך גם להיות דטרמיניסטי. מה הכוונה? ובכן זה אומר שכל פעם שאנחנו עובר בדיוק את אותו פיסת המידע לפונקצית החשיש אנחנו תמיד לצאת באותו hashcode. אם אני עובר לג'ון פונקצית חשיש אני יוצא 4. אני צריך להיות מסוגל לעשות את זה 10,000 פעמים ואני תמיד מקבלים 4. אז לא מספרים אקראיים ביעילות יכול להיות מעורב בהחשיש tables-- בפונקציות החשיש שלנו. 

פונקצית חשיש גם צריכה אחיד להפיץ נתונים. אם בכל פעם שאתה מפעיל באמצעות נתונים פונקצית חשיש אתה מקבל hashcode 0, זה כנראה לא כל כך גדול, נכון? אתה כנראה רוצה גדול מגוון של קודי חשיש. כמו כן ניתן להפיץ דברים מתוך לאורך השולחן. וגם זה יהיה נהדר אם באמת נתונים דומים, כמו ג'ון ויונתן, אולי היו פרושים לשקול מקומות שונים בשולחן החשיש. זה יהיה יתרון נחמד. 

הנה דוגמא של פונקצית חשיש. אני כתבתי את זה אחד מוקדם יותר. זה לא במיוחד פונקצית חשיש טובה מסיבות שלא ממש לשאת הולכים לעכשיו. אבל אתה רואה מה קורה כאן? זה נראה כמו שאנחנו מכריזים על משתנים נקרא סכום והגדיר אותו שווה 0. ולאחר מכן, ככל הנראה, שאני עושה משהו כל עוד strstr [י] הוא לא שווה ללוכסן 0. מה אני עושה שם? 

זה בעצם רק עוד דרך של יישום [? strl?] וגילוי כאשר יש לך הגיע לסוף המחרוזת. אז לא צריך אני ממש לחשב את האורך של המחרוזת, אני רק משתמש כאשר אני מכה קו נטוי 0 דמות שאני יודע אני כבר הגעתי לסוף המחרוזת. ואז אני הולך לשמור iterating דרך מחרוזת ש, הוספת strstr [י] לסיכום, ולאחר מכן ב סופו של היום הולך לחזור mod הסכום HASH_MAX. 

בעיקרון כל חשיש זה הפונקציה עושה היא הוספה עד כל ערכי ASCII של המחרוזת שלי, ואז זה חוזר כמה hashcode modded ידי HASH_MAX. זה כנראה הגודל של המערך שלי, נכון? אני לא רוצה להיות מקבל חשיש קודים אם המערך שלי הוא בגודל 10, אני לא רוצה להיות מקבל קודים את חשיש 11, 12, 13, אני לא יכול לשים את הדברים ב אלה מקומות של המערך, זה יהיה בלתי חוקי. הייתי סובל אשמת פילוח. 

עכשיו הנה עוד מהיר בצד. בדרך כלל אתה כנראה לא הולך רוצה לכתוב פונקציות חשיש משלך. זה בעצם קצת אמנות, לא מדע. ויש הרבה שהולך להם. האינטרנט, כמו שאמרתי, הוא מלא של פונקציות חשיש ממש טובות, ואתה צריך להשתמש באינטרנט ל למצוא פונקציות חשיש כי זה באמת רק סוג של מיותר בזבוז הזמן ליצור משלך. 

אתה יכול לכתוב פשוט אלה למטרות בדיקה. אבל כאשר אתה בעצם הולך להתחיל hashing נתונים ואחסונו לשולחן חשיש אתה כנראה הולך רוצה להשתמש בחלק פונקציה שנוצרה בשבילך, שקיים באינטרנט. אם רק כדי להיות בטוח לצטט המקורות שלך. אין שום סיבה ל לגנוב שום דבר כאן. 

קהילת מדעי מחשב היא בהחלט גדל, ובאמת ערכים קוד פתוח, וזה באמת חשוב לצטט המקורות שלך, כך שאנשים יכול לקבל ייחוס ל העבודה שהם עושה לטובת הקהילה. אז תמיד יהיה sure-- ולא רק לחשיש פונקציות, אבל בדרך כלל כשאתה להשתמש בקוד ממקור חיצוני, תמיד מצטט המקור שלך. תן לאדם שעשה אשראי חלק מהעבודה, כך שאתה לא צריך. 

אישור אז בואו לבקר זה שולחן חשיש לשנייה. זה מקום שבי שעזבנו אחרי שהכנסנו את ג'ון ופול לשולחן חשיש זה. האם אתה רואה בעיה כאן? ייתכן שתראה שני. אבל בפרט, לעשות לך רואה בעיה אפשרית זו? 

מה אם אני חשיש רינגו, וזה מתברר עיבוד לאחר ש נתונים שבאמצעות פונקצית החשיש רינגו גם נוצר 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. אישור גם אנחנו יודעים ש7 של מלאים עכשיו, אז אנחנו לא יכולים לשים הומר שם. אז בואו נלך עד 8. האם 8 זמינים? כן, וקרוב של 8 עד 7, כך שאם אנחנו צריכים להתחיל לחפש אנחנו לא יצטרך ללכת רחוק מדי. ואז בואו לשים הומר בשעת 8. 

עכשיו אנחנו חשיש מגי ו חוזר 3, תודה לאל אנחנו יכולים רק לשים מגי שם. אנחנו לא צריכים לעשות שום סוג של חיטוט בשביל זה. עכשיו אנחנו חשיש מארג ', ו מארג 'גם מחזיר 6. 

ובכן 6 מלאים, 7 מלאים, 8 מלאים, 9, בסדר תודה לאל, 9 הוא ריקים. אני יכול לשים את מארג 'בשעת 9. כבר אנו יכולים לראות כי אנחנו מתחילים יש את הבעיה הזו שבי עכשיו אנחנו מתחיל למתוח סוג דברים של הרחק מקודי החשיש. ותטא של 1, ממוצע ש מקרה של להיות זמן קבוע, הוא מתחיל לקבל קצת more-- מתחיל נוטה קצת יותר לקראת תטא של n. אנחנו מתחילים לאבד את זה יתרון של שולחנות חשיש. 

בעיה זו שאנחנו פשוט ראינו הוא משהו שנקרא אשכולות. ומה באמת רע על אשכולות הוא שברגע שאתה עכשיו יש שני גורמים שהם בצד על ידי צד זה עושה את זה אפילו יותר סביר, יש לך כפול סיכוי, כי אתה הולך יש התנגשות נוספת עם אשכול ש, והאשכול יגדל על ידי אחד. ואתה תמשיך לגדול וגדל הסבירות שלך שיש התנגשות. וסופו של דבר זה רע בדיוק כמו לא מיון הנתונים בכל. 

הבעיה אחרת היא שלמרות ש עדיין, ועד כה עד לנקודה זו, רק שהיינו סוג של הבנה מה הוא שולחן חשיש, עדיין יש לנו רק חדר למשך 10 מיתרים. אם אנחנו רוצים להמשיך וחשיש אזרחי ספרינגפילד, אנחנו יכולים רק לקבל 10 מהם לשם. ואם אנחנו מנסים ולהוסיף ה -11 או ה -12, אין לנו מקום לשים אותם. אנחנו רק יכולים להיות מסתובבים ב חוגים מנסים למצוא מקום ריק, ואנחנו אולי להיתקע בלולאה אינסופית. 

אז זה סוג של משאיל לרעיון של משהו שנקרא שרשור. וזה מקום שבו אנחנו הולכים להביא רשימות מקושרות חזרה לתמונה. מה אם במקום אחסון פשוט המידע עצמו במערך, כל אלמנט של המערך יכול להחזיק חתיכות מרובות של נתונים? ובכן זה לא הגיוני, נכון? אנחנו יודעים שמערך רק יכול hold-- כל אלמנט של מערך יכול להחזיק רק חתיכה אחת נתונים של סוג הנתונים. 

אבל מה אם זה סוג הנתונים היא רשימה מקושרת, נכון? אז מה אם כל אלמנט של המערך היה מצביע לראש רשימה מקושרת? ואז אנחנו יכולים לבנות רשימות המקושרות אלה ולגדל אותם באופן שרירותי, כי רשימות מקושרות לאפשר לנו לגדול ולהתכווץ הרבה יותר גמישות מאשר מערך עושה. אז מה אם אנחנו משתמשים כעת, אנו ממנפים את זה, נכון? אנחנו מתחילים לגדול רשתות אלה מתוך מקומות מערך אלה. 

עכשיו אנחנו יכולים להתאים אינסופיים כמות הנתונים, או לא אינסופי, סכום שרירותי של הנתונים, לשולחן החשיש שלנו מבלי להיתקל הבעיה של התנגשות. גם אנחנו כבר בוטלו אשכולות ידי עושה את זה. וגם אנחנו יודעים שכאשר אנו מכניסים לרשימה מקושרת, אם אתה זוכר מהווידאו שלנו ברשימות מקושרות, ביחידים רשימות מקושרות ורשימות מקושרות כפליים, זה זמן פעולה קבועה. אנחנו רק הוספנו לחזית. 

ולמבט למעלה, גם אנחנו יודעים שנראה ברשימה מקושרת יכול להיות בעיה, נכון? יש לנו לחפש ב זה מהתחלה ועד הסוף. אין אקראי גישה ברשימה מקושרת. אבל אם במקום שיש אחד קשור רשימה שבה בדיקה תהיה O של n, עכשיו יש לנו 10 רשימות מקושרות, או 1,000 רשימות מקושרות, עכשיו זה O של n מתחלק ב -10, או O של n מחולק ב1,000. 

ובעוד אנחנו מדברים באופן תיאורטי על מורכבות נתעלם קבועים, באמיתי עולם הדברים האלה ממש משנה, נכון? אנחנו בעצם נבחין שזה קורה לרוץ 10 פעמים מהר יותר, או 1,000 פעמים מהר יותר, כי אנחנו מפיצים אחד ארוך שרשרת על פני 1,000 רשתות קטנות יותר. וכך בכל פעם שיש לנו לחפש באמצעות אחד מאותם רשתות שאנחנו יכולים להתעלם 999 הרשתות לא אכפת לנו על, ופשוט לחפש את זה. 

אשר הוא בממוצע ל להיות 1,000 פעמים קצרות יותר. ואז אנחנו עדיין הם סוג של הנוטה לכיוון מקרה ממוצע זה להיות זמן קבוע, אבל רק בגלל שאנחנו ממנפים החלוקה על ידי גורם קבוע ענק. בואו לראות איך אולי זה באמת נראה כאילו. אז זה היה שולחן החשיש שהיו לנו לפני שהכרזנו על שולחן חשיש ש היה מסוגלת לאחסן 10 מיתרים. אנחנו לא הולכים לעשות את זה יותר. אנחנו כבר יודעים מגבלות של שיטה ש. עכשיו שולחן החשיש שלנו הולך להיות מערך של 10 צמתים, מצביעים לראשי רשימות מקושרות. 

ועכשיו זה ריק. כל אחד מאלה הוא 10 המצביעים null. אין שום דבר בנו חשיש שולחן עכשיו. 

עכשיו בואו נתחיל לשים קצת דברים לשולחן חשיש זה. ובואו לראות איך שיטה זו היא הולך ליהנות קצת. בואו עכשיו חשיש ג'ואי. אנחנו יפעלו המחרוזת ג'ואי דרך פונקצית חשיש ואנו חוזרים 6. ובכן מה עושים עכשיו? 

ובכן עכשיו עובד עם רשימות מקושרות, אנחנו לא עובדים עם מערכים. וכאשר אנחנו עובדים עם רשימות המקושרות יודע שאנחנו צריכים להתחיל באופן דינמי הקצאת רשתות חלל ובניין. זה סוג של how-- אלה הם הליבה אלמנטים של בניית רשימה מקושרת. אז בואו דינמי להקצות שטח לג'ואי, ואז בואו נוסיף אותו לשרשרת. 

אז עכשיו תראה מה שעשינו. כאשר אנו חשיש ג'ואי הגענו hashcode 6. עכשיו את המצביע במיקום מערך 6 מצביע לראש רשימה מקושרת, ועכשיו זה רק אלמנט של רשימה מקושרת. ואת הצומת שב רשימה מקושרת היא ג'ואי. 

אז אם אנחנו צריכים להסתכל למעלה ג'ואי מאוחר יותר, אנחנו רק חשיש ג'ואי שוב, אנחנו מקבלים 6 שוב כי פונקצית חשיש היא דטרמיניסטית. ואז אנחנו מתחילים בראש של הרשימה המקושרת הצביע ללפי מיקום מערך 6, ואנחנו יכולים לחזר על פני שמנסה למצוא ג'ואי. ואם אנו בונים חשיש שולחן ביעילות, ופונקצית החשיש שלנו בצורה יעילה להפיץ נתונים טובים, בממוצע כל אחד מאלה קשורים רשימות בכל מיקום מערך יהיה 1/10 הגודל של אם רק שהיה לו כאחד ענק רשימה מקושרת עם כל אשר בו. 

אם אנו מפיצים כי ענק צמודים רשימה על פני 10 רשימות מקושרות כל רשימה תהיה 1/10 הגודל. וכך 10 פעמים מהר יותר לחפש ב. אז בואו נעשה את זה שוב. בואו עכשיו חשיש רוס. 

ונניח רוס, כאשר אנחנו עושים את זה קוד החשיש שנחזור הוא 2. ובכן עכשיו אנחנו דינמי להקצות צומת חדשה, אנחנו שמים רוס בצומת ש, ואנחנו אומרים עכשיו מיקום מערך 2, במקום להצביע על null, מצביע על ראש קשור רשימה שרק צומת רוס. ואנחנו יכולים לעשות את זה עוד פעם אחת, אנחנו יכול חשיש רחל ולקבל hashcode 4. malloc צומת חדשה, לשים את רחל ב הצומת, ואומרת מיקום מערך 4 עכשיו מצביע על הראש של רשימה מקושרת ש האלמנט קורה רק להיות רחל. 

בסדר, אבל מה קורה אם יש לנו התנגשות? בואו לראות איך אנחנו מטפלים בהתנגשויות בשיטת השרשור נפרדת. בואו חשיש פיבי. אנחנו מקבלים את hashcode 6. בדוגמא הקודמת שלנו היינו רק אחסון המחרוזות במערך. זו הייתה בעיה. 

אנחנו לא רוצים להרביץ בי ג'ואי, ויש לנו כבר ראיתי שאנחנו יכולים לקבל קצת אשכולות בעיות אם ננסה וצעד דרך ובדיקה. אבל מה אם אנחנו פשוט סוג של טיפול זה באותה הדרך, נכון? זה בדיוק כמו הוספת אלמנט לראש רשימה מקושרת. בואו חלל רק malloc לפיבי. 

אנחנו נגיד נקודות המצביע הבאות של פיבי לראש הרשימה המקושרת הישן, ולאחר מכן 6 רק מצביע על הראש חדש של הרשימה המקושרת. ועכשיו נראה, שינינו פיבי ב. כעת אנו יכולים לאחסן שתי אלמנטים עם hashcode 6, ואין לנו שום בעיות. 

זה פחות או יותר כל יש לשרשור. ושרשור הוא בהחלט השיטה זו הולך להיות יעיל ביותר עבורך אם אתה מאחסן נתונים בטבלת חשיש. אבל זה שילוב של מערכים ורשימות מקושרות יחד כדי ליצור טבלת חשיש באמת משפר באופן דרמטי את היכולת שלך לאחסון כמויות גדולות של נתונים, ו לחפש מהר מאוד וביעילות באמצעות הנתונים ש. 

יש עדיין אחד יותר מבנה נתונים בחוץ שאולי אפילו להיות קצת טוב יותר במונחים של הבטחת כי הכנסה, מחיקה, ושלנו פעמים לחפש אפילו מהר יותר. ואנו רואים כי בוידאו על ניסיונות. אני דאג לויד, זה CS50.