Hash table

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

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

הדגמה ויזואלית