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

 

== שימושים ==

=== טבלת גיבוב ===

{{הפניה לערך מורחב|טבלת גיבוב}}

 

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

דוגמה לפונקציית גיבוב מסוג זה נתונה על ידי האלגוריתם הבא:

 

 

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

פונקציות גיבוב ויישומן לצורך איחזור מידע, נחקרו לראשונה על ידי [[ארנולד דמי]] (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>h : U\rightarrow \{1,...,N\}</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>.

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

 

 

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

==פונקציית גיבוב קריפטוגרפית==

{{ערך מורחב|פונקציית גיבוב קריפטוגרפית}}

 

 

פונקציית גיבוב קריפטוגרפית בטוחה מקיימת את התנאים הבאים: