Đến nội dung chính
notes.vinhnq.com

Tìm kiếm

Cấu trúc dữ liệu & Thuật toánSenior21 phút đọc

Bên trong Java Collections: ArrayList, LinkedList, ArrayDeque và HashMap

Ôn 14 thẻ
Trong bài này

Cụm bài Cấu trúc dữ liệu: 1. Array, Linked List, Stack, Queue · 2. List, Set, Map · 3. TreeMap, Comparator, Iterator · 4. Bên trong ArrayList, HashMap

Dùng ArrayList và HashMap thì ai cũng biết; phỏng vấn senior hỏi tiếp chúng chạy thế nào bên trong JDK. Đọc xong, bạn giải thích được add tốn bao nhiêu khi mảng đầy, vì sao LinkedList và Stack hiếm khi đúng, HashMap xử lý trùng bucket ra sao, và tự viết lại được ArrayList, LinkedList. Nên đọc trước phần 1 (array, linked list, stack, queue ở mức khái niệm), phần 2 (API của List, Set, Map) và phần 3 (TreeMap, Comparator, Iterator).

1. Bên trong JDK (phần senior hay bị hỏi)

Ý chính: mỗi collection là một cấu trúc dữ liệu cụ thể (mảng, mảng vòng, danh sách liên kết, bảng băm). Biết cấu trúc đó là suy ra được chi phí của từng thao tác và các bẫy của nó.

1.1. ArrayList tăng kích thước thế nào

Ý chính: ArrayList là một mảng; đầy thì tạo mảng mới lớn hơn ~1.5 lần và copy sang. Vì tăng theo cấp số nhân, thêm vào cuối là O(1) amortized.

  • new ArrayList<>() chưa cấp phát 10 ô ngay. Nó trỏ tới một mảng rỗng dùng chung; lần add đầu tiên mới tạo mảng capacity 10. Slide nói “mặc định là 10” là đúng con số, nhưng việc cấp phát là lười.
  • Khi đầy: capacity mới = old + (old >> 1) (≈ 1.5 lần), rồi Arrays.copyOf sang mảng mới.
  • Amortized (khấu hao) nghĩa là chi phí trung bình trên cả chuỗi thao tác. Tổng chi phí copy cho n lần add vẫn là O(n), nên trung bình mỗi lần O(1). Riêng lần add gặp resize tốn O(n): với hệ thống nhạy latency, đó là một cú “spike”.
  • Biết trước kích thước thì khai báo luôn: new ArrayList<>(expectedSize) hoặc ensureCapacity(n), để tránh resize nhiều lần.
  • ArrayList không thread-safe. Cần đa luồng thì cân nhắc Collections.synchronizedList, CopyOnWriteArrayList (đọc rất nhiều, ghi rất ít), hoặc thiết kế để không chia sẻ list.
ArrayList: trimToSize, remove và cơ chế fail-fast modCount
  • trimToSize() thu mảng về đúng size để giảm bộ nhớ.
  • remove(index) dùng System.arraycopy để dịch các phần tử sau sang trái, rồi gán ô cuối bằng null để GC thu hồi được object. Quên bước gán null này là một kiểu memory leak kinh điển khi tự viết cấu trúc dữ liệu.
  • ArrayList có biến modCount đếm số lần bị sửa cấu trúc. Iterator kiểm tra nó để phát hiện list bị sửa trong lúc duyệt, rồi ném ConcurrentModificationException. Đây là cơ chế fail-fast (báo lỗi sớm để lộ bug), không phải cơ chế đồng bộ: đừng dựa vào nó cho tính đúng đắn đa luồng.
  • Với int số lượng lớn, ArrayList<Integer> tốn hơn int[] nhiều lần do boxing (bọc giá trị primitive thành object; mỗi Integer ~16 byte). Code xử lý số liệu lớn nên dùng mảng primitive hoặc IntStream.

1.2. LinkedList trong JDK

