הבדלים בין גרסאות בדף "פונקציית גיבוב"

 
===Chained Hashing===
פונקציות גיבוב ויישומן לצורך איחזור מידע, נחקרו לראשונה על ידי [[ארנולד דמי]] (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>,
שתמפה את הערכים באקראי, כך שכל כניסה <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>.