בקצרה על העיקר - Java Collections Framework

תחילת הדרך

היום אני רוצה לדבר על נושא כל כך מעניין כמו " מסגרת אוספי Java " או, במילים פשוטות, על אוספים. רוב עבודת הקוד היא עיבוד נתונים בצורה כזו או אחרת. קבל רשימת משתמשים, קבל רשימת כתובות וכו'. איכשהו למיין אותם, לבצע חיפוש, להשוות ביניהם. זו הסיבה שידע באוספים נחשב למיומנות ליבה. לכן אני רוצה לדבר על זה. בנוסף, אחת השאלות הנפוצות ביותר בראיונות למפתחי Java היא אוספים. לדוגמה, "צייר היררכיה של אוספים". המהדר המקוון יעזור לנו בדרכנו. לדוגמה, אתה יכול להשתמש ב- " Tutorialspoint Online Java Compiler " או ב-Repl.it. הדרך להכרת מבני נתונים כלשהם מתחילה במשתנים רגילים (Variables). באתר אורקל, נושאים שונים מיוצגים כ"נתיבים" או Trails. לכן, הדרך להיכרות עם ג'אווה נקראת " מסלול: לימוד שפת ג'אווה: תוכן עניינים ". והיסודות של השפה (כלומר יסודות השפה) מתחילים במשתנים. לכן, בואו נכתוב קוד פשוט:

public static void main(String[] args) {
	String user = "Max";
	System.out.println("Hello, " + user);
}

זה טוב בכל דבר, חוץ מזה שאנחנו מבינים שהקוד הזה טוב ויפה רק למשתנה אחד. מה לעשות אם יש כמה מהם? מערכים הומצאו לאחסון נתונים מסוג אחד. באותו Trail מאורקל ישנו קטע נפרד המוקדש למערכים. סעיף זה נקרא: " מערכים ". העבודה עם מערכים היא גם די פשוטה:

import java.util.Arrays;
class Main {
  public static void main(String[] args) {
    String[] users = new String[2];
    users[0] = "Max";
    users[1] = "John";
    System.out.println("Hello, " + Arrays.toString(users));
  }
}

מערכים פותרים את הבעיה של אחסון ערכים מרובים במקום אחד. אבל הוא מטיל מגבלה: גודל המערך קבוע. אם, כמו בדוגמה, אמרנו שגודל = 2, אז זה שווה לשניים. זה הכל. אם אנחנו רוצים מערך גדול יותר, אנחנו צריכים ליצור מופע חדש. כמו כן, מציאת אלמנט היא גם דבר מסובך עבור מערך. יש שיטה Arrays.binarySearch, אבל החיפוש הזה עובד רק על מערך ממוין (עבור מערך לא ממוין, התוצאה לא מוגדרת או פשוט בלתי צפויה). כלומר, החיפוש יחייב אותנו למיין בכל פעם. מחיקה גם רק מנקה את הערך. לכן, אנחנו עדיין לא יודעים כמה נתונים יש באמת במערך, אנחנו יודעים רק כמה תאים יש במערך. כדי לרענן את הידע שלך על מערכים:

• " JavaRush: מערכים ב-Java "
• " מדריך Java: מערכים "

וכתוצאה מפיתוח שפת Java, הופיעה מסגרת אוספי Java ב-JDK 1.2, עליה נדבר היום.

אוסף

