סיפור על שני איטרטורים: אסטרטגיות שינוי תחרותי בג'אווה

מחבר הפתק הוא Grzegorz Mirek, מפתח תוכנה מקרקוב (פולין). הוא התחיל להתפתח בג'אווה לפני כ-6 שנים, עוד באוניברסיטה, ומאז הוא משפשף ללא לאות את כישוריו בתחום זה. הוא מתעניין במיוחד בביצועים ובאופטימיזציה של JVM, ועל כך הוא כותב בעיקר בבלוג שלו . כמה משאלות הראיונות הפופולריות ביותר בג'אווה כוללות: מה ההבדל בין איטרטורים מהירי כישלון לבין איטרטורים בטוחים? התשובה הפשוטה ביותר לכך היא: איטרטור מהיר כישלון זורק ConcurrentModificationException אם האוסף משתנה במהלך האיטרציה, אבל איטרטור בטוח בכשל לא עושה זאת. למרות שזה נשמע די משמעותי, עדיין לא ברור למה מתכוון המראיין כשיש כשל? מפרטי שפת Java אינם מגדירים את המונח הזה ביחס לאיטרטורים. עם זאת, ישנן ארבע אסטרטגיות שינוי תחרותי.

שינוי תחרותי

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

List<String> cities = new ArrayList<>();
cities.add(“Warsaw”);
cities.add(“Prague”);
cities.add(“Budapest”);

Iterator<String> cityIterator = cities.iterator();
cityIterator.next();
cities.remove(1);
cityIterator.next(); // генерирует ConcurrentModificationException

כשל מהיר

קטע הקוד לעיל הוא דוגמה לאיטרטור מהיר כישלון . כפי שאתה יכול לראות, ConcurrentModificationException נזרק בעת ניסיון לאחזר את האלמנט השני מהאיטרטור . איך איטרטור יודע שהאוסף השתנה מאז שנוצר? לדוגמה, לאוסף עשוי להיות חותמת תאריך/שעה, למשל lastModified . בעת יצירת איטרטור, עליך להעתיק שדה זה ולאחסן אותו באובייקט איטרטור. לאחר מכן, בכל פעם שנקרא למתודה next() , פשוט תשווה את הערך lastModified מהאוסף עם העותק מהאיטרטור. גישה דומה מאוד משמשת, למשל, ביישום המחלקה ArrayList . יש לו משתנה מופע modCount המאחסן את מספר הפעמים שהרשימה שונתה:

final void checkForComodification() {
   if (modCount != expectedModCount)
       throw new ConcurrentModificationException();
}

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

עקביות חלשה

רוב האוספים המקבילים בחבילת java.util.concurrent (כגון ConcurrentHashMap ורוב Queue ) מספקים איטרטורים עקביים חלשים. המשמעות של מונח זה מוסברת היטב בתיעוד :

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

תמונת מצב

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

התנהגות לא מוגדרת

אתה עלול להיתקל בהתנהגות לא מוגדרת בסוגי אוספים מדור קודם כמו Vector ו- Hashtable . לשניהם יש איטרטורים סטנדרטיים מהירי כשל , אך בנוסף, הם מאפשרים שימוש ביישומים של ממשק ה-Enumeration , והם אינם יודעים כיצד להתנהג במקרה של שינוי במקביל. אתה עלול להיתקל באלמנטים מסוימים שחוזרים על עצמם או חסרים, או אפילו כמה חריגים מוזרים. עדיף לא לשחק איתם!