מדריך לטכניקת הקיפול בג'אווה

1. הקדמה

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

אנו דנים ביתר פירוט במה שמכונה טכניקת קיפול ולתת מבוא קצר לטכניקות אמצע הריבועים והבינונים.

2. סקירה כללית

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

חבילת השירות Java מציעה לנו הרבה מאוד מבני נתונים לאחסון האובייקטים שלנו. למידע נוסף על מבני נתונים, עיין בדף האוסף של אוספי Java שלנו המכיל מדריכים על כמה מהם.

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

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

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

על מנת לטפל בבעיה זו, מבני נתונים רבים מנסים להקצות ערך מספרי שיכול לשמש אינדקס מערכים לאובייקטים. אנו מכנים ערך זה a ערך חשיש או פשוט א בְּלִיל.

3. Hashing

Hashing הוא הפיכת אובייקט לערך מספרי. פונקציות המבצעות טרנספורמציות אלה נקראות פונקציות חשיש.

לשם הפשטות, נבחן פונקציות חשיש שהופכות מחרוזות לאינדקסים של מערכים, כלומר למספרים שלמים מהטווח [0, N] עם סופי נ.

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

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

אנו עשויים לשכנע את עצמנו די בקלות שמספר המיתרים גדול בהרבה ממספר המספרים השלמים בכל טווח [0, N]. לכן, אין מנוס מכך שיש זוג מיתרים לא שווים שעבורם פונקציית hash מייצרת ערכים שווים. תופעה זו נקראת הִתנַגְשׁוּת.

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

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

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

4. טכניקת קיפול

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

4.1. תיאור

נתחיל בהמרת תווי המחרוזת למספרים. ASCII הוא מועמד טוב למבצע זה:

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

השלב הבא הוא לשרשר את המספרים בכל קבוצה כאילו הם מחרוזות ולמצוא את הסכום שלהם:

עכשיו עלינו לעשות את הצעד האחרון. בואו לבדוק אם המספר 348933 עשוי לשמש אינדקס למערך שלנו בגודל 105. מטבע הדברים, הוא עולה על הערך המקסימלי המותר 99999. אנו עשויים להתגבר על בעיה זו בקלות על ידי שימוש במפעיל המודולו על מנת למצוא את התוצאה הסופית:

348933 % 10000 = 48933

4.2. הערות אחרונות

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

לדוגמא, אם היינו רוצים לדלג על הקיפול והחלנו את מפעיל המודול ישירות על מחרוזת הקלט שהפכה ASCII (תוך התעלמות מבעיית ההצפה)

749711897321089711010311797103101 % 100000 = 3101

אז פונקציית hash כזו תייצר את אותו הערך עבור כל המחרוזות שיש להן שתי התווים האחרונים כמו מחרוזת הקלט שלנו: age, עמ 'גיל, large, וכולי.

מתיאור האלגוריתם אנו יכולים לראות בקלות שהוא אינו נקי מהתנגשויות. לדוגמה, האלגוריתם מייצר את אותו ערך hash עבור שפת ג'אווה ו שפת vaJa מיתרים.

5. טכניקות אחרות

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

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

5.1. טכניקת binning

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

5.2. טכניקת אמצע הריבוע

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

בואו נמחיש זאת בדוגמה קונקרטית. נניח, יש לנו מספר בן ארבע ספרות 1111. על פי האלגוריתם, אנו מרובעים אותו וכך מקבלים 1234321‬. כעת, אנו מחלצים ארבע ספרות מהאמצע, למשל, 2343. האלגוריתם מאפשר לנו לחזור על תהליך זה עד שנהיה מרוצים מהתוצאה.

6. מסקנה

במדריך זה שקלנו כמה טכניקות hashing. תארנו בפירוט את טכניקת הקיפול ונתנו תיאור בזק של האופן שבו ניתן להשיג כיכר וריבוע אמצע.

כמו תמיד, אנו עשויים למצוא את קטעי הקוד המתאימים במאגר GitHub שלנו.


$config[zx-auto] not found$config[zx-overlay] not found