Ý chính: LinkedList là danh sách liên kết đôi; truy cập theo index vẫn O(n) và mỗi phần tử tốn thêm một object node. Ưu điểm thật sự chỉ là chèn/xoá O(1) qua ListIterator đang đứng sẵn ở vị trí đó.

  • Là doubly linked list (mỗi node trỏ cả node trước và node sau), implement cả List lẫn Deque.
  • get(i) đi từ đầu gần hơn: i < size/2 thì đi từ first, ngược lại từ last. Vẫn là O(n).
  • Mỗi phần tử là một object Node (item, next, prev): khoảng 24 byte mỗi node với compressed oops (JVM nén tham chiếu 64-bit xuống 4 byte), chưa tính object phần tử. ArrayList chỉ tốn 4 byte tham chiếu mỗi phần tử. Nhiều object nhỏ cũng làm GC vất vả hơn.
  • Node nằm rải rác trong heap nên CPU cache kém hiệu quả; mảng của ArrayList nằm liền nhau (cache locality tốt). Làm queue/stack thì ArrayDeque tốt hơn.

1.3. Đừng dùng Stack, hãy dùng ArrayDeque

Ý chính: Stack là class cũ, khoá không cần thiết và lộ thao tác theo index. ArrayDeque làm stack và queue đều O(1) amortized, không lock, không tạo node.

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);         // addFirst
stack.pop();           // removeFirst

Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1);        // addLast
queue.poll();          // pollFirst

Cho đa luồng có các queue riêng. Backpressure (áp lực ngược) nghĩa là khi consumer chậm, producer bị buộc chậm lại thay vì đổ dồn việc vào bộ nhớ.

1.4. HashMap hoạt động thế nào

Ý chính: HashMap là mảng bucket; hash của key chọn bucket, key trùng bucket được nối thành list (dài thì thành cây). Quá 75% đầy thì gấp đôi mảng.

flowchart LR
  K["key.hashCode()"] --> M["h ^ (h >>> 16)"]
  M --> I["index = hash & (n - 1)"]
  I --> T["table[index]"]
  T --> B1["Node(k1,v1)"] --> B2["Node(k2,v2)"]
  T -. "bucket >= 8 node và table >= 64" .-> RB["Red-black tree"]
  • Mảng table các bucket (ô chứa). Capacity mặc định 16, luôn là lũy thừa của 2, nên index tính bằng phép AND hash & (n - 1) thay vì %.
  • Collision (hai key trùng bucket) được nối thành linked list. Từ Java 8, bucket có từ 8 node trở lên và table ≥ 64 ô thì chuyển thành cây đỏ-đen (treeify): worst case từ O(n) xuống O(log n). Table còn nhỏ hơn 64 thì HashMap resize thay vì treeify.
  • Load factor mặc định 0.75: khi size > capacity * 0.75, table gấp đôi và entry được chia lại.
  • get/put trung bình O(1) nếu hashCode phân bố tốt. hashCode() trả hằng số thì mọi key dồn vào một bucket.
  • Không thread-safe: nhiều luồng cùng put có thể mất dữ liệu. Dùng ConcurrentHashMap.
  • Đừng dùng object mutable làm key: đổi field tham gia hashCode sau khi put thì không bao giờ get lại được nữa. Record và String là key tốt vì immutable.
  • LinkedHashMap giữ thứ tự chèn; dựng với accessOrder = true và override removeEldestEntry là thành LRU cache đơn giản. TreeMap là cây đỏ-đen, O(log n), có floorKey, ceilingKey, subMap.
Chi tiết HashMap: trộn hash, chia lại khi resize, key null, HashSet
  • Hash được “trộn” bằng h ^ (h >>> 16) để các bit cao cũng ảnh hưởng tới index (vì & (n - 1) chỉ lấy các bit thấp).
  • Khi resize gấp đôi, mỗi entry hoặc giữ nguyên index, hoặc dịch thêm đúng oldCapacity. Không cần tính lại hash đầy đủ.
  • Cây trong bucket giảm còn 6 node thì về lại linked list.
  • Cho phép một key null (nằm ở bucket 0) và nhiều value null.
  • Trước Java 8, nhiều luồng cùng resize còn có thể tạo vòng lặp vô hạn trong bucket.
  • HashSet thực chất là một HashMap với value là một object dummy.

