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

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

 

פונקציות גיבוב ויישומן לצורך איחזור מידע, נחקרו לראשונה על ידי [[ארנולד דמי]] (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}(x)</math> דהיינו הוספה, מחיקה או חיפוש ערכים, צריכות להתבצע און-ליין במהירות האפשרית, זאת במינימום זיכרון אפשרי. <math>k</math> הוא המפתח לערך ו-<math>x</math> הוא המידע המשוייך אליו. תיאורטית אפשר לאחסן את המרחב <math>U</math> בשטח זיכרון כגודל המרחב עצמו ואז כל אלמנט ממופה לעצמו לפי סדר כלשהו אולם במקרה זה צריכת הזיכרון תהיה בזבזנית ואף בלתי מעשית אם המרחב מכיל אלמנטים גדולים, לכן ההנחה היא ששטח האחסון קטן משמעותית מהמרחב. הפיתרון של דמי פשוט, מגדירים פונקציה <math>h</math> שהיא פונקציה [[מספר אקראי|ראנדומלית]] 'כאוטית', 'משוגעת':

:<math>h : U\rightarrow \{1,...,N\}</math>,