[רעש].
לפני הצלילה לתוך שולחנות חשיש, בואו
תסקור את היתרונות וחסרונות של חלק ראשון
מבני נתונים פשוטים יותר, החל
מערכים.
נזכיר כי מערכים לאפשר לנו לאחסן
אלמנטים מסוג נתונים אחד
סמיכות בזיכרון.
מכיוון שכל אלמנט קשור
מדד, או מיקום,
יש לנו גישה אקראית לכל
אלמנטים במערך.
במילים אחרות, אנו יכולים לגשת לכל אלמנט
בשלב אחד על ידי יצירת אינדקס ל
מערך.
זה עניין גדול, כי אלגוריתמים
כמו חיפוש בינארי תלוי באקראי
גישה.
חיסרון של מערכים הוא שהגודל שלהם
הוא קבוע.
מאחר שנתוני חנות מערכי contiguously ב
זיכרון, עליך לציין גודל מערך
כאשר אתה מצהיר מערך.
אתה למעשה שואל את ההפעלה
מערכת שומרת לעצמנו את הכמות המתאימה
זיכרון לאלמנטים של המערך.
אין שום ערובה לכך שיותר זיכרון,
בסמוך למערך שלך, יהיה זמין
לשימוש מאוחר יותר.
אז מערכים לא יכולים לגדול בקלות.
נזכיר כי גם אנחנו למדנו על מקושרים
רשימות, אשר יכול לגדול בגללם
אלמנטים אינם רציפים בזיכרון.
כל צומת ברשימה מקושרת מכילה את
אלמנט שאנחנו רוצים לאחסן, כמו גם
מצביע לאלמנט הבא ב
הרשימה.
למרבה הצער, את המחיר ששלמנו בשבילו
גודל דינמי הוא גישה אקראית ל
אלמנטים.
כדי לגשת לאלמנט מסוים,
זה הכרחי כדי לעבור את כולו
רשימה עד הרכיב הרצוי הוא
הגיע.
לכן, אם אני מחפש את המספר 9, הייתי
בצע את המצביעים מצומת לצומת,
בודק אם הערך של כל צומת
שווה ל 9.
ככזה, במקרה הגרוע ביותר, הוא להסתכל למעלה
O (n), שהוא רחוק מלהיות יעיל.
אנחנו יכולים לעשות טובים יותר מאשר O (n) ועדיין
המאפשר למבנה הנתונים שלנו לצמוח מעל
זמן?
שולחנות חשיש להציע פתרון.
שולחנות חשיש משמשים בעת מהירה
הוספה, מחיקה, ובדיקה של
אלמנטים הם בראש סדר עדיפויות.
בתאוריה, הוספה, מחיקה, ובדיקה
אפילו יכול להיות מושלם במתמיד
זמן.
אז, מה הוא שולחן חשיש בכל מקרה?
שולחן חשיש הוא רק מערך שילוב
עם פונקציה, שאנחנו קוראים לחשיש
פונקציה.
פונקציית hash לוקחת פיסת המידע
כקלט, אנחנו קוראים לזה מפתח, ו
פלטי מספר שלם, המכונות
כערך Hash.
ערך Hash מפות המפתח שלנו ל
מדד מסוים בשולחן החשיש.
אתה בהתחלה הייתי להשתמש בפונקצית החשיש
לקבוע היכן בטבלת החשיש
לאחסן מפתח נתון.
מאוחר יותר, היית להשתמש באותה פונקצית החשיש
כדי לקבוע היכן בטבלת החשיש
לחפש את מפתח נתון.
מסיבה זו, זה חיוני כי חשיש
פונקציה מתנהגת באופן עקבי ותפוקות
את אותו ערך Hash עבור מפתחות זהים.
דע כי שולחנות חשיש יכולים לשמש כדי
לאחסן נתונים מכל הסוגים.
אבל כדי לפשט את הדברים, אנחנו מתמקדים
מחרוזות לעת עתה.
הנה פונקצית חשיש פשוט עבור מחרוזות.
פונקציית hash זה מחשב חשיש
פונקציה המבוססת על האות הראשונה של
מפתח.
"אפל" מתחיל באות "A", כך שזה
ממופה למדד 0 בטבלת הגיבוב.
בדומה לכך, "בננה" ממופית למדד 1,
או "חתול" ממופה לאינדקס 2.
אם חבר שואל אם המילה "כלב" היא ב
השולחן, אנחנו קלט "כלב" לחשיש
פונקציה, אשר יהיה פלט ערך Hash
של 3.
מאז "כלב" אינו מאוחסן במדד 3, אנחנו
ניתן לומר בביטחון ש" כלב "הוא לא
בטבלה,
למרות שאנחנו בדקנו אחד בלבד
חשיש מדדי 26 של הטבלה.
הגיע זמן לזרוק את מפתח ברגים לדברים.
מה אם אנחנו רוצים לאחסן את "נמלה" ל
שולחן גם כן?
"נמלה" hashes למדד 0, בדיוק כמו "תפוחים" לא.
זוהי דוגמא של התנגשות,
תוצאה של שני מפתחות וליבון לאותו
אינדקס.
גם אם שולחן החשיש שלך הוא גדול יותר מאשר
הנתונים שלך להגדיר, ושבחרת טוב
חשיש פונקציה,
אתה עדיין צריך תכנית להתמודדות עם
התנגשויות, אם וכאשר הם מתעוררים.
בואו לדבר על היתרונות וחסרונות של שני
שיטות נפוצות לפתרון התנגשויות:
ליניארי חיטוט ושרשור נפרד.
עם יניארי חיטוט, אם hashes מפתח
אותו המדד כפי שאוחסן בעבר
מפתח, זה מוקצה זמין הבא
חריץ בטבלה.
אז, "נמלה" מאוחסנת כעת במדד 3, שכן
מדדים 0, 1, ו -2 כבר היו בשימוש.
ואם ננסה לאחסן מילה שלישית ש
מתחיל עם האות "א", זה שהוקצה
למדד 4, שכן מדדים 0, 1, 2, ו -3
הם מלאים.
כפי שניתן לראות אפילו מזו פשוטה
למשל, ברגע שמתרחשת התנגשות, אתה
להגדיל את הסיכויים באופן משמעותי, כי
התנגשות נוספת תתרחש באותו
אזור.
זה נקרא קיבוץ, וזה
חסרון רציני ליניארי חיטוט.
יתר על כן, במקרה הגרוע ביותר הכנסה, מחיקה,
ובזמני בדיקה שהואצלו לO (n),
כמו שיש לי החריץ הפנוי הבא יכול
פוטנציאל היה החריץ האחרון בטבלה.
אולי שרשור נפרד יציע יותר
פתרון משכנע.
במודל השרשור הנפרד, החשיש
שולחן הוא למעשה מערך של מצביעים ל
רשימות מקושרות.
כאשר מתרחשת התנגשות, המפתח יכול להיות
הוכנס בזמן קבוע בראש
הרשימה המתאימה המקושרת.
מה קורה עכשיו כאשר אנו לחפש את "תפוח"
בשולחן החשיש?
במקרה הגרוע ביותר, עלינו לעבור את
כל רשימה מקושרת, החל משעת מדד 0.
המקרה הגרוע ביותר זמן בדיקה לחשיש
שולחן שמשתמש בשרשור נפרד הוא
לכן O (n / k), כאשר k הוא
גודלו של שולחן החשיש.
חכה שני, k הוא קבוע.
אז O (n / k) הוא באמת רק O (n),
שהיה הגרוע ביותר בזמן בדיקה ל
רשימה מקושרת.
האם אנחנו באמת עברנו את כל
צרות של למידה על שולחנות חשיש
אך בסופו של דבר חזרה בה התחלנו?
זה יכול להיות במקרה מתיאורטי
נקודת מבט, אבל בעולם האמיתי,
O (n / k) יכול להיות שיפור עצום על פני
O (n).
תחשוב על זה ככה: תניח k שהוא
10 - היית מעדיף לחכות 100 שניות
או 100 / k?
10 שניות מ-Microsoft Word כדי לסיים
בדיקת איות המסמך שלך.
כפי שראית, פתרון התנגשויות
כרוך בסוג של חיפוש ליניארי אחד או
אחר, אשר מאט את הדברים
במידה ניכרת.
לכן, אתה רוצה לבחור חשיש
פונקציה שמקטינה את הסיכוי של
התנגשויות מתרחשות במקום הראשון.
הנה כמה מאפיינים של חשיש טוב
פונקציות שכדאי לזכור.
פונקציית hash טובה צריכה לעשות שימוש
כל המידע הנמסר על ידי מפתח נתון
על מנת למקסם את מספר
ערכי Hash אפשריים.
לדוגמא, "חתול" אם היו לנו שתי מחרוזות
ו" זחל ", שהיינו רוצה שהם חשיש
למקומות שונים על השולחן.
אם פונקצית חשיש לקחה בחשבון רק
הראשון אחד, שתיים, או אפילו שלוש אותיות
של המחרוזות, התנגשות תתרחש,
מאז שני המילים מתחילות באותה
שלוש אותיות.
ערכי Hash צריכים להתפשט באופן שווה
מעבר לשולחן החשיש.
זה יקטין את אורך מקושר
רשימות צריכה התנגשויות יתרחשו.
זה גם סימן טוב, אם ערך Hash שלך
היא מסוגלת לייצר שונה מאוד
חשיש ערכים למפתחות דומים,
מה שהופך את ההתנגשויות הרבה פחות סביר.
המטרה שלנו היא כניסה מהירה, מחיקה,
ובדיקה.
פונקציית hash ממלאת תפקיד מכריע ב
כל אחד מתהליכים אלה ויהיו
נקרא לעתים קרובות מאוד.
לכן, ודא שהוא מעסיק רק מאוד
פעולות פשוטות, מהירות כדי למזער את הטווח
זמן.
אני מקווה שאתה נהנה זה קצר
מבוא לחשיש שולחנות.
שמי הוא לורן, וזה CS50.