1.5. Java 21: Sequenced Collections

Ý chính: từ Java 21, List, Deque, LinkedHashSet có chung getFirst(), getLast(), reversed()… nên không phải viết list.get(list.size() - 1) nữa.

1.6. Bảng Big-O tổng hợp

Ý chính: mảng mạnh ở truy cập index, ArrayDeque ở hai đầu, HashMap ở tìm theo key, TreeMap khi cần thứ tự. LinkedList chỉ rẻ khi đã đứng sẵn ở vị trí cần sửa.

Cấu trúc Truy cập index Tìm theo giá trị Thêm đầu Thêm cuối Thêm/xoá giữa Xoá đầu Xoá cuối
int[] O(1) O(n) không không không không không
ArrayList O(1) O(n) O(n) O(1)* O(n) O(n) O(1)
LinkedList O(n) O(n) O(1) O(1) O(n) tìm + O(1) nối O(1) O(1)
ArrayDeque không O(n) O(1)* O(1)* không O(1) O(1)
PriorityQueue không O(n) offer O(log n) poll O(log n)
HashMap/HashSet không O(1) trung bình, O(log n) worst (Java 8+) put O(1) TB remove O(1) TB
TreeMap/TreeSet không O(log n) put O(log n) remove O(log n)

* amortized.

Bài tập

Bài 1: Tự viết ArrayList và bổ sung method

Đề: từ class ArrayList tự viết trong bài, thêm clear, contains, get, indexOf, lastIndexOf, set, trimToSize, addFirst, addLast, removeFirst, removeLast, getFirst, getLast.

Lời giải Bài 1: hệ số tăng capacity và MyArrayList generic (đã chạy test)
import java.util.Arrays;
import java.util.NoSuchElementException;
import java.util.Objects;

public class MyArrayList<E> {
    private static final int DEFAULT_CAPACITY = 10;
    private Object[] data;
    private int size;

    public MyArrayList() { this(DEFAULT_CAPACITY); }

    public MyArrayList(int initialCapacity) {
        if (initialCapacity < 0) throw new IllegalArgumentException("capacity < 0");
        data = new Object[initialCapacity];
    }

    public int size() { return size; }
    public boolean isEmpty() { return size == 0; }

    private void growIfFull() {
        if (size == data.length) {
            // tăng ~1.5 lần giống JDK; max(...) để xử lý capacity 0 hoặc 1
            int newCap = Math.max(DEFAULT_CAPACITY, data.length + (data.length >> 1));
            data = Arrays.copyOf(data, newCap);
        }
    }

    private void checkIndex(int index) {
        if (index < 0 || index >= size)
            throw new IndexOutOfBoundsException("index=" + index + ", size=" + size);
    }

    public void add(E e) { add(size, e); }

    public void add(int index, E e) {
        if (index < 0 || index > size)        // index == size nghĩa là thêm vào cuối
            throw new IndexOutOfBoundsException("index=" + index + ", size=" + size);
        growIfFull();
        System.arraycopy(data, index, data, index + 1, size - index);
        data[index] = e;
        size++;
    }

    @SuppressWarnings("unchecked")
    public E get(int index) {
        checkIndex(index);
        return (E) data[index];
    }

    public E set(int index, E e) {
        E old = get(index);
        data[index] = e;
        return old;
    }

    public E remove(int index) {
        E old = get(index);
        System.arraycopy(data, index + 1, data, index, size - index - 1);
        data[--size] = null;                   // không giữ tham chiếu thừa -> tránh leak
        return old;
    }

    public int indexOf(Object o) {
        for (int i = 0; i < size; i++)
            if (Objects.equals(o, data[i])) return i;   // xử lý được cả null
        return -1;
    }

    public int lastIndexOf(Object o) {
        for (int i = size - 1; i >= 0; i--)
            if (Objects.equals(o, data[i])) return i;
        return -1;
    }

    public boolean contains(Object o) { return indexOf(o) >= 0; }