התחילו לעלות מההתחלה. למה אוספים? המונח עצמו מגיע מדברים כמו "תורת הסוגים" ו"סוגי נתונים מופשטים". אבל אם אתה לא מסתכל על עניינים גבוהים, אז כשיש לנו כמה דברים, אנחנו יכולים לקרוא להם "אוסף של דברים". אלו שאוספים חפצים. באופן כללי, המילה לאסוף עצמה מגיעה מ-Lat. collectio "איסוף, איסוף". כלומר, אוסף הוא אוסף של משהו, מיכל לאלמנטים מסוימים. אז יש לנו אוסף של אלמנטים. מה אולי נרצה לעשות עם זה: כפי שאתה יכול לראות, אולי נרצה דברים הגיוניים למדי. אנחנו גם מבינים שאולי נרצה לעשות משהו עם מספר אוספים: בהתאם לכך, מפתחי Java כתבו את ממשק java.util.Collection כדי לתאר התנהגות כללית זו עבור כל האוספים . ממשק האוסף הוא המקום שבו מקורם של כל האוספים. אוסף הוא רעיון, זה רעיון של איך כל האוספים צריכים להתנהג. לכן, המונח "אוסף" מתבטא כממשק. מטבע הדברים, ממשק זקוק למימושים. לממשק java.util.Collectionיש מחלקה אבסטרקטית AbstractCollection, כלומר "אוסף מופשט" כלשהו, ​​המייצג את השלד עבור יישומים אחרים (כפי שנכתב ב-JavaDoc מעל המחלקה java.util.AbstractCollection). אם כבר מדברים על אוספים, בואו נחזור ונזכור שאנחנו רוצים לחזור עליהם. זה אומר שאנחנו רוצים לחזור על האלמנטים אחד אחד. זה מושג חשוב מאוד. לכן, הממשק Collectionעובר בירושה מ- Iterable. זה מאוד חשוב כי... ראשית, כל מה ש-Iterable חייב להיות מסוגל להחזיר איטרטור על סמך התוכן שלו. ושנית, כל מה ש-Iterable יכול לשמש בלולאות for-each-loop. ובעזרת איטרטור מיושמות AbstractCollectionשיטות כגון contains, . והדרך להבנת אוספים מתחילה באחד ממבני הנתונים הנפוצים ביותר - רשימה, כלומר. . toArrayremoveList

רשימות

אז, רשימות תופסות מקום חשוב בהיררכיית האוספים: כפי שאנו יכולים לראות, רשימות מיישמות את ממשק java.util.List . רשימות מבטאות שיש לנו אוסף של אלמנטים המסודרים ברצף כלשהו בזה אחר זה. לכל אלמנט יש אינדקס (כמו במערך). בדרך כלל, רשימה מאפשרת לך לקבל אלמנטים עם אותו ערך. כפי שאמרנו לעיל, Listהוא יודע על האינדקס של האלמנט. זה מאפשר לך לקבל ( get) אלמנט לפי אינדקס או להגדיר ערך עבור אינדקס ספציפי ( set). שיטות איסוף add, addAll, removeמאפשרות לך לציין את האינדקס שממנו לבצע אותן. בנוסף, ל-y Listיש גרסה משלו של איטרטור בשם ListIterator. איטרטור זה יודע על האינדקס של האלמנט, כך שהוא יכול לחזור לא רק קדימה אלא גם אחורה. ניתן אפילו ליצור אותו ממקום מסוים באוסף. בין כל ההטמעות, ישנם שניים הנפוצים ביותר: ArrayListו LinkedList. ראשית, ArrayListזוהי רשימה ( List) המבוססת על מערך ( Array). זה מאפשר לך להשיג "גישה אקראית" לאלמנטים . גישה אקראית היא היכולת לאחזר מיד אלמנט לפי אינדקס, במקום לחזור על כל האלמנטים עד שנמצא את האלמנט עם האינדקס הרצוי. המערך כבסיס הוא שמאפשר להשיג זאת. להיפך, LinkedListזוהי רשימה מקושרת. כל ערך ברשימה מקושרת מיוצג בטופס Entry, המאחסן את הנתונים עצמם, כמו גם קישור אל הבא (הבא) והקודם (הקודם) Entry. כך LinkedListמיישם "גישה רציפה " . ברור שכדי למצוא את האלמנט ה-5 נצטרך לעבור מהיסוד הראשון לאחרון, כי אין לנו גישה ישירה לאלמנט החמישי. אנחנו יכולים לגשת אליו רק מהאלמנט הרביעי. ההבדל בתפיסה שלהם ניתן להלן: בעבודה, כפי שאתם מבינים, יש גם הבדל. למשל, הוספת אלמנטים. האלמנטים LinkedListפשוט מחוברים כמו חוליות בשרשרת. אבל ArrayListהוא מאחסן אלמנטים במערך. ומערך, כידוע, אינו יכול לשנות את גודלו. איך זה עובד אז ArrayList? וזה עובד מאוד פשוט. כשהשטח במערך נגמר, הוא גדל פי 1.5. הנה קוד הזום: int newCapacity = oldCapacity + (oldCapacity >> 1); הבדל נוסף בפעולה הוא כל היסט של אלמנטים. לדוגמה, בעת הוספה או הסרה של אלמנטים לאמצע. כדי להסיר LinkedListמאלמנט, פשוט הסר הפניות לרכיב זה. במקרה של , ArrayListאנו נאלצים להעביר את האלמנטים בכל פעם באמצעות ה- System.arraycopy. לפיכך, ככל שיותר אלמנטים, כך יהיה צורך לבצע יותר פעולות. תיאור מפורט יותר ניתן למצוא במאמרים הבאים:

