Hash table - פעולות

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

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

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

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

פסאודו קוד

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

HashFunc ( ID_number ) 
{
    return ID_number mod 101
}

InsertToHash ( ID_number)
{
    InsertToList( Hash[HashFunc(ID_number)], ID_number)
}

DeleteFromHash ( ID_number)
{
    DeleteFromList( Hash[HashFunc(ID_number)], ID_number)
}

FindInHash ( ID_number)
{
    FindInList( Hash[HashFunc(ID_number)], ID_number)
}

מובן גם שאם במקום רשימות היה הhash מצביע על מבנה נתונים אחר, ההבדל היחידי היה בפונקציה אליה אנו קוראים: במקום FindInList הינו קוראים ל FindInRedBlackTree לדוגמא.