    public void clear() {
        data = new Object[DEFAULT_CAPACITY];   // đề yêu cầu trả về kích thước mặc định
        size = 0;
    }

    public void trimToSize() {
        if (data.length > size) data = Arrays.copyOf(data, size);
    }

    public void addFirst(E e) { add(0, e); }        // O(n)
    public void addLast(E e)  { add(size, e); }     // O(1) amortized
    public E removeFirst() { requireNotEmpty(); return remove(0); }
    public E removeLast()  { requireNotEmpty(); return remove(size - 1); }
    public E getFirst()    { requireNotEmpty(); return get(0); }
    public E getLast()     { requireNotEmpty(); return get(size - 1); }

    private void requireNotEmpty() {
        if (size == 0) throw new NoSuchElementException("list is empty");
    }

    @Override
    public String toString() {             // slide 1.3 "show()": [a, b, c]
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < size; i++) {
            if (i > 0) sb.append(", ");     // dấu phẩy chỉ đặt GIỮA hai phần tử
            sb.append(data[i]);
        }
        return sb.append(']').toString();
    }
}

Giải thích nhanh:

  • System.arraycopy xử lý đúng cả khi vùng nguồn và đích chồng nhau, nên dùng nó để dịch phải (khi chèn) và dịch trái (khi xoá), thay cho vòng for thủ công.
  • getFirst trên list rỗng ném NoSuchElementException, giống ArrayList.getFirst() trong Java 21.
  • Objects.equals giúp indexOf(null) hoạt động đúng.
  • toString() thay cho show() của slide (in dạng [a, b, c]): dấu phẩy đặt trước mọi phần tử trừ phần tử đầu, nên không thừa dấu phẩy cuối. List rỗng in ra []. Override toString tốt hơn method tự in ra System.out, vì chuỗi dùng được cho log, test và debugger.

Bài 2: Tự viết LinkedList và bổ sung method

Đề: từ class LinkedList (singly, có head, tail, size) trong bài, thêm clear, contains, indexOf, lastIndexOf, set, getFirst, getLast.

Lời giải Bài 2: các lỗi của code mẫu slide và MyLinkedList

Các lỗi nhỏ hơn nhưng vẫn nên biết: tên method removeFist bị gõ sai; get(n) với n ngoài phạm vi lặng lẽ trả null thay vì ném exception; add(i, e) với i > size lặng lẽ thêm vào cuối thay vì báo lỗi; remove(i) với i >= size làm hỏng danh sách. Lời giải dưới kiểm tra index và ném IndexOutOfBoundsException cho tất cả các trường hợp này.

import java.util.NoSuchElementException;
import java.util.Objects;

public class MyLinkedList<E> {
    private static final class Node<E> {
        E data;
        Node<E> next;
        Node(E data) { this.data = data; }
    }

    private Node<E> head;
    private Node<E> tail;
    private int size;

    public int size() { return size; }

    private Node<E> node(int index) {
        if (index < 0 || index >= size)
            throw new IndexOutOfBoundsException("index=" + index + ", size=" + size);
        Node<E> cur = head;
        for (int i = 0; i < index; i++) cur = cur.next;
        return cur;
    }

    public void addFirst(E e) {
        Node<E> n = new Node<>(e);
        n.next = head;
        head = n;
        if (tail == null) tail = n;     // list đang rỗng
        size++;
    }

    public void addLast(E e) {          // O(1) nhờ có tail
        Node<E> n = new Node<>(e);
        if (tail == null) {
            head = tail = n;
        } else {
            tail.next = n;
            tail = n;
        }
        size++;
    }

    public void add(int index, E e) {
        if (index < 0 || index > size)
            throw new IndexOutOfBoundsException("index=" + index + ", size=" + size);
        if (index == 0)    { addFirst(e); return; }
        if (index == size) { addLast(e);  return; }
        Node<E> prev = node(index - 1);
        Node<E> n = new Node<>(e);
        n.next = prev.next;             // nối node mới vào phần sau TRƯỚC
        prev.next = n;                  // rồi mới đổi con trỏ của prev
        size++;
    }