• " מבני נתונים בתמונות. ArrayList "
• " מבני נתונים בתמונות. LinkedList "
• " מה יש מתחת למכסה המנוע של LinkedList? "

לאחר בחינת ArrayList, אי אפשר שלא לזכור את "קודמתה", המחלקה java.util.Vector . זה שונה Vectorבכך ArrayListששיטות העבודה עם האוסף (הוספה, מחיקה וכו') מסונכרנות. כלומר, אם חוט אחד ( Thread) מוסיף אלמנטים, אז חוטים אחרים ימתינו עד שהשרשור הראשון יסיים את עבודתו. מכיוון שבטיחות שרשור לרוב אינה נדרשת, מומלץ להשתמש במחלקה במקרים כאלה ArrayList, כפי שצוין במפורש ב-JavaDoc עבור המחלקה Vector. בנוסף, Vectorהוא מגדיל את גודלו לא פי 1.5, ArrayListאלא פי 2. אחרת, ההתנהגות זהה - Vectorאחסון האלמנטים בצורה של מערך מוסתר ולהוספה/הסרה של אלמנטים יש אותן השלכות כמו ב ArrayList. למעשה, Vectorנזכרנו בזה מסיבה מסוימת. אם נסתכל ב-Javadoc, נראה ב-"Direct Known Subclasses" מבנה כמו java.util.Stack . המחסנית היא מבנה מעניין שהוא last-in-first-outמבנה LIFO (אחרון נכנס, ראשון יוצא). מחסנית מתורגמת מאנגלית היא מחסנית (כמו ערימת ספרים, למשל). המחסנית מיישמת שיטות נוספות: peek(תסתכל, תסתכל), pop(דחיפה), push(דחיפה). השיטה peekמתורגמת למראה (לדוגמה, הצצה בתוך התיק מתורגמת ל"הסתכל בתוך התיק ", והצצה דרך חור המנעול מתורגמת ל"הצצה דרך חור המנעול "). שיטה זו מאפשרת לך להסתכל על "החלק העליון" של הערימה, כלומר. קבל את האלמנט האחרון מבלי להסיר (כלומר מבלי להסיר) אותו מהערימה. השיטה pushדוחפת (מוסיפה) אלמנט חדש אל המחסנית ומחזירה אותו, ושיטת האלמנטים popדוחפת (מסירה) ומחזירה את המוסר. בכל שלושת המקרים (כלומר הצצה, פופ ודחיפה), אנו עובדים רק עם האלמנט האחרון (כלומר "החלק העליון של הערימה"). זוהי התכונה העיקרית של מבנה המחסנית. אגב, ישנה משימה מעניינת להבין ערימות, המתוארת בספר "קריירה של מתכנת" (ראיון פיצוח קידוד) יש משימה מעניינת שבה באמצעות מבנה ה"מחסנית" (LIFO) צריך ליישם את ה"תור". מבנה (FIFO). זה אמור להיראות כך: ניתן למצוא ניתוח של משימה זו כאן: " יישום תור באמצעות ערימות - ה-ADT של תור ("יישום תור באמצעות ערימות" ב-LeetCode) ". אז אנחנו עוברים בצורה חלקה למבנה נתונים חדש - תור.

תוֹר

תור הוא מבנה המוכר לנו מהחיים. תורים לחנויות, לרופאים. מי שהגיע ראשון (First In) יהיה הראשון שיצא מהתור (First Out). ב-Java, תור מיוצג על ידי ממשק java.util.Queue . לפי Javadoc של התור, התור מוסיף את השיטות הבאות: כפי שניתן לראות, ישנן שיטות הזמנה (אי ביצוען טומן בחובו חריג) וישנן שיטות בקשה (חוסר היכולת לבצע אותן אינו מוביל לטעויות). אפשר גם לקבל את האלמנט מבלי להסיר אותו (הצצה או אלמנט). לממשק התור יש גם יורש שימושי - Deque . זהו מה שנקרא "תור דו כיווני". כלומר, תור כזה מאפשר לך להשתמש במבנה הזה גם מההתחלה וגם מהסוף. התיעוד אומר כי "אפשר להשתמש ב-Deques גם כ-LIFO (Last-In-First-Out) ערימות. יש להשתמש בממשק זה עדיפות למחלקת Stack legacy.", כלומר, מומלץ להשתמש ביישום Deque במקום לַעֲרוֹם. ה-Javadoc מראה אילו שיטות מתאר ממשק Deque: בוא נראה אילו יישומים יש. ונראה עובדה מעניינת - LinkedList נכנסה למחנה התורים) כלומר, LinkedList מיישמת גם List, וגם Deque. אבל יש גם "תורים בלבד", למשל PriorityQueue. לא זוכרים אותה לעתים קרובות, אבל לשווא. ראשית, אתה לא יכול להשתמש ב"אובייקטים שאינם ניתנים להשוואה" בתור זה, כלומר. יש לציין Comparator או שכל האובייקטים חייבים להיות ברי השוואה. שנית, "הטמעה הזו מספקת זמן O(log(n)) עבור שיטות התור והתור". יש סיבה למורכבות לוגריתמית. מיושם PriorityQueue על סמך הערימה. ה-Javadoc אומר: "תור עדיפות מיוצג כערימה בינארית מאוזנת". האחסון עצמו עבור זה הוא מערך רגיל. שגדל כשצריך. כאשר הערימה קטנה, היא גדלה פי 2. ואז ב-50%. הערה מהקוד: "גודל כפול אם קטן; אחרת גדל ב-50%". תור עדיפות וערימה בינארית הם נושא נפרד. אז למידע נוסף:

