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

 
===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>.