    public E removeFirst() {
        if (head == null) throw new NoSuchElementException();
        E val = head.data;
        head = head.next;
        if (head == null) tail = null;  // vừa xoá phần tử cuối cùng
        size--;
        return val;
    }

    public E removeLast() {             // vẫn O(n): singly list phải tìm node áp chót
        if (size <= 1) return removeFirst();
        Node<E> prev = node(size - 2);
        E val = tail.data;
        prev.next = null;
        tail = prev;
        size--;
        return val;
    }

    public E remove(int index) {
        if (index == 0) return removeFirst();
        Node<E> prev = node(index - 1);
        Node<E> target = prev.next;
        if (target == null) throw new IndexOutOfBoundsException("index=" + index);
        prev.next = target.next;
        if (target == tail) tail = prev;
        size--;
        return target.data;
    }

    public E get(int index) { return node(index).data; }

    public E set(int index, E e) {
        Node<E> n = node(index);
        E old = n.data;
        n.data = e;
        return old;
    }

    public int indexOf(Object o) {
        int i = 0;
        for (Node<E> cur = head; cur != null; cur = cur.next, i++)
            if (Objects.equals(o, cur.data)) return i;
        return -1;
    }

    public int lastIndexOf(Object o) {  // singly list không đi lùi được: duyệt một lượt, nhớ lần khớp cuối
        int i = 0, last = -1;
        for (Node<E> cur = head; cur != null; cur = cur.next, i++)
            if (Objects.equals(o, cur.data)) last = i;
        return last;
    }

    public boolean contains(Object o) { return indexOf(o) >= 0; }

    public void clear() {
        head = tail = null;             // các node không còn ai tham chiếu, GC sẽ dọn
        size = 0;
    }

    public E getFirst() {
        if (head == null) throw new NoSuchElementException();
        return head.data;
    }

    public E getLast() {
        if (tail == null) throw new NoSuchElementException();
        return tail.data;
    }

    @Override
    public String toString() {          // O(n), đi theo next thay vì gọi get(i)
        StringBuilder sb = new StringBuilder("[");
        for (Node<E> cur = head; cur != null; cur = cur.next) {
            sb.append(cur.data);
            if (cur.next != null) sb.append(" -> ");
        }
        return sb.append("]").toString();
    }
}

Đề có ghi clear() “đặt về kích thước mặc định”, nhưng linked list không có capacity, nên ở đây chỉ cần bỏ hết tham chiếu.

Ghi nhớ

  • Giải thích được vì sao add của ArrayList là O(1) amortized dù có lần tốn O(n), và vì sao tăng +10 mỗi lần lại thành O(n²).
  • Biết khi nào LinkedList thật sự tốt hơn ArrayList, và nêu được hai lý do nó thường thua (cache locality, ~24 byte mỗi node).
  • Nói được ba lý do bỏ Stack để dùng ArrayDeque, và vì sao ArrayDeque không nhận null.
  • Vẽ lại được đường đi hashCode → trộn hash → hash & (n - 1) → bucket → list/cây, với các ngưỡng 8, 64, 0.75.
  • Biết vì sao key mutable làm hỏng HashMap và vì sao queue production phải có giới hạn.

Câu hỏi phỏng vấn

Mid

ArrayList tăng kích thước như thế nào và vì sao add là O(1) amortized?

Đầy thì tạo mảng mới ~1.5 lần và copy sang; vì tăng theo cấp số nhân, tổng chi phí copy qua n lần add chỉ là O(n).

Constructor mặc định dùng mảng rỗng; lần add đầu cấp 10 ô. Tổng copy bị chặn bởi một hằng số nhân n, nên trung bình mỗi lần add là O(1), dù một lần riêng lẻ có thể là O(n).

Khi nào LinkedList thực sự tốt hơn ArrayList?

Hiếm khi: chủ yếu khi chèn/xoá nhiều ở giữa qua một ListIterator đang đứng sẵn ở vị trí đó.