• מאמר סופר על Habré: " מבני נתונים. מדריך לא פורמלי "
• הסבר ברור על ה"ערימה": " פוקספורד: מדעי המחשב. מבני נתונים: ערימה "
• מאמר מהבר על ערימה בינארית: " מבני נתונים: ערימה בינארית "
• " מבוא לערמות בינאריות (MaxHeaps) "

מימוש java.util.Dequeיכול להיות המחלקה java.util.ArrayDeque . כלומר, ניתן ליישם רשימות באמצעות רשימה מקושרת ומערך, וניתן ליישם תורים גם באמצעות מערך או באמצעות רשימה מקושרת. לממשקי Queueו Dequeיש צאצאים המייצגים את "תור החסימה": BlockingQueueו BlockingDeque. להלן השינוי בממשק בהשוואה לתורים רגילים: בואו נסתכל על כמה דוגמאות לחסימת תורים. אבל הם מעניינים. לדוגמה, BlockingQueue מיושם על ידי: PriorityBlockingQueue , SynchronousQueue , ArrayBlockingQueue, DelayQueue , LinkedBlockingQueue . אבל BlockingDequeהם מיישמים הכל ממסגרות האוסף הסטנדרטיות LinkedBlockingDeque. כל תור הוא נושא לסקירה נפרדת. ובמסגרת סקירה זו, נציג את היררכיית הכיתה לא רק עם List, אלא גם עם Queue: כפי שאנו יכולים לראות מהתרשים, הממשקים והמחלקות של Java Collections Framework שלובים מאוד זה בזה. בואו נוסיף עוד ענף בהיררכיה - Set.

מַעֲרֶכֶת

Set- תורגם כ"סט". הוא שונה מתור ומרשימה Setבהפשטה הגדולה יותר שלו על פני אחסון אלמנטים. Set- כמו שקית של חפצים, שם לא ידוע כיצד ממוקמים החפצים ובאיזה סדר הם מונחים. ב-Java, קבוצה כזו מיוצגת על ידי ממשק java.util.Set . כפי שאומר התיעוד, Setזהו "אוסף שאינו מכיל אלמנטים כפולים". מעניין שהממשק עצמו Setלא מוסיף שיטות חדשות לממשק Collection, אלא רק מבהיר את הדרישות (על מה לא צריך להכיל כפילויות). בנוסף, מהתיאור הקודם עולה שאי אפשר פשוט Setלקבל ממנו אלמנט. איטרטור משמש כדי לקבל אלמנטים. Setיש עוד כמה ממשקים הקשורים אליו. הראשון הוא SortedSet. כפי שהשם מרמז, SortedSetזה מציין שקבוצה כזו ממוינת, ולכן האלמנטים מיישמים את הממשק Comparableאו מצוינים Comparator. בנוסף, SortedSetהוא מציע מספר שיטות מעניינות: בנוסף, ישנן שיטות first(האלמנט הקטן ביותר לפי ערך) ו- last(האלמנט הגדול ביותר לפי ערך). יש SortedSetיורש - NavigableSet. מטרת ממשק זה היא לתאר את שיטות הניווט הדרושות לזיהוי מדויק יותר של אלמנטים מתאימים. דבר מעניין הוא NavigableSetשהוא מוסיף לאיטרטור הרגיל (שהולך מהקטן לגדול) איטרטור לסדר הפוך - descendingIterator. בנוסף, NavigableSetהוא מאפשר לך להשתמש בשיטה descendingSetכדי לקבל תצוגה של עצמך (View), שבה האלמנטים נמצאים בסדר הפוך. זה נקרא Viewמכיוון שבאמצעות האלמנט שנוצר אתה יכול לשנות את האלמנטים של האלמנט המקורי Set. כלומר, בעצם, מדובר בייצוג של הנתונים המקוריים בצורה אחרת, ולא העתק שלהם. מעניין, NavigableSet, כמו Queue, יכול להתמודד עם אלמנטים pollFirst(מינימליים) ו- pollLast(מקסימליים). כלומר, הוא מקבל את האלמנט הזה ומסיר אותו מהסט. איזה סוג של יישומים יש? ראשית, המימוש המפורסם ביותר מבוסס על קוד hash - HashSet . יישום נוסף לא פחות מוכר מבוסס על עץ אדום-שחור - TreeSet . בואו נשלים את התרשים שלנו: בתוך האוספים נותר לסדר את ההיררכיה – המתבודדים. שבמבט ראשון עומד בצד - java.util.Map.

