Movatterモバイル変換

[0]ホーム
URL:

לדלג לתוכן
ויקיפדיההאנציקלופדיה החופשית
חיפוש

טבלת גיבוב

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

ספר טלפונים קטן כטבלת גיבוב. ניתן לראות כיצד המפתחות השמיים מוחלפים באמצעותפונקציית גיבוב לאינדקסים מספריים וכך ניתן לגשת לרשומות
יצירה
הומצא ב:1953
סיבוכיותמקום וזמן
ממוצעבמקרה הגרוע
זיכרון:
O(n)O(n)
חיפוש:
O(1)O(n)
הכנסה:
O(1)O(n)
הוצאה:
O(1)O(n)

במדעי המחשב,טבלת גִּבּוּב אוטבלת ערבול (באנגלית:Hash table), היאמבנה נתוניםמילוני, אשר נותן גישה לרשומה באמצעותהמפתח המתאים לה. המבנה הזה עובד באמצעות הפיכת המפתח על ידיפונקציית הגיבוב, למספר המייצג מיקום במערך שמפנה אל הרשומה המבוקשת. הפעולה העיקרית שבה היא תומכת ביעילות היא אחזור המידע מתוך מבנה הנתונים: בהינתן מפתח נתון (למשל שם של אדם), מצא את הרשומה המתאימה (למשל מספר הטלפון של אותו אדם).

הרעיון לטבלת הגיבוב הופיע כבר ב-1953 במזכר פנימי בחברתIBM שפורסם על ידי ה.פ. לון (H. P. Luhn)[1] ובמקביל פותחה על ידיג'ין אמדל(Gene Amdahl), ה.מ בוהם (E. M. Boehme), נתניאל רוצ'סטר (Nathaniel Rochester) וארתור סמואל (Arthur Samuel) תוכנית שמשתמשת בגיבוב. כאשר למדען המחשב הרוסי אנדריי ארשוב (Andrey Ershov), היה את אותו רעיון כמו לאמדל.

מבנה טבלת הגיבוב

[עריכת קוד מקור |עריכה]

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

כדוגמה לטבלת גיבוב פשוטה נוכל לקחת מפעל קטן בעל 1000 עובדים שבו רוצים לשמור רשומות המכילות את פרטי העובדים והגישה לרשומות תהיה לפי מספר עובד בן 3 ספרות (000-999). כדי לבנות טבלת גיבוב מתאימה, נוכל להשתמש במערך בעל אלף תאים ונבחר פונקציית גיבוב פשוטה שעבור כל מספר עובד, מחזירה את המספר עצמו (פונקציית הזהות) ולמעשה מצביעה על כך שאת המידע על העובד שמספרו X נוכל להשיג בתא מספר X. בדוגמה הזאת ביצענומיעון ישיר - השתמשנו ב"פונקציה חד-חד-ערכית", כלומר, לא קיים יותר ממספר עובד אחד שיופנה לתא מסוים.

בעיית ההתנגשות

[עריכת קוד מקור |עריכה]

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

טבלה פתוחה וסגורה

[עריכת קוד מקור |עריכה]

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

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

