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

מ
סקריפט החלפות (תאור, פונקציית, פתרון, מעוניינים, משוי)
מ (סקריפט החלפות (תאור, פונקציית, פתרון, מעוניינים, משוי))
 
===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>.
 
===פונקצית גיבוב אוניברסלית===
{{ערך מורחב|פונקצית גיבוב אוניברסלית}}
ב-1975 פרסמו [[לורנס קרטר]] ו[[מרק ווגמן]] מאמר{{הערה|[http://www.cs.princeton.edu/courses/archive/fall09/cos521/Handouts/universalclasses.pdf Universal Classes of Hash Functions]}} רב השפעה שחוקר את פונקציות הגיבוב מהיבט תיאורתיתאורתי. הם הטביעו לראשונה את המושג [[פונקצית גיבוב אוניברסלית]] (Universal Hash Function) והראו שלוש מחלקות אפשריות של פונקציות כאלו וכן הוכיחו שפונקציה העונה להגדרה זו, קרובה למינימום התיאורטיהתאורטי האפשרי, כלומר עם מינימום התנגשויות ללא תלות באופי הקלט וכן ניתנת לחישוב באופן יעיל.
 
תהי <math>\mathcal{H}</math> מחלקה של פונקציות מהצורה <math>h : U\rightarrow A[1..N]</math> כאשר <math>h</math> שנבחרה באקראי מתוך המרחב <math>\mathcal{H}</math> הממפה ערכים מ-<math>U</math> ל-<math>A</math> כאשר <math>|U|>|A|</math>. אומרים ש-<math>h</math> אוניברסלית אם עבור כל <math>x,y\in U</math> כאשר <math>x\ne y</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\equiv x_1+x_2 \ (\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) ופעולה לוגית אחת ואין צורך במודולו כלל.
 
דרך אחרת להימנע מחילוק הוצעה על ידי Dietzfelbinger. נוטלים את הסיביות המשמעותיות של התוצאה. לדוגמה אם <math>k=32</math>, אם התוצאה בגודל 64 סיביות, נוטלים רק את 32 הסיביות המשמעותיות, או בניסוח אחר: <math>h_{m,n}(x)=(mx+n) \gg k</math> כאשר <math>\gg</math> הוא הזזה לימין (shift right), אזי הפונקציה <math>h_{m,n}(x)</math> אוניברסלית.