leetcode: two sum

Đi phỏng vấn hay luyện thuật toán trên LeetCode, bài Two Sum (tìm 2 số có tổng bằng target) gần như là "Hello World" của cấu trúc dữ liệu.

Dev nào cũng thuộc lòng:

• Brute-force: O(N²) thời gian, O(1) bộ nhớ → Kém.
• Dùng HashMap: O(N) thời gian, O(N) bộ nhớ → Lời giải tối ưu nhất.

Về độ phức tạp thì đúng là vậy. Nhưng nếu bạn làm hệ thống low-latency hay thường xuyên phải tối ưu hiệu năng, lời giải HashMap<Integer, Integer> chạy trên phần cứng thật không đẹp như trên giấy.

Một thuật toán O(N) có thể chậm ngang, thậm chí chậm hơn cách O(N log N) hay một vòng lặp quét tuần tự, vì Big-O không đếm cái giá của việc CPU ngồi chờ bộ nhớ. Muốn thấy rõ thì phải nhìn xuống tầng CPU và Cache Line.

# lý thuyết thuật toán nói một đằng, phần cứng làm một nẻo

Big-O giả định một máy tính lý thuyết (RAM Model), trong đó mọi lần truy cập bộ nhớ đều tốn như nhau (O(1)). Thực tế thì CPU chạy ở 3–5 GHz, còn mỗi lần đọc RAM chính (DRAM) mất 50 tới 100 nano-giây, tức là hàng trăm chu kỳ CPU ngồi chờ không.

# cái giá ẩn của HashMap trong Java

Giải Two Sum bằng HashMap<Integer, Integer> thì mỗi phần tử thêm vào, HotSpot phải làm:

1. Autoboxing: đổi primitive int (4 bytes) thành object java.lang.Integer. Trên JVM 64-bit với compressed oops (mặc định khi heap dưới 32 GB), mỗi Integer chiếm 16 bytes: 12 bytes header + 4 bytes giá trị. Lưu một cặp key/value (8 bytes dữ liệu thật) thành ra tốn 32 bytes chỉ cho 2 object Integer. Integer.valueOf chỉ cache sẵn các giá trị từ -128 tới 127, ngoài khoảng đó là mỗi lần một object mới.
2. Overhead của Node: mỗi entry trong HashMap là một instance Node<K, V>, gồm:
   • 12B Object Header
   • 4B hash
   • 4B reference tới Key
   • 4B reference tới Value
   • 4B reference tới Next Node → 28 bytes, làm tròn theo 8 thành 32 bytes mỗi node (tắt compressed oops thì reference thành 8B và node lên 48 bytes).
3. Pointer Chasing (nhảy theo con trỏ): bảng băm chỉ giữ reference tới Node, Node lại trỏ tiếp tới Integer. Một lần map.get() là ít nhất 3 lần đọc ở 3 địa chỉ khác nhau, và vì hash rải đều nên vị trí trong bảng gần như ngẫu nhiên. Lúc vừa cấp phát, các object nằm khá sát nhau trong TLAB, nhưng thứ tự truy cập thì vẫn lung tung, Hardware Prefetcher không đoán được, và thế là cache miss liên tục khi dữ liệu lớn hơn cache. Sau vài lần GC dời object đi thì càng tệ.

# các mức tối ưu cho two sum

# mức 1 & 2: từ brute-force tới HashMap của java

// CẤP ĐỘ 2: LỜI GIẢI PHỔ BIẾN NHƯNG KÉM HIỆU QUẢ TRÊN LOW-LATENCY
import java.util.HashMap;
import java.util.Map;
 
public class StandardTwoSum {
    public static int[] twoSum(int[] nums, int target) {
        // Sinh ra hàng nghìn đối tượng ngắn hạn trên Young Gen!
        Map<Integer, Integer> lookup = new HashMap<>(nums.length);
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            Integer prevIndex = lookup.get(complement); // Autoboxing complement & lookup
            if (prevIndex != null) {
                return new int[] { prevIndex, i };
            }
            lookup.put(nums[i], i); // Autoboxing nums[i] và i -> Tạo Node<K, V>
        }
        throw new IllegalArgumentException("No solution found");
    }
}