מפות

מפות הן מבנה נתונים שבו הנתונים מאוחסנים לפי מפתח. לדוגמה, המפתח יכול להיות מזהה או קוד עיר. ועל ידי מפתח זה יתבצע חיפוש בנתונים. מעניין שהכרטיסים מוצגים בנפרד. לפי המפתחים (ראה " שאלות נפוצות בנושא עיצוב API של Java Collections API "), מיפוי מפתח-ערך אינו אוסף. וניתן לחשוב על מפות מהר יותר כאוסף של מפתחות, אוסף של ערכים, אוסף של זוגות מפתח-ערך. זו חיה כל כך מעניינת. אילו שיטות מספקים כרטיסים? בואו נסתכל על ממשק Java API java.util.Map . כי מכיוון שמפות אינן אוספים (הן אינן יורשות מאוספים), הן אינן מכילות contains. וזה הגיוני. מפה מורכבת ממפתחות וערכים. אילו מאלה השיטה צריכה לבדוק containsואיך לא להתבלבל? לכן, לממשק Mapיש שתי גרסאות שונות: containsKey(מכיל מפתח) ו- containsValue(מכיל ערך). השימוש בו keySetמאפשר לך לקבל סט מפתחות (אותו אחד Set). ובאמצעות השיטה valuesנוכל לקבל אוסף ערכים במפה. המפתחות במפה הם ייחודיים, דבר המודגש על ידי מבנה הנתונים Set. ניתן לחזור על ערכים, דבר המודגש על ידי מבנה הנתונים של איסוף. בנוסף, באמצעות השיטה entrySetנוכל להשיג קבוצה של צמדי מפתח-ערך. אתה יכול לקרוא עוד על אילו מימושי כרטיסים קיימים בניתוחים המפורטים ביותר:

• " מבני נתונים בתמונות. HashMap "
• " מבני נתונים בתמונות. LinkedHashMap "
• " פעולה פנימית של HashMap ב-Java (עדכון עבור Java 8) "

אני גם רוצה לראות מה HashMapמאוד דומה ל HashSet, TreeMapול TreeSet. יש להם אפילו ממשקים דומים: NavigableSetו NavigableMap, SortedSetו SortedMap. אז המפה הסופית שלנו תיראה כך: אפשר לסיים בעובדה המעניינת שהקולקציה Setמשתמשת באופן פנימי Map, כאשר הערכים המוספים הם מפתחות, והערך זהה בכל מקום. זה מעניין כי זה Mapלא אוסף והחזרות Setשהוא אוסף אבל למעשה מיושם כ Map. קצת סוריאליסטי, אבל ככה זה יצא)

סיכום

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

• " אורקל שביל: אוספים "
• " מדריך IBM: אוספי ג'אווה "
• " יורי טקך: ג'אווה מתקדמת - אוספים "
• " אוספי ג'אווה: הכוח מתעורר מאת ראול-גבריאל אורמה וריצ'רד וורברטון "
• " טימור בטירשינוב: 22 - יסודות ג'אווה. אוספים (והסרטונים הבאים מהפלייליסט) "
• " חמישה דברים שלא ידעת עליהם... ה-API של Java Collections "

#ויאצ'סלב