Hash table - פונקצית hash

בבוחרינו פונקצית hash מתאימה אנו מחפשים פונקציה שתתן תוצאות ייחודיות ככל האפשר לאיברים, כדי להגיע למינימום איברים שערך הפונקציה עבורם יהיה זהה, וזאת כדי להגיע למינימום איברים עבור כל כניסה ב- hash.

תחום הפונקציה יהיה תחום האיברים האפשריים, והטווח יהיה כמות הכניסות ב- hash table. לדוגמא: אם על ה- hash להחזיק מילים בעברית וגודל ה- hash יהיה 100 מצביעים לרשימות מקושרות אשר יחזיקו בפועל את המילים, פונקצית hash סבירה תהיה פונקציה שתחשב את הערך הלקסיקוגרפי של המילה, או את ערכה בגמטריה, תחלק את התוצאה ב- 100 ותחזיר את השארית.

עם זאת כדי לקבל פונקציה מתאימה ככל האפשר נתייחס לאופי המידע, אם אנו מחזיקים משכורות, לא נבחר פונקציה שפשוט מחזירה את השארית של חלוקת המשכורת ב- 100 שכן מכיוון שמשכורות הן בדרך-כלל עגולות, ולכן נקבל את רוב האיברים ברשימה המקושרת עליה מצביעה הכניסה 100, כך שה- hash חסר תועלת.

פונקצית hash לדוגמא

פונקציה זו היא עבור hash table בגודל 101 שבו המפתח הוא מספר תעודת זהות.

HashFunc ( ID_number ){
   return ID_number mod 101;
}