انتقل إلى المحتوى
أمين أبوزيد
Englishالعربية
منشورBEG-030-L06

اختيار المجموعة: مخطط القرار

  • الدرس 6 من 9
  • 11 دقيقة قراءة
  • مبتدئ
في هذا الدرس 11 موضوعات

هذا الدرس متاح حاليًا باللغة الإنجليزية فقط، ولم تُنشر نسخته العربية بعد.

Lesson Overview

You now know the four families and their main implementations. The skill that separates a beginner from a working developer is choosing: looking at a requirement and picking the right collection in a few seconds, then being able to defend the choice in a code review.

This lesson turns the previous five into one decision procedure: a short list of questions, asked in order, that ends at a class name. We also add the three things that are easy to forget: how to move data between collections, how to keep the variable type general, and when to stop agonizing and just use the default.

This lesson builds on Lessons 1 to 5.

Learning Objectives

By the end of this lesson you will be able to:

  • Follow a two-step chart: first pick the family, then pick the ordering.
  • Map a written requirement to List, Set, Map, Queue, or Deque.
  • Pick Hash*, Linked*, or Tree* from the ordering requirement.
  • Justify a choice in one sentence using words such as unique, by key, in order, sorted, and front.
  • Convert between collections with copy constructors.
  • Declare variables by interface type, and name the one case where a concrete type is acceptable.

Written Explanation

Step 1: pick the family by what you must do

Ask these questions in order and stop at the first "yes".

  1. Do I look things up by a key, getting a value back? Use a Map. (Product by code, customer by id, count by word.)
  2. Must every element be unique, and do I mainly ask "is it in there?" Use a Set.
  3. Will I process elements in arrival order, or from the ends only? Use a Queue or Deque. (Waiting line: Queue. Undo or both ends: Deque. Most urgent first: PriorityQueue.)
  4. Otherwise (I need order, duplicates are fine, and I access by position or just loop over everything): use a List.

Two cautions. First, the order of the questions matters: a "list of customers I look up by id" fails question 1, so it is a Map, not a List. Second, a family can hide inside another: counting words is a Map whose values are numbers, and grouping is a Map whose values are lists.

Step 2: pick the ordering and implementation

Once the family is known, ask what order the iteration must show.

NeedListSetMapQueue / Deque
No special order, best speedArrayListHashSetHashMapArrayDeque
Insertion orderArrayList (already ordered)LinkedHashSetLinkedHashMapArrayDeque (arrival order)
Sorted ordersort the list when needed (BEG-032)TreeSetTreeMapPriorityQueue (head only)

A list is always in insertion order, since you control positions, so "sorted" for a list means sorting it explicitly; that is covered in BEG-032 (ordering with Comparable and Comparator). A TreeSet or TreeMap keeps itself sorted, at a small cost per operation, and the elements or keys must be comparable with each other.

A quick cost picture

Without numbers, the rough costs from the Java documentation and from Lessons 2 to 5 are:

TaskArrayListHashSet / HashMapTreeSet / TreeMapArrayDeque
Is X present / find by key?Scan the listAbout constantLogarithmic (guaranteed)Scan
Read the n-thConstantNot applicableNot applicableNot applicable
Add at the endCheap on averageAbout constantLogarithmicCheap at either end
Keeps sorted orderNoNoYesNo

"About constant" assumes good hashing; "logarithmic" grows very slowly as data grows; "scan" means the time grows in step with the size. Lesson 9 measures the gap between scan and about constant, so you can see it for yourself.

Declare general, create specific

Whatever you pick, declare by interface: List<String>, Set<String>, Map<String, Integer>, Queue<String>, Deque<String>. Create by class on the right-hand side. If you later find that a LinkedHashSet would suit better than a HashSet, you change one word. For method parameters that only read, a general type such as Collection<String> is even more flexible.

The exception: declare the concrete class when you need methods that only it has. TreeSet<Integer> ts lets you call first() and last(); LinkedList<String> lets you call addFirst (and so does the Deque interface). If you only need peek and poll, use Queue.

Moving data between collections

Every collection class has a constructor that copies from another collection. This lets you change your mind cheaply:

java
List<String> sortedDistinct = new ArrayList<>(new TreeSet<>(words));  // unique + sorted
List<String> firstSeen = new ArrayList<>(new LinkedHashSet<>(words)); // unique, original order

Conversions copy: the new collection is independent of the old one. Use them to de-duplicate, to sort distinct values, or to take a mutable copy of an unmodifiable List.of(...).

When you are unsure

Start with the default for the family: ArrayList, HashSet, HashMap, ArrayDeque. Move to Linked* when order of insertion matters, to Tree* when sorted order matters. Treat LinkedList as a special tool, not a default. And do not agonize: because you declared by interface, a wrong first guess costs you one line, not a rewrite.

Examples

Example 1: five requirements, five declarations (simple)

