Hash table - סוגי hash tables

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

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

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

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

פירוט נוסף על ביצוע פעולות בכל סוג של hash table.