פונקציית גיבוב – הבדלי גרסאות

פונקציות גיבוב ויישומן לצורך איחזור מידע, נחקרו לראשונה על ידי [[ארנולד דמי]] (A.I. Dumey) ב-1956. במדוברמדובר באופן כללי בשיטות [[היוריסטיקה|היוריסטיות]] שנותנות פתרון לבעיה שנקראת 'בעיית המילון', שהיא הבעיה הבסיסית שפונקציית גיבוב אמורה לפתור. בהינתן המרחב <math>U</math> של כל אלמנטים האפשריים - מתוכם צריך לאחסן <math>N</math> אלמנטים, המטרה היא למצוא פונקציה שממפה אלמנטים מהמרחב <math>U</math> ל[[מערך (מבנה נתונים)|מערך]] כניסות בזיכרון <math>A[1..N]</math> כך ששלוש הפונקציות הבסיסיות: <math>\text{INSERT}(x,k)</math>, <math>\text{DELETE}(k)</math> ו-<math>\text{LOOKUP}(k)</math> דהיינו הוספה, מחיקה או חיפוש ערכים, צריכות להתבצע און-ליין במהירות האפשרית ובמינימום זיכרון אפשרי. <math>k</math> הוא המפתח לערך ו-<math>x</math> הוא המידע המשויך אליו.

תאורטית אפשר להקצות שטח זיכרון כגודל המרחב <math>U</math> ואז כל אלמנט יהיה ממופה לעצמו לפי סדר רץ כלשהו (כל אלמנט יכול להיות [[אינדקס (מחשב)|אינדקס]] של עצמו). אולם במקרה זה צריכת הזיכרון תהיה בזבזנית כי אם <math>N</math> קטן משמעותית מ-<math>U</math> שטח הזיכרון לא ינוצל במלואו. מלבד זאת ייתכן שיהיה בלתי מעשי להקצות כמות כזו של זיכרון אם המרחב גדול. הפתרון של דמי פשוט,; מגדירים פונקציה <math>h</math> שהיא פונקציה "[[מספר אקראי|אקראית]]" "כאוטית"{{הבהרה}}, "משוגעת"{{הבהרה}}:

שתמפה את הערכים באקראי, כך שכל כניסה <math>i</math> במערך <math>A[1..N]</math> תכיל [[רשימה מקושרת]] (מכאן השם), של מפתחות <math>k</math> (אם במקרה קיימים שניים או יותר באותה כניסה) כך שמתקיים <math>h(k)=i</math>. לכל מפתח מצמידים את המידע המשויך אליו. לצורך הפונקציה הראנדומליתהאקראית הציע דמי פונקציה פשוטה כמו <math>h(x)=x\text{ modulo }p</math> כאשר <math>p</math> [[מספר ראשוני|ראשוני]]. בממוצע הפונקציה פועלת כמצופה והערכים מתפזרים היטב על פני המערך. הסיכוי שיימצאו מספר גדול של מפתחות בכניסה אחת במקרה הממוצע,הוא נמוך. אפשר לראות שמציאת ערך בטבלה היא בערךבממוצע ב[[סיבוכיות]] של <math>O(1)</math>.

כדי להימנע מפעולת הצמצום המודלוריהמודולורי שהיא פעולה לא יעילה במונחי מיחשוב אפשר לבצע את הטריק הבא: אם <math>p=2^j-1</math> עבור <math>j</math> כלשהו (למשל <math>2^{11}-1</math> הוא מספר ראשוני), אם <math>x</math> ניתן לייצוג על ידי <math>2j</math> סיביות, אזי קיימים <math>x_1,x_2<2^j</math> כך שמתקיים <math>x= 2^jx_1+x_2</math> במילים אחרות <math>x_1</math> הוא <math>j</math> הסיביות המשמעותיות ביותר של <math>x</math> ו-<math>x_2</math> הוא <math>j</math> הסיביות הפחות משמעותיות. היות ש-<math>2^j\equiv 1 \ (\text{ mod }p)</math> מתקיים:

פועל יוצא הוא שהערך <math>x</math> אותו מעוניינים למפות מצטמצם מודולו <math>p</math> למספר בגודל <math>j+1</math> סיביות. כי כדי לחשב את <math>x(\text{mod }p)</math> מספיק לחשב את <math>x_1+x_2</math>, לבצע בדיקה אם הוא גדול מ-<math>p</math> ולכל היותר יידרש חיסור אחד של <math>p</math>. לסיכום אם <math>b</math> הוא [[חזקה של 2]], כל התהליך מצטמצם לכפל אחד, שתי פעולות חיבור, הזזה (shift) ופעולה לוגית אחת, ואין צורך במודולו כלל.

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