10 השאלות המובילות על אוספים ב-Java

המאמר הוא תרגום של המאמר " 10 השאלות המובילות על אוספי Java " . להלן השאלות הפופולריות ביותר על אוספים ב-Java, שנשאלו ונדונו ב-Stackowerflow. לפני שתסתכל על השאלות האלה, יהיה טוב להסתכל על דיאגרמת ההיררכיה של הכיתה. 1. מתי להשתמש ב-LinkedList במקום ב-ArrayList? ArrayList הוא למעשה מערך; ניתן לגשת ישירות לאלמנטים שלו באמצעות אינדקס. אם המערך עולה על גדותיו, יהיה צורך במערך חדש עם יותר מקום. מיקום והזזה של כל האלמנטים ייקח זמן O(n). כמו כן, הוספה והסרה של אלמנטים נחוצה כדי להעביר אלמנטים קיימים במערך. זו אולי אי הנוחות הגדולה ביותר בשימוש ב- ArrayList. LinkedList היא רשימה כפולה של קישורי אלמנטים. לפיכך, כדי לגשת לאלמנט שבמרכז, עליך לחפש מההתחלה ועד הסוף של הגיליון. מצד שני, הוספה והסרה של אלמנט ב-LinkedList היא מהירה יותר מכיוון שפעולות אלו רק משנות את הרשימה עצמה. להלן השוו הזמנים הגרועים ביותר:

שיטה	רשימת מערך	רשימה מקושרת
get(index)	O(1)	עַל)
הוסף (E)	עַל)	O(1)
add(E, index)	עַל)	עַל)
להסיר (אינדקס)	עַל)	עַל)
Iterator.remove()	עַל)	O(1)
Iterator.add(E)	עַל)	O(1)

למרות זמן הריצה, השימוש בזיכרון חייב להיחשב בנפרד עבור רשימות גדולות. ב-LinkedList, לכל צומת חייבים להיות לפחות שני מצביעים נוספים כדי לקשר את הצמתים הקודמים והבאים, בעוד שב-ArrayList יש צורך במערך של אלמנטים בלבד. השוואות נוספות של רשימות ArrayList, LinkedList ו-Vector . 2. מקבילה יעילה להסרת אלמנטים במהלך איטרציה של אוסף הדרך הנכונה היחידה לשנות (להסיר אלמנטים) אוסף במהלך איטרציה היא להשתמש ב-Iterator.remove() . לדוגמה: השגיאה הנפוצה ביותר היא: תקבל ConcurrentModificationException בזמן הפעלת הקוד למעלה. זה קורה בגלל שהאיטרטור נוצר כדי לעבור ברשימה כולה, אבל באותו זמן הגיליון משתנה על ידי קריאה ל-Iterator.remove(). כפי שנכתב בתיעוד לחריג זה,