java
List<String> steps = new ArrayList<>();          // ordered steps, positions matter
Set<String> visitors = new LinkedHashSet<>();    // unique, in order first seen
Set<String> sortedTags = new TreeSet<>();        // unique and always sorted
Map<Integer, String> nameById = new HashMap<>(); // look up by id, no order needed
Queue<String> jobs = new ArrayDeque<>();         // first come, first served
Deque<String> history = new ArrayDeque<>();      // newest first, like a stack

Each comment states the requirement in plain words, which is exactly what you should be able to say about every collection you write. Filling them with one value each (sortedTags with z then b) printed [a] [v1] [b, z] {1=Ana} [j1] [h1].

Example 2: the wrong choice, then the right one (practical)

java
record Customer(int id, String name) {}

static Customer findSlow(List<Customer> list, int id) {
    for (Customer c : list) if (c.id() == id) return c;
    return null;
}

// in main: fill both a list and a map with the same five customers
Map<Integer, Customer> byId = new HashMap<>();
// ... byId.put(c.id(), c) for each customer
System.out.println(findSlow(list, 4));
System.out.println(byId.get(4));
System.out.println(byId.get(99));

Output:

text
Customer[id=4, name=C4]
Customer[id=4, name=C4]
null

(The record is the compact class form previewed in BEG-026-L05; it prints itself in this style.) Both lookups give the same answer on five customers, so the mistake is invisible. On a million customers the list version scans up to a million entries per call while the map jumps to the entry. The requirement, "find by id", should have pointed to Map at question 1 of the chart.

Example 3: one small system, three collections (realistic)

java
String[] orders = {"ana:book", "omar:pen", "ana:bag", "lina:pen", "ana:book"};
Map<String, List<String>> byCustomer = new TreeMap<>();
Set<String> products = new TreeSet<>();
Queue<String> toShip = new ArrayDeque<>();
for (String o : orders) {
    String[] p = o.split(":");
    if (!byCustomer.containsKey(p[0])) byCustomer.put(p[0], new ArrayList<>());
    byCustomer.get(p[0]).add(p[1]);
    products.add(p[1]);
    toShip.offer(o);
}
System.out.println(byCustomer);
System.out.println(products);
System.out.println(toShip.poll() + " then " + toShip.peek());

Output:

text
{ana=[book, bag, book], lina=[pen], omar=[pen]}
[bag, book, pen]
ana:book then omar:pen

The justification, one line each. byCustomer: look up a customer's orders by name, sorted by name, and a customer may order the same product twice, hence a list as the value. products: each product listed once, sorted for a catalog. toShip: orders leave in the order they arrived.

Backend Insight

In code review, "why this collection?" is a normal question, and the answer is a short sentence built from the vocabulary of this lesson. The same reasoning applies to the interfaces you will meet next: a repository returns a List because the caller loops through results in order; a "roles" field is a Set because roles are unique and membership is the question; a cache is a Map because lookup is by key; a task buffer is a Queue.

Choice also affects correctness, not only speed: a List<Role> can hold the same role twice and then every "does the user have the role?" check silently does extra work, while a Set<Role> makes the duplicate impossible. Fixing a wrong structure late, after dozens of methods depend on its quirks, is expensive. Declaring by interface keeps that fix cheap. The internals that make HashMap fast or TreeMap sorted are covered in BEG-040 and BEG-041; for now, trust the contracts and measure when speed matters.

Common Mistakes

Mistake 1: A List where a Map or Set is needed

If you write a loop whose only job is to find an element by value or id, you probably need a Map or a Set. This is the module's most common mistake.

Mistake 2: Choosing by habit

ArrayList for everything works until the first "find by id" or "no duplicates" requirement. Run the four questions every time, even if the answer is usually ArrayList.

Mistake 3: Paying for order you do not need, or missing order you do

TreeMap costs more than HashMap; use it when you need sorted keys. And the reverse: do not rely on HashMap iteration order for anything the user sees.

Mistake 4: Declaring the concrete class in signatures

static ArrayList<String> load() forces every caller and every future change to deal with ArrayList. Return List<String>.

Mistake 5: Forgetting what you copied

new ArrayList<>(set) makes an independent copy. Changing the list does not change the set. If you expected a live view, you will be surprised.

Exercises

Try each exercise yourself before opening the solutions.

Level A: Foundation

A1. For each requirement choose the family (List, Set, Map, Queue/Deque): (a) the temperature readings of a day, in order, repeats allowed; (b) the distinct countries in an address book; (c) the exchange rate for each currency code; (d) tasks waiting for a worker.

أظهر الحل A1

A1. (a) List. (b) Set. (c) Map. (d) Queue.

A2. For each requirement choose the implementation: (a) unique usernames shown alphabetically; (b) unique visitor ids shown in order of first visit; (c) a lookup table where order never matters; (d) a back-button history.

أظهر الحل A2

A2. (a) TreeSet. (b) LinkedHashSet. (c) HashMap. (d) ArrayDeque used as a stack through push and pop.

A3. Which declaration is better, and why: ArrayList<String> a = new ArrayList<>(); or List<String> a = new ArrayList<>();?

أظهر الحل A3

A3. List<String> a = new ArrayList<>();. The variable type is the interface, so the implementation can change in one place and all code uses only list behavior.

