מושגי Hashing


מבוא

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

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

בתרשים לעיל מתואר כתובת חסימות נתונים זהה לערך המפתח הראשי. פונקציית hash זו יכולה להיות גם פונקציה מתמטית פשוטה כמו mod, sin, cos, exponential וכו '. דמיין שיש לנו פונקציית hash כ mod (5) כדי לקבוע את כתובת גוש הנתונים. אז מה קורה למקרה הנ"ל? זה מחיל mod (5) על מפתחות ראשיים ויוצר 3,3,1,4 ו- 2 בהתאמה והרשומות נשמרות באותן כתובות חסימות נתונים.

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

ישנם שני סוגים של ארגוני קבצי hash - סטטי ו דינמי גיבוב.

Hashing סטטי

בשיטת hashing זו, כתובת דלי הנתונים שהתקבלה תהיה תמיד זהה. כלומר, אם אנו רוצים ליצור כתובת עבור EMP_ID = 103 באמצעות פונקציית hash mod (5), זה תמיד יביא לאותה כתובת דלי 3. לא יהיו שינויים בכתובת הדלי כאן. מכאן שמספר דליי הנתונים בזיכרון עבור גיבוב סטטי זה נשאר קבוע לאורך כל הדרך. בדוגמה שלנו, יהיו לנו חמישה דליי נתונים בזיכרון המשמשים לאחסון הנתונים.

מחפש שיא

באמצעות פונקציית hash, נוצרת כתובת דלי נתונים עבור מפתח hash. לאחר מכן התקליט מאוחזר ממיקום זה. כְּלוֹמַר; אם ברצוננו לאחזר רשומה שלמה עבור מזהה 104, ואם פונקציית הגיבוב היא mod (5) בתעודה מזהה, הכתובת שנוצרה תהיה 4. ואז ניגש ישירות לכתובת 4 ונשיג את כל הרשומה עבור מזהה 104. כאן מזהה משמש כמפתח חשיש.

הכנסת רשומה

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

מחק רשומה

באמצעות פונקציית ה- hash נביא תחילה את הרשומה שאמורה להימחק. לאחר מכן נסיר את הרשומות עבור אותה כתובת בזיכרון.

עדכן רשומה

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

 

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

חשיש סגור

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

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

פתח Hashing

בשיטה זו, נעשה שימוש בחסימת הנתונים הזמינה הבאה להזנת הרשומה החדשה, במקום להחליף בתיק הישן. שיטה זו נקראת Open Hashing או חיטוט לינארי.

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

בחיטוט הליניארי, ההבדל בין הדלי הישן לדלי החדש הוא בדרך כלל קבוע והוא יהיה 1 ברוב המקרים.

חיטוט ריבועי

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

Hashing כפול

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

Hashing דינמי

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

קחו בחשבון שיש שלוש רשומות R1, R2 ו- R4 בטבלה. רשומות אלה מייצרות כתובות 100100, 010110 ו- 110110 בהתאמה. שיטת אחסון זו שוקלת רק חלק מכתובת זו - במיוחד רק סיבית ראשונה אחת לאחסון הנתונים. אז הוא מנסה לטעון שלושה מהם בכתובת 0 ו -1.

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

כעת אנו יכולים לראות כי הכתובת של R1 ו- R2 משתנה כך שתשקף את הכתובת החדשה וגם R3 מוכנס. ככל שגודל הנתונים גדל, הוא מנסה להכניס לדליים הקיימים. אם אין דליים זמינים, מספר הביטים גדל בכדי לשקול כתובת גדולה יותר, ומכאן להגדיל את הדליים. אם אנו מוחקים רשומה כלשהי ואם ניתן לאחסן את הנתונים עם דליים פחותים, זה מכווץ את גודל הדלי. זה עושה את ההפך ממה שראינו לעיל. כך עובד גיבוב דינמי. בתחילה רק אינדקס / כתובת חלקית שנוצרו על ידי פונקציית ה- Hash נחשבים לאחסון הנתונים. ככל שמספר הנתונים גדל ויש צורך בדלי נוסף, חלק גדול יותר מהאינדקס שוקל לאחסן את הנתונים.

היתרונות של חשיש דינמי

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

 

חסרונות של חשיש דינמי

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

השוואה בין הוספה לאינדקס והאש

הוספה לאינדקס

חבטות

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

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

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

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

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