# mức 3: two pointers trên mảng đã sắp xếp, cache rất thích

Nếu mảng đầu vào đã sort sẵn (chính là bài Two Sum II trên LeetCode), Two-Pointer nhanh hơn hẳn: chỉ quét tuần tự từ hai đầu, không cấp phát gì. Còn nếu phải tự sort trước thì chi phí Arrays.sort chiếm gần hết thời gian, và theo số đo ở cuối bài, tổng thời gian ngang ngửa HashMap. Thêm nữa, sort xong là mất vị trí gốc, nên muốn trả về index như đề Two Sum gốc thì phải sort kèm index (mảng cặp giá trị/index), tốn thêm bộ nhớ:

// CẤP ĐỘ 3: TWO POINTERS TRÊN MẢNG PHẲNG (ZERO HEAP ALLOCATION)
public class TwoPointerTwoSum {
    public static boolean hasTwoSum(int[] sortedNums, int target) {
        int left = 0;
        int right = sortedNums.length - 1;
 
        // Dữ liệu mảng nằm liên tục trên RAM -> CPU Prefetcher nạp trước 64-byte Cache Lines
        // Quét tuần tự từ hai đầu nên gần như không bị cache miss
        while (left < right) {
            int sum = sortedNums[left] + sortedNums[right];
            if (sum == target) {
                return true;
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        return false;
    }
}

# mức 4: primitive open addressing hash map, không cấp phát object nào

Muốn giữ O(N) trên lý thuyết mà không phải trả giá bằng pointer chasing hay GC churn, các hệ thống giao dịch tần suất cao (HFT) và database in-memory dùng Primitive Open Addressing Hash Map (như Int2IntHashMap của Agrona hay Int2IntOpenHashMap của fastutil; Koloboke cũng là một lựa chọn nhưng đã lâu không được bảo trì).

Toàn bộ dữ liệu nằm thẳng trong 2 mảng primitive phẳng int[] keys và int[] values. Khi trùng hash, thuật toán dùng Linear Probing để dò sang ô kế bên. Các ô kế nhau thường nằm chung một Cache Line 64 bytes (16 số int), nên dò thêm vài bước gần như không tốn thêm lần đọc RAM nào. Đổi lại, open addressing phải giữ hệ số tải thấp (ở đây là 0.5), tức là chấp nhận tốn gấp đôi số ô để chuỗi dò luôn ngắn.

package com.tungdadev.lowlatency;
 
import java.util.Arrays;
 
public final class PrimitiveIntIntMap {
    private final int[] keys;
    private final int[] values;
    private final int mask;
    private final int emptyKey;
 
    public PrimitiveIntIntMap(int expectedCapacity, int emptyKey) {
        int capacity = 1;
        while (capacity < expectedCapacity * 2) { // Hệ số tải 0.5 để tối ưu hóa Linear Probing
            capacity <<= 1;
        }
        this.mask = capacity - 1;
        this.emptyKey = emptyKey;
        this.keys = new int[capacity];
        this.values = new int[capacity];
        Arrays.fill(this.keys, emptyKey);
    }
 
    public void put(int key, int value) {
        int index = hash(key) & mask;
        while (keys[index] != emptyKey && keys[index] != key) {
            index = (index + 1) & mask; // Linear Probing: ô kế bên thường vẫn nằm trong cùng Cache Line
        }
        keys[index] = key;
        values[index] = value;
    }
 
    public int get(int key, int defaultValue) {
        int index = hash(key) & mask;
        while (keys[index] != emptyKey) {
            if (keys[index] == key) {
                return values[index];
            }
            index = (index + 1) & mask;
        }
        return defaultValue;
    }
 
    private static int hash(int x) {
        // MurmurHash3 integer finalizer
        x ^= x >>> 16;
        x *= 0x85ebca6b;
        x ^= x >>> 13;
        x *= 0xc2b2ae35;
        x ^= x >>> 16;
        return x;
    }
}

Có hai điểm cần để ý với bản tự viết này. Thứ nhất, emptyKey là giá trị "lính canh" đánh dấu ô trống, nên dữ liệu không được chứa đúng giá trị đó (với đề LeetCode, nums[i] nằm trong khoảng ±10⁹ nên chọn Integer.MIN_VALUE là an toàn; Agrona cũng bắt bạn chọn một missingValue tương tự). Thứ hai, nó không xoá được phần tử và không tự giãn, vì bài toán này không cần.

Dùng PrimitiveIntIntMap để giải Two Sum:

public class ZeroAllocationTwoSum {
    public static int[] twoSum(int[] nums, int target) {
        // Không sinh ra object Integer/Node nào, chỉ 2 mảng int[] trong constructor
        PrimitiveIntIntMap map = new PrimitiveIntIntMap(nums.length, Integer.MIN_VALUE);
 
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            int prevIdx = map.get(complement, -1);
            if (prevIdx != -1) {
                return new int[] { prevIdx, i };
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No solution");
    }
}

# đi xa hơn: chạy song song bằng simd vector api

Vector API (thuộc Project Panama) cho phép viết code Java dùng tập lệnh vector của CPU (SSE/AVX trên x86, NEON trên ARM). API này ủ ở dạng incubator từ JDK 16; JEP 448 là vòng incubator thứ sáu trong Java 21, và tới JDK 26 (JEP 529) nó vẫn là incubator, nên phải thêm --add-modules jdk.incubator.vector khi biên dịch và khi chạy. Một lệnh vector so sánh được nhiều số cùng lúc: 16 số int với thanh ghi 512-bit của AVX-512, 8 số với AVX2 256-bit, 4 số với NEON 128-bit (Apple Silicon, phần lớn chip ARM).

Cần nói rõ SIMD giúp ở đâu: nó tăng tốc thao tác quét tuyến tính tìm một giá trị trong mảng, tức là vòng lặp trong của brute-force. Dùng nó cho cả bài Two Sum thì vẫn là brute-force O(N²), chỉ chia hằng số cho số lane, nên với N lớn vẫn thua xa cách dùng bảng băm (xem số đo bên dưới).

import jdk.incubator.vector.IntVector;
import jdk.incubator.vector.VectorMask;
import jdk.incubator.vector.VectorSpecies;
 
public class SimdVectorSearch {
    private static final VectorSpecies<Integer> SPECIES = IntVector.SPECIES_PREFERRED;
 
    // Quét từ vị trí `from`, mỗi lần so SPECIES.length() phần tử (4 lane với NEON, 16 với AVX-512)
    public static int findComplementSimd(int[] arr, int from, int complement) {
        IntVector targetVec = IntVector.broadcast(SPECIES, complement);
        int upperBound = from + SPECIES.loopBound(arr.length - from);
 
        int i = from;
        for (; i < upperBound; i += SPECIES.length()) {
            IntVector chunk = IntVector.fromArray(SPECIES, arr, i);
            VectorMask<Integer> matchMask = chunk.eq(targetVec);
            if (matchMask.anyTrue()) {
                return i + matchMask.firstTrue();
            }
        }
        // Xử lý các phần tử đuôi (tail loop)
        for (; i < arr.length; i++) {
            if (arr[i] == complement) return i;
        }
        return -1;
    }
 
    // Two Sum bằng brute-force + SIMD: vẫn O(N²), chỉ nhanh hơn vòng lặp thường vài lần
    public static int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length - 1; i++) {
            int j = findComplementSimd(nums, i + 1, target - nums[i]);
            if (j != -1) {
                return new int[] { i, j };
            }
        }
        throw new IllegalArgumentException("No solution");
    }
}

Biên dịch và chạy: javac --add-modules jdk.incubator.vector SimdVectorSearch.java, java --add-modules jdk.incubator.vector .... JVM sẽ in cảnh báo "Using incubator modules", đó là bình thường.

# kết quả benchmark (jmh)

Đo bằng Java Microbenchmark Harness (JMH 1.37) trên N = 100,000 số nguyên ngẫu nhiên, cặp nghiệm đặt ở cuối mảng để cách nào cũng phải đi hết (trường hợp xấu nhất). Máy Apple M1 Pro, JDK 21.0.2, cấp phát đo bằng -prof gc. Con số tuyệt đối sẽ khác trên máy bạn, nên nhìn tỷ lệ giữa các dòng thôi:

Vài điều đọc ra từ bảng:

• HashMap cấp phát ~9.6 MB cho 100 nghìn phần tử: mỗi phần tử một Node 32 bytes và hai Integer 16 bytes, thêm Integer tạo ra lúc get(complement), thêm mảng bảng băm. Có một chi tiết hay bị bỏ qua: new HashMap<>(n) không chứa được n phần tử mà không resize, vì ngưỡng resize là capacity × 0.75. Muốn đặt trước cho đúng thì dùng HashMap.newHashMap(n) (có từ Java 19).
• Bảng băm primitive nhanh hơn HashMap khoảng 4 lần trong phép đo này, không phải vì độ phức tạp khác mà vì bớt được object, bớt pointer chasing.
• Two-Pointer chỉ thắng áp đảo khi mảng đã sort sẵn. Phải tự sort thì O(N log N) của sort ăn hết lợi thế.
• SIMD làm vòng quét nhanh thật (6.5 µs cho 100 nghìn số), nhưng gắn vào brute-force thì O(N²) vẫn là O(N²).

# khi dữ liệu là luồng: streaming two sum

Khi dữ liệu không còn là một mảng tĩnh nằm gọn trong RAM một máy, mà là luồng thời gian thực (real-time stream) chảy liên tục, không bao giờ "đủ" để sort hay dựng xong một bảng băm (ví dụ phát hiện các giao dịch chuyển tiền bù trừ nhau trong ngân hàng), bài toán thành: với mỗi giao dịch mới, đã có giao dịch nào trước đó khớp với nó chưa. State phải giữ ở đâu đó và phải có giới hạn:

1. Stateful Windowing: giới hạn phạm vi tìm theo cửa sổ thời gian (Sliding Window, ví dụ 5 phút gần nhất). Giao dịch ra khỏi cửa sổ thì được dọn khỏi state. Tumbling window thì đơn giản hơn nhưng sẽ bỏ sót cặp nằm vắt qua ranh giới hai cửa sổ; cách thường gặp hơn là keyed state với TTL hoặc interval join của Flink.
2. Bloom Filter: RocksDB (state backend của Flink) có thể gắn Bloom Filter vào từng file SST, nằm ngoài Java heap. Khi tra một key chắc chắn không có, filter trả lời "không" ngay mà khỏi đọc xuống đĩa. Bloom Filter có thể báo nhầm "có" (false positive) với tỷ lệ tuỳ số bit cấp cho mỗi key, nhưng không bao giờ báo nhầm "không".

# lời kết

Two Sum là bài dễ, nhưng đủ để thấy chữ O(N) trên giấy chưa nói hết chuyện. Nếu code của bạn thật sự nằm trên đường nóng (hot path):

1. Đo trước bằng JMH với -prof gc, xem cái giá thật của Autoboxing là bao nhiêu byte mỗi lần chạy.
2. Thay Map<Integer, ...> bằng map primitive (Agrona, fastutil) hoặc mảng phẳng, để dữ liệu hợp với Cache Line 64-byte của CPU.
3. Dùng Vector API (SIMD) cho các vòng quét tuyến tính, nhưng nhớ nó chỉ chia hằng số, không đổi được độ phức tạp.

Còn đi phỏng vấn thì cứ viết bản HashMap trước, rồi kể thêm mấy chuyện trên nếu người phỏng vấn hỏi "nhanh hơn được nữa không".

Tài liệu tham khảo:

• Martin Thompson: CPU Cache Flushing Fallacy
• Agrona High-Performance Java Data Structures
• JEP 448: Vector API (Sixth Incubator)
• JEP 529: Vector API (Eleventh Incubator), JDK 26
• Ulrich Drepper: What Every Programmer Should Know About Memory

Chỉ là những ghi chép cá nhân với hy vọng mang lại chút giá trị. Nếu thấy hữu ích, đừng ngại chia sẻ cho bạn bè & đồng nghiệp nhé!

Happy coding 😎 👍🏻 🚀 🔥.