נושאים פעיליםנושאים פעילים  הצגת רשימה של חברי הפורוםרשימת משתמשים  חיפוש בפורוםחיפוש  עזרהעזרה
  הרשמההרשמה  התחברותהתחברות RSS עדכונים
מדעי המחשב
RSS UnderWarrior Forums : RSS מדעי המחשב
נושא

נושא: double hashing

 שליחת תגובהשליחת נושא חדש
כותב
הודעה << נושא קודם | נושא הבא >>
gcd
אורח
אורח


הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
נשלח בתאריך: 13 July 2007 בשעה 17:47 | IP רשוּם
ציטוט gcd

נתונה טבלת גיבוב בגודל m ונתונה פונקציית גיבוב מהצורה- hi(x)=h(x)+id(x).z (לא להתייחס ל z).

אומרים שכדי שהחיפוש אחר תא פנוי יסרוק את טבלת הגיבוב כולה d(x) ו- m צריכים להיות זרים אחרת- אם יהיה להם מחלק משותף גדול מ- 1, נגיד k אז חיפוש אחר מפתח יבדוק רק אחד חלקי k מן הטבלה.

לא הצלחתי להבין למה. מישהו מוכן להסביר?(או להפנות למקום שמסביר..)

תודה
חזרה לתחילת העמוד הצג את כרטיס החבר של gcd חפש הודעות אחרות של gcd בקר בדף הבית של gcd
 
צחי@
משתמש חבר
משתמש חבר


הצטרף / הצטרפה: 02 January 2007
מדינה: Israel
משתמש: מנותק/ת
הודעות: 209
נשלח בתאריך: 13 July 2007 בשעה 19:05 | IP רשוּם
ציטוט צחי@
פונקציית ה-hash מחפשת אך ורק בתאים שהאינדקס שלהם הוא כפולה של (d(x
ועוד התוצאה של (h(x. כמה תאים קיימים שהאינדקס שלהם הוא כפולה של d(x) ?
יש סה"כ m תאים, אז יש m/k תאים לכל היותר שהאינדקס שלהם הוא כפולה של d(x).
(חיבור או הפחתת h(x) לא משנה את המספר הזה - זה רק אומר מה תהיה נק' ההתחלה של החיפוש),
כלומר, החיפוש סורק רק אחד חלקי k מן התאים ב-hash. 
חזרה לתחילת העמוד הצג את כרטיס החבר של צחי@ חפש הודעות אחרות של צחי@ בקר בדף הבית של צחי@
 
gcd
אורח
אורח


הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
נשלח בתאריך: 14 July 2007 בשעה 22:07 | IP רשוּם
ציטוט gcd
תודה  
חזרה לתחילת העמוד הצג את כרטיס החבר של gcd חפש הודעות אחרות של gcd בקר בדף הבית של gcd
 

אם ברצונך להגיב לנושא זה עליך קודם להתחבר
אם אינך רשום/ה כבר עליך להרשם

  שליחת תגובהשליחת נושא חדש
גרסת הדפסה גרסת הדפסה

קפיצה לפורום
אינך יכול/ה לשלוח נושאים חדשים בפורום זה
אינך יכול/ה להגיב לנושאים בפורום זה
אינך יכול/ה למחוק את הודעותיך ותגוביך בפורום זה
אינך יכול/ה לערוך את הודעותיך ותגובותיך בפורום זה
אינך יכול/ה לצור סקרים בפורום זה
אינך יכול/ה להצביע בסקרים בפורום זה