Hoặc khi cần thêm/xoá ở đầu mà không muốn dùng ArrayDeque. Trong đa số benchmark, ArrayList thắng nhờ cache locality và ít object hơn; LinkedList tốn ~24 byte overhead mỗi node và làm GC vất vả hơn.

Vì sao nên dùng ArrayDeque thay cho Stack?

Stack kế thừa Vector nên khoá không cần thiết và phá vỡ LIFO; ArrayDeque là mảng vòng, push/pop O(1) amortized, không lock.

Mọi method của Stack đều synchronized, và nó lộ các method truy cập theo index. ArrayDeque không tạo node. Javadoc khuyến nghị dùng Deque.

Senior

Mô tả cách HashMap hoạt động trong Java 8+.

Mảng bucket kích thước lũy thừa 2; hash chọn bucket, collision nối thành list, list dài thành cây đỏ-đen, quá load factor thì gấp đôi table.

Mặc định 16 bucket. Hash được trộn bằng h ^ (h >>> 16), index = hash & (n-1). Bucket từ 8 node trở lên và table ≥ 64 thì treeify (worst case O(log n)), giảm còn 6 thì về lại list. Vượt capacity * 0.75 thì gấp đôi table và chia lại entry. Không thread-safe; cho phép một key null.

Dùng object mutable làm key của HashMap có vấn đề gì?

Đổi field tham gia hashCode sau khi put thì get tính ra bucket khác, nên không bao giờ tìm thấy entry nữa.

Entry vẫn nằm ở bucket cũ, thành “rác” không lấy lại được, gây memory leak. Dùng key immutable (String, record, Long).

Chọn queue nào cho producer/consumer trong production? Vì sao bounded?

ArrayBlockingQueue hoặc LinkedBlockingQueue có capacity, vì queue không giới hạn che giấu consumer chậm cho tới khi heap đầy.

Queue không giới hạn kết thúc bằng OutOfMemoryError. Queue có giới hạn tạo backpressure: producer bị chặn hoặc nhận false từ offer, từ đó có thể từ chối request, đổ ra chỗ khác hoặc scale consumer. ThreadPoolExecutor mặc định của Executors.newFixedThreadPool dùng LinkedBlockingQueue không giới hạn; đây là một cái bẫy hay gặp.

Thiết kế LRU cache bằng Java Collections như thế nào?

Dùng LinkedHashMap(capacity, 0.75f, true) và override removeEldestEntry trả về size() > capacity; get/put O(1).

accessOrder = true để mỗi lần get đẩy entry về cuối. Tự làm thì kết hợp HashMap (key → node) với doubly linked list. Đa luồng thì cần lock, hoặc dùng thư viện như Caffeine.

Từ vựng tiếng Anh

Term Phát âm Nghĩa Ví dụ câu trong phỏng vấn
amortized /ˈæmərtaɪzd/ chi phí trung bình (khấu hao) “Appending to an ArrayList is amortized O(1).”
capacity /kəˈpæsəti/ sức chứa “Capacity is the length of the backing array, size is how many elements it holds.”
resize / grow /riːˈsaɪz/ tăng kích thước “When the array is full, it grows by about fifty percent.”
collision /kəˈlɪʒən/ va chạm (trùng bucket) “Collisions are chained in a bucket and treeified when they get long.”
load factor /loʊd ˈfæktər/ hệ số tải “The default load factor of 0.75 trades memory for fewer collisions.”
bucket /ˈbʌkɪt/ ô chứa trong bảng băm “The key’s hash decides which bucket it lands in.”
thread-safe /θrɛd seɪf/ an toàn đa luồng “HashMap isn’t thread-safe; use ConcurrentHashMap instead.”
backpressure /ˈbækˌprɛʃər/ áp lực ngược “A bounded queue gives us backpressure when consumers fall behind.”
boxing /ˈbɑːksɪŋ/ đóng gói primitive thành object “A List of Integer has boxing overhead compared with an int array.”

Ghi chép dựa trên khoá Fundamentals of Backend (Ronin Engineer) và tài liệu Java Core của Hỏi Dân IT, cộng thêm kiến thức tự tìm hiểu, viết lại theo cách hiểu của mình.