טבלה סגורה פותרת את בעיית ההתנגשות על ידי הפניה מכל תא במערך אל מבנה נתונים שמספק את אותן תכונות כמו טבלת הגיבוב (חיפוש, מחיקה, הוספה וכו'). טבלת הגיבוב משתמשת בפונקציה כדי למצוא את התא המתאים במערך והוא מפנה אל מבנה הנתונים שנותן גישה אל כל הרשומות שנשלחו לתא על ידי הפונקציה. השימוש במבני הנתונים הנוספים, משפיע על מאפייני הטבלה כמו למשל עלסיבוכיות הזמן של פעולות הטבלה, המקום בזיכרון שהטבלה תצרוך ומספר הרשומות שיהיה ניתן להכניס לטבלה. דוגמה לכך היא שימושברשימות מקושרות שכל תא במערך מפנה לאחת מהן. השימוש ברשימה מקושרת, מאפשר להכניס אל טבלת הגיבוב מספר רשומות גדול מ-B אבל אם מספר הרשומות (n) יהיה גדול משמעותית מ-B, אז לפיעקרון שובך היונים הרשימות המקושרות תהיינה יותר ארוכות וסיבוכיות הזמן של פעולות על הטבלה תושפע מהרשימות ותהיה O(n){\displaystyle \ O(n)}. השימוש במבנה הנתונים הנוסף גם יצרוך יותר מקום בזיכרון בגלל דרישות מבנה הנתונים ובגלל המערך שסביר ויהיו בו יותר תאים ריקים בניגוד לטבלה הפתוחה.

קיימת שיטה נוספת לפתרון התנגשויות הנקראתגיבוב קוקייה.

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

פונקציית הגיבוב

[עריכת קוד מקור |עריכה]
ערך מורחב –פונקציית גיבוב

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

פעולת חיפוש

[עריכת קוד מקור |עריכה]

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

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

עבור פונקציית גיבוב טובה, סיבוכיות הזמן תהיה תלויה במספר ההתנגשויות בזמן חיפוש ערך ותהיה גבוהה יותר ככל שמספר הרשומות בטבלה, מתקרב לגודל המערך (מסומן "B<<n" כאשר B - גודל המערך, n - מספר הרשומות בפועל במערך). הסיבוכיות תהיה תלויה גם בכמות הרשומות שהוכנסו לטבלה אפילו אם הן כבר לא נמצאות בה כיוון שהרבה תאים יסומנו כתאים ש"אוכלסו". כאשר כמות הרשומות אינה גבוהה, מספר ההתנגשויות צפוי להיות בודד ולכן סיבוכיות החיפוש תהיה במקרה הממוצע O(1){\displaystyle \ O(1)}. במקרה הגרוע של הרבה התנגשויות הסיבוכיות תהיה O(n){\displaystyle \ O(n)}.

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

עבור פונקציית גיבוב טובה, כאשר כמות הרשומות באותוסדר גודל של מספר התאים במערך (מסומן "B~n"), סיבוכיות החיפוש תהיה במקרה הממוצע O(1){\displaystyle \ O(1)} כיוון שבכל מבנה נתונים יהיה בממוצע מספר בודד של רשומות. במקרה הגרוע, הסיבוכיות תהיה כמו הסיבוכיות במקרה הגרוע של מבנה הנתונים בו משתמשים.

פעולת הכנסה

[עריכת קוד מקור |עריכה]

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

עבור הכנסה בטבלה פתוחה, גם כאשר מוצאים תא שהיה בעבר מאוכלס, מכניסים לתוכו את הרשומה. סיבוכיות ההכנסה עבור פונקציה טובה וטבלה שמספר הרשומות בה קטן באופן משמעותי ממספר התאים, תהיה במקרה הממוצע O(1){\displaystyle \ O(1)}. במקרה הגרוע של הרבה התנגשויות הסיבוכיות תהיה O(n){\displaystyle \ O(n)}.

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

פעולת מחיקה

[עריכת קוד מקור |עריכה]

גם הוצאת רשומה מטבלת הגיבוב דומה לחיפוש.

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

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

שיטות גיבוב

[עריכת קוד מקור |עריכה]

עבור טבלה סגורה, ניתן להשתמש במבנה הנתוניםרשימה מקושרת ואף על פי שבמקרה הגרוע, היעילות תהיה O(n){\displaystyle \ O(n)} עבור כל אחת משלוש הפעולות, קלות התפיסה של פעולת הרשימות המקושרות והתכנות שלהם, יכולים לפצות על כך. ניתן להשתמש גם בעץ חיפוש מאוזן כמועץ AVL ועץ B+ שיקטינו את החיפוש במקרה הגרוע ל O(log⁡n){\displaystyle \ O(\log n)}. במערכות זמן אמת בהם זמן ביצוע פעולה הוא קריטי גם במקרה הגרוע, בחירה במבני נתונים אלו יכולה לשפר את ביצועי המערכת.

בטבלה הפתוחה קיימות מספר שיטות לפתירת בעיית ההתנגשות:

  • בדיקה ליניארית(אנ')- עבור כל התנגשות נבדוק סדרתית האם האינדקס הבא במערך פנוי. שיטה זו קלה לחישוב ולהבנה ושומרת על מקומיות בזיכרון דברשחוסך גישה לדיסק הקשיח אך יכולה ליצור בעיה של הצטברות רשומות בסדרת אינדקסים ובעקבות כך יהיה מספר גדול של התנגשויות עבור הרשומות באותם באינדקסים. ההצטברות תתהווה משום שעבור כל ניסיון הכנסה של רשומה לצביר רשומות, ההצטברות תגדל בעוד אחד וכך גם מספר האינדקסים שיגדילו את הצביר יגדל באחד.
  • בדיקה ריבועית(אנ')- עבור כל התנגשות נבדק מקום מתאים אחר תוך שימוש בהעלאה בריבוע של מספר ההתנגשויות שהיו עד כה עבור אותו מפתח. הפונקציה עבור הבדיקה הריבועית היא:h(k,i)=(h(k)+c1i+c2i2)modm{\displaystyle h(k,i)=(h(k)+c_{1}i+c_{2}i^{2})\mod m} כאשר:h{\displaystyle h} - פונקציית הגיבוב,k{\displaystyle k} - המפתח המבוקש,i{\displaystyle i} - מספר ההתנגשויות,m{\displaystyle m} - מספר התאים בטבלה ו-c1,c2{\displaystyle c_{1},c_{2}} - מספרים קבועים. בשיטה זו אמנם תיתכן הצטברות שתבוא לידי ביטוי בסדרות של תאים מאוכלסים שמתחילות מ-h(k){\displaystyle h(k)} וממשיכות בתאים שבאופן רצוף האינדקס עבורם הואh(k,i){\displaystyle h(k,i)} והם מאוכלסים. ההצטברות מתהווה משום שכל המפתחות שמחזיריםh(k){\displaystyle h(k)} תמיד ינותבו אל אותה סדרת תאים. ההצטברות עבור הבדיקה הריבועית פחות משמעותית מההצטברות המתרחשת עבור הבדיקה הליניארית, אך הבדיקה הריבועית שומרת על מקומיות בזיכרון ברמה פחותה.
  • גיבוב כפול(אנ')- בגיבוב כפול משתמשים בפונקציית גיבוב נוספת כדי לטפל במקרה של התנגשות. הנוסחה עבור גיבוב כפול היא:h(k,i)=(h1(k)+i⋅h2(k))modm{\displaystyle h(k,i)=(h_{1}(k)+i\cdot h_{2}(k))\mod m} כאשרk{\displaystyle k} - המפתח המבוקש,h1,h2{\displaystyle h_{1},h_{2}} - פונקציות גיבוב,i{\displaystyle i} - מספר ההתנגשויות ו-m{\displaystyle m} - מספר התאים בטבלה. ההצטברות בגיבוב כפול מתרחשת רק עבור מפתחות שבאופן נדיר שתי הפונקציות מחזירות עבורם את אותו הערך, ובכך עדיפה על הבדיקה הריבועית אבל לא נשמרת המקומיות בכלל.

שימושים לטבלאות גיבוב

[עריכת קוד מקור |עריכה]

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

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

ראו גם

[עריכת קוד מקור |עריכה]

קישורים חיצוניים

[עריכת קוד מקור |עריכה]
ויקישיתוף מדיה וקבצים בנושאטבלת גיבוב בוויקישיתוף

הערות שוליים

[עריכת קוד מקור |עריכה]
  1. ^Hans Peter Luhn and the Birth of the Hashing Algorithm - IEEE Spectrum, spectrum.ieee.org(באנגלית)
מבני נתונים
מבנים מופשטיםרשימה •מחסנית •קבוצה •מולטי קבוצה •תור •דו-תור •תור עדיפויות •מילון •מחרוזת •איחוד קבוצות זרות
מימושים ליניארייםמערך •מערך משונן •טבלת גיבוב •רשימה מקושרת •רשימת דילוגים •חוצץ
גרפים ועציםערימה (בינארית •בינומית •פיבונאצ'י)•עץ חיפוש (עץ אדום שחור •עץ 2-3 •עץ 2-3-4)•עץ סיפות •עץ B •עץ +B •עץ AVL •עץ Splay •עץ BSP •עץ kd •עץ R‏ •Trie •X-fast trie •טריי y מהיר•עץ WAVL
הסתברותייםמסנן בלום
בקרת זהויותעריכת הנתון בוויקינתונים
אוחזר מתוך "https://he.wikipedia.org/w/index.php?title=טבלת_גיבוב&oldid=39947447"
קטגוריה:
קטגוריות מוסתרות:
[8]ページ先頭
©2009-2025 Movatter.jp