Level B: Application

B1. Given List<String> words = List.of("kiwi", "fig", "kiwi", "apple", "fig"), write two lines that produce (a) a list of the distinct words, sorted, and (b) a list of the distinct words in first-seen order. Give both results.

أظهر الحل B1

B1.

java
List<String> sortedDistinct = new ArrayList<>(new TreeSet<>(words));
List<String> firstSeen = new ArrayList<>(new LinkedHashSet<>(words));

Results: [apple, fig, kiwi] and [kiwi, fig, apple].

B2. The code below finds a product price by code in a list of Product objects on every request. Name the problem and describe the better structure in one or two lines.

java
for (Product p : products) {
    if (p.code().equals(code)) return p.price();
}
أظهر الحل B2

B2. It scans the whole list for each request. Keep a Map<String, Product> (or Map<String, Double>) keyed by code and call get(code), handling the null result for an unknown code.

B3. A teammate's method is declared static HashSet<String> uniqueNames(ArrayList<String> in). Rewrite the signature so that callers can pass any list and the implementation can change.

أظهر الحل B3

B3. static Set<String> uniqueNames(Collection<String> in). Callers can pass any collection, and the method can return a LinkedHashSet or TreeSet without changing the signature.

Level C: Challenge

C1. Build Map<String, Integer> firstIndex for the list in B1, mapping each word to the index of its first occurrence, in first-seen order. Show the result.

أظهر الحل C1

C1.

java
Map<String, Integer> firstIndex = new LinkedHashMap<>();
for (int i = 0; i < words.size(); i++) {
    if (!firstIndex.containsKey(words.get(i))) firstIndex.put(words.get(i), i);
}

The result is {kiwi=0, fig=1, apple=3}. Without the containsKey check, later put calls would overwrite the value with the last index (a HashMap would then give kiwi=2 and fig=4).

C2. A chat app needs: (1) the set of users currently online, (2) each user's unread messages, in arrival order, (3) the 50 most recent chat rooms the user opened, newest first. Pick a collection for each and give a one-sentence reason.

أظهر الحل C2

C2. (1) Set<String>, because a user is online or not and membership checks must be fast. (2) Map<String, Queue<String>> keyed by user, with a queue per user, because messages are read in arrival order. (3) Deque<String> (an ArrayDeque), pushing newest to the front and removing from the back when it exceeds 50, because newest-first and trimming the oldest are both end operations.

Mini Challenge

Take this requirement text and, for each noun in bold, write the declaration with a one-line justification:

A library tracks the books on each shelf in order, the set of members who currently have a loan (no repeats), each member's loan count looked up by member id, the reservation line for a popular book, and the list of genres shown alphabetically without repeats.

Check your work: five declarations, all with interface types on the left, each justified by one of the words order, unique, by key, waiting line, sorted. Do not forget the generic type arguments.

Summary & Next Lesson

Key takeaways

  • Choose the family first: by key is a Map; unique values is a Set; arrival order or the ends is a Queue/Deque; otherwise a List.
  • Then choose the ordering: Hash* for none, Linked* for insertion order, Tree* for sorted.
  • Defaults: ArrayList, HashSet, HashMap, ArrayDeque.
  • Declare by interface; convert between collections with copy constructors.
  • A List used for lookup by value or id is the classic wrong choice.

Next lesson

The next lesson, "Iteration and ConcurrentModificationException", covers the one situation where even the right collection bites back: removing elements while looping.

Self-check

  1. A requirement says "find a customer by id quickly." Which family?
  2. Which implementation gives unique values, sorted?
  3. Which implementation gives unique values in insertion order?
  4. Why declare List<String> instead of ArrayList<String>?
  5. What does new ArrayList<>(someSet) produce?
أظهر الإجابات
  1. Map (a HashMap).
  2. TreeSet.
  3. LinkedHashSet.
  4. So the implementation can change in one place without affecting code that only needs list behavior.
  5. An independent list containing the set's elements.

References

  • Oracle, Java SE 21 API, HashMap. Supports no order guarantee and constant-time get/put with good hashing.
  • Oracle, Java SE 21 API, TreeMap. Supports sorted keys and guaranteed log(n) cost.
  • Oracle, Java SE 21 API, LinkedHashSet. Supports insertion-order iteration and copying a set with order preserved.
  • Oracle, Java SE 21 API, ArrayList and ArrayDeque. Support constant-time get on ArrayList and the queue and stack behavior of ArrayDeque.
  • Outputs were produced by compiling and running the examples with JDK 21. The cost table is a qualitative summary of the documented guarantees above; the "scan" entries for list and deque lookups are general knowledge that I did not find stated in the fetched pages.

التطبيق

طبّق هذا الدرس بمختبر الوحدة وتمارينها واختبارها.

المختبر والتمارين الاختبار

تعليم الدرس كمكتمل اختياري ويمكنك التراجع عنه في أي وقت. يبقى تقدمك محفوظًا في هذا المتصفح.

تابع إلى الدرس التالي

اكتب للبحث في المستويات والمراحل والوحدات والدروس.