Iterator
   itr = list.iterator(); while(itr.hasNext()) { // do something itr.remove(); }

for(Integer i: list) { list.remove(i); }

"לא מותר בדרך כלל לשרשור אחד לשנות אוסף בזמן שרשור אחר חוזר עליו."

באופן כללי, זה לא מקובל ששרשור אחד ישנה אוסף בזמן שרשור אחר חוצה אותו. 3. כיצד להמיר רשימה למערך int[]? הדרך הקלה ביותר לעשות זאת היא להשתמש ב-ArrayUtils , הממוקם בספריית Apache Commons Lang . int[] array = ArrayUtils.toPrimitive(list.toArray(new Integer[0])); אין קיצור דרך לביטוי זה ב-JDK. זכור שאינך יכול להשתמש ב- List.toArray() מכיוון שהביטוי הזה ממיר רשימה למספר שלם[] (שאיננו סוג פרימיטיבי). הדרך הנכונה תהיה האפשרות הבאה: int[] array = new int[list.size()]; for(int i=0; i < list.size(); i++) { array[i] = list.get(i); } 4. כיצד להמיר מערך int[] לרשימה? הדרך הקלה ביותר היא גם להשתמש ב-ArrayUtils בספריית Apache Commons Lang , כמו לעיל. List list = Arrays.asList(ArrayUtils.toObject(array)); כמו כן, אין קיצור דרך לביטוי זה ב-JDK. 5. מהי הדרך הטובה ביותר לסנן את האוסף? אתה יכול להשתמש בחבילות של צד שלישי כגון Guava או Apache Commons Lang כדי להגביר את הפונקציונליות. לשתי החבילות הללו יש שיטת filter() (במחלקה Collections2 מ-Guava ו- CollectionUtils מ-Apache). שיטת filter() תחזיר אלמנטים התואמים לפרדיקט הנתון. ב-JDK הכל יותר מסובך. החדשות הטובות הן שהפרדיקטים יתווספו ב-Java 8 , אך לעת עתה עליכם להשתמש ב-Iterator כדי לחזור על כל האוסף. כמובן, אתה יכול לחקות את הנתיב שאחריו עוקבים Guava ו- Apache על ידי היכרות עם ממשק Predicate החדש. כעת נוכל להשתמש בקוד הבא כדי לסנן את האוסף: 6. כיצד להמיר בקלות רשימה לסט? ישנן שתי דרכים לעשות זאת, תלוי איך אתה רוצה להגדיר שוויון. קטע הקוד הראשון מכניס את הרשימה ל-HashSet. הכפילות במקרה זה נקבעת בעיקר על ידי hashCode(). בדרך כלל זה יעבוד. אבל אם אתה צריך לקחת בחשבון את נתיב ההשוואה, אז עדיף להשתמש בחלק השני של הקוד, שבו אתה יכול להגדיר את המשווה שלך. 7. כיצד אוכל להסיר רכיבים כפולים מ-ArrayList? שאלה זו קשורה במידה מסוימת לשאלה שלמעלה. אם סדר האלמנטים ב-ArrayList לא משנה לך, צעד חכם יהיה למקם את הגיליון ב-Set כדי להסיר כפילויות, ולאחר מכן להחזיר אותו ל-List. להלן דוגמה. אם סדר האלמנטים חשוב לך, אז ניתן להבטיח את הסדר על ידי הצבת הרשימה ב- LinkedHashSet , שנמצא ב-JDK הסטנדרטי. 8. אוסף ממוין

int[] array = {1,2,3,4,5}; List
   list = new ArrayList
   
    (); for(int i: array) { list.add(i); }

Iterator
   itr = list.iterator(); while(itr.hasNext()) { int i = itr.next(); if (i > 5) { // filter all ints bigger than 5 itr.remove(); } }

public interface Predicate
   { boolean test(T o); } public static 
   
    void filter(Collection
    
     collection, Predicate
     
      predicate) { if ((collection != null) && (predicate != null)) { Iterator
      
       itr = collection.iterator(); while(itr.hasNext()) { T obj = itr.next(); if (!predicate.test(obj)) { itr.remove(); } } } }

filter(list, new Predicate
   () { public boolean test(Integer i) { return i <= 5; } });

Set
   set = new HashSet
   
    (list);

Set
   set = new TreeSet
   
    (aComparator); set.addAll(list);

ArrayList** list = ... // initial a list with duplicate elements Set
   set = new HashSet
   
    (list); list.clear(); list.addAll(set);

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

Collections.sort() יכול למיין רשימה. כפי שצוין בתיעוד Java, מיון זה יציב ומבטיח ביצועים של n log(n).
PriorityQueue מספק תור מסודר. ההבדל בין PriorityQueue לבין Collections.sort() הוא ש-PriorityQueue שומר על סדר התור כל הזמן, אבל אתה יכול לקבל רק את האלמנט הראשון של התור. אתה לא יכול לגשת באופן אקראי לרכיב כמו PriorityQueue.get(4).
אם אין כפילויות באוסף, אתה יכול לבחור TreeSet . כמו כן, כמו PriorityQueue, TreeSet שומר על סט מסודר בכל עת. אתה יכול לקבל את האלמנט הקטן או הגדול ביותר מ-TreeSet, אבל עדיין לא תהיה לך גישה אקראית לאלמנטים.

במילים פשוטות, Collections.sort() מספק רשימה מסודרת חד פעמית. PriorityQueue ו-TreeSet שומרים על אוסף מסודר בכל עת, במחיר של חוסר גישה לאינדקס לאלמנטים. 9. Collections.emptyList() או מופע חדש. אותה שאלה חלה על emptyMap() ו-emptySet(). שתי השיטות מחזירות רשימה ריקה, אבל Collections.emptyList() היא רשימה בלתי ניתנת לשינוי. משמעות הדבר היא שאינך יכול להוסיף אלמנטים חדשים לרשימה "ריקה". ברקע, כל קריאה למתודה Collections.emptyList() לא יוצרת למעשה מופע חדש של הרשימה הריקה. במקום זאת, הוא יעשה שימוש חוזר במופע הריק שכבר קיים. אם אתם מכירים את Singleton כתבנית עיצובית , כדאי שתבינו למה הכוונה. זה אמור לתת לך ביצועים טובים יותר אם קוראים לך לעתים קרובות. 10 העתקת אוסף, Collections.copy() קיימות שתי דרכים להעתיק רשימת מקורות לרשימת יעדים. דרך אחת היא להשתמש בבנאי ArrayList. דרך נוספת היא להשתמש בשיטת Collections.copy() . שים לב בשורה הראשונה: אנו מקצים רשימה שאורכה לפחות זהה לאורכה של הרשימה המקורית, מכיוון שתיעוד Java על אוספים אומר:

ArrayList
   dstList = new ArrayList
   
    (srcList);

רשימת היעד חייבת להיות ארוכה לפחות כמו רשימת המקורות.

מה שאומר שהרשימה הסופית חייבת להיות לא קצרה מהרשימה המקורית. שתי השיטות הן העתקה רדודה. אז מה ההבדל בין שתי השיטות הללו? ראשית, Collections.copy() לא יקצה מחדש את קיבולת האיסוף של dstList, גם אם ל-dstList אין מספיק מקום להכיל את כל האלמנטים מה-srcList. במקום זאת, הוא יזרוק IndexOutOfBoundsException . אפשר לשאול אם יש בזה תועלת. הסיבה היא שזה מבטיח שהשיטה פועלת באופן ליניארי בזמן. זה מתאים גם כאשר אתה רוצה לעשות שימוש חוזר במערכים במקום להקצות מחדש זיכרון בבנאי ArrayList. במקום מסקנה אם לאחר קריאת המאמר עדיין יש לך שאלות, אתה מוזמן לשאול אותן בתגובות. כמו כן, אם תמצא אי דיוק בתרגום או כל טעות אחרת, כתוב לראש הממשלה, זה יתוקן, ותודה לך. מְקוֹרִי.

ArrayList
   dstList = new ArrayList
   
    (srcList.size()); Collections.copy(dstList, srcList);