מה ההבדל בין מערך לטבלת חשיש בשפת תכנות?


תשובה 1:

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

אתה יכול להשתמש במערכים לדליים. נניח שרצית לספור כמה מכל אות בטקסט נניח בעיצוב משהו כמו קוד מורס. אתה מכין מערך עם 26 ערכים (עבור האלף-בית הרומי הפשוט-לא-מבוטל). בכל פעם שאתה רואה אות, אתה מחשיב את האינדקס והולך לערך זה במערך.

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

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