המדריך ללא קוד ללא שולחנות האש

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

כל המדריכים שנתקלים בהם בטוח דנים בטבלאות hashing ו- hash ב- JavaScript, Python או בשפת תכנות אחרת.

המשמעות של זה היא שאולי תבינו קצת כיצד עובד hashing וכיצד להשתמש בטבלת hash ב [הכניסו שפה כאן], אך ייתכן שתפספסו את עקרונות אופן פעולתו.

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

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

אז מה בכל זאת פונקציית Hash?

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

הקופסה השחורה הזו מיוחדת. זה נקרא תיבת פונקציות. אנחנו נקרא לזה תיבת פונקציה מכיוון שתיבה זו תמפה משתנה עצמאי בקלט למשתנה תלוי בפלט (זה נשמע מתמי אבל נשא איתי).

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

תיבת הפונקציות שלנו תיקח אות מ- AJ על הקלט ותפלט מספר מקביל בין 0 ל- 9 בפלט. אז אם נקליט C נקבל 2 על הפלט.

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

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

מה עם שולחנות האש?

אז בשלב זה אתם אולי תוהים מהו שולחן חשיש. טבלאות Hash משתמשות ב- hashing ליצירת מבנה נתונים.

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

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

טבלאות האש מהירות ביותר, עם מורכבות זמן בסדר גודל של O (1).

מְבוּלבָּל? התבונן בתרשים זה, שם יש לנו מספר תיבות פונקציה המייצרות ערכי hash.

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

המבנה המתקבל ייראה כך:

התנגשויות חשיש

זה זמן טוב לדבר על התנגשות בפונקציות hash ובטבלאות hash.

פונקציה במתמטיקה היא אידיאלית בכך שאלמנט בקלט ממופה לאלמנט אחד בדיוק בפלט.

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

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

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

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

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

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

האם Hashing זהה להצפנה או קידוד?

אנשים רבים נוטים לקשר hashing להצפנה או קידוד. אז האם הצפנת hashing? האם זהה לקידוד?

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

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

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

מה אני יכול לעשות עם Hashing?

לטבלאות חשיש וחשיש יש שימושים רבים! אלו כוללים:

  1. מערכות קריפטות
  2. בדיקות יתירות מחזוריות
  3. מנועי חיפוש
  4. מאגרי מידע
  5. מהדרים

או כל מערכת שיש בה תהליך בדיקה מורכב.

מסיימים

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

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

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

אהבת את הגישה חסרת הקוד? רוצה ללכת רחוק יותר?

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

מבני נתונים ואלגוריתמים ללא קוד - למד DSA מבלי לכתוב שורת קוד אחת | ארמסטרונג סוברו | Apress ספר זה מביא לך נקודת מבט חדשה על אלגוריתמים ומבני נתונים, ללא קוד לחלוטין. למד על אלגוריתמים של מבנה נתונים (DSA) מבלי שתצטרך לפתוח את עורך הקוד שלך, להשתמש במהדר או להסתכל על סביבת פיתוח משולבת (IDE) .... Armstrong Subero חיפוש תפריט עגלת V העגלה שלך ריקה כרגע. כניסה חשבון מדף כניסה כניסה Apress Access