leetcode: two sum

Trong hầu hết các buổi phỏng vấn nhập môn hoặc trên các nền tảng luyện thuật toán như LeetCode, bài toán Two Sum (tìm 2 số có tổng bằng Target) luôn là "Hello World" của cấu trúc dữ liệu.

Bất kỳ lập trình viên nào cũng có thể đọc vanh vách:

• 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.

Tuy nhiên, dưới góc nhìn của một Low-Latency Systems Architect hoặc Performance Engineer, lời giải HashMap<Integer, Integer> thường là một "thảm họa hiệu năng" trên phần cứng máy tính hiện đại!

Tại sao một thuật toán có độ phức tạp lý thuyết O(N) lại có thể chạy chậm hơn gấp nhiều lần so với giải pháp O(N log N) hoặc thậm chí một vòng lặp tuần tự trên tập dữ liệu thực tế? Bài viết này sẽ đưa bạn đi từ mô hình toán học trừu tượng đến kiến trúc vật lý của CPU và bộ nhớ đệm Cache Line.

# nghịch lý giữa lý thuyết thuật toán & kiến trúc phần cứng

Độ phức tạp thuật toán Big-O giả định một mô hình máy tính lý thuyết (RAM Model), nơi mọi truy xuất bộ nhớ đều có chi phí bằng nhau (O(1)). Nhưng trong thực tế, CPU hiện đại chạy ở tốc độ 3–5 GHz, trong khi việc truy xuất bộ nhớ RAM chính (DRAM) mất từ 50 đến 100 nano-giây (tương đương hàng trăm chu kỳ CPU bị lãng phí).

# chi phí ẩn của HashMap trong Java

Khi giải Two Sum bằng HashMap<Integer, Integer>, với mỗi phần tử được thêm vào, máy ảo HotSpot phải thực hiện:

1. Autoboxing Overhead: Ép kiểu primitive int (4 bytes) thành đối tượng java.lang.Integer (16 đến 24 bytes trên Heap bao gồm Object Header). Để lưu 2 số int, ta tiêu tốn tới 48 bytes!
2. Node Overhead: Mỗi entry trong HashMap là một instance của Node<K, V>, chứa:
   • 12-16B Object Header
   • 4B hash
   • 8B reference tới Key
   • 8B reference tới Value
   • 8B reference tới Next Node → Mỗi node tốn thêm 32 bytes.
3. Thảm Họa Pointer Chasing (Truy Đuổi Con Trỏ): Các Node và Integer được cấp phát rải rác trên khắp bộ nhớ Heap. Mỗi lần gọi map.get() hoặc map.put(), CPU buộc phải nhảy đến các địa chỉ bộ nhớ ngẫu nhiên, phá vỡ cơ chế nạp trước phần cứng (Hardware Prefetcher) và gây ra hàng loạt L1/L2/L3 Cache Misses.

# các cấp độ tối ưu thuật toán two sum

# cấp độ 1 & 2: từ brute-force đến standard java hashmap

// 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");
    }
}

# cấp độ 3: two pointers trên mảng đã sắp xếp — thân thiện với bộ nhớ cache

Nếu yêu cầu bài toán chỉ cần trả về giá trị của 2 số (hoặc mảng đầu vào đã được sắp xếp sẵn), kỹ thuật Two-Pointer là sự lựa chọn vượt trội tuyệt đối về tốc độ thực thi vật lý:

// 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
        // Tỷ lệ Cache Hit tiệm cận 100%!
        while (left < right) {
            int sum = sortedNums[left] + sortedNums[right];
            if (sum == target) {
                return true;
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        return false;
    }
}

# cấp độ 4: primitive open addressing hash map — chuẩn mực zero-allocation

Để đạt được độ phức tạp lý thuyết O(N) mà hoàn toàn 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à cơ sở dữ liệu in-memory sử dụng Primitive Open Addressing Hash Map (như Agrona Int2IntHashMap hoặc Koloboke):

Toàn bộ dữ liệu được lưu trữ trực tiếp trên 2 mảng nguyên thủy phẳng int[] keys và int[] values. Khi có xung đột hash, giải thuật sử dụng Linear Probing để quét ngay ô nhớ kế tiếp. Do các ô nhớ nằm liền kề nhau trên cùng một Cache Line 64 bytes, chi phí giải quyết xung đột gần như bằng 0!

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 trên 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;
    }
}

Sử dụng PrimitiveIntIntMap giải bài toán Two Sum:

public class ZeroAllocationTwoSum {
    public static int[] twoSum(int[] nums, int target) {
        // Không một đối tượng Integer nào bị sinh ra trên Heap!
        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");
    }
}

# kỹ thuật tương lai: tăng tốc song song bằng simd vector api

Từ Java 21+, với Vector API (Project Panama - JEP 448), ta có thể tận dụng các tập lệnh vector phần cứng của CPU (AVX-512 hoặc ARM Neon) để kiểm tra 16 số nguyên cùng một lúc trong một chu kỳ xung nhịp duy nhất:

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 song song 16 phần tử mỗi chu kỳ CPU để tìm complement
    public static int findComplementSimd(int[] arr, int complement) {
        IntVector targetVec = IntVector.broadcast(SPECIES, complement);
        int upperBound = SPECIES.loopBound(arr.length);
 
        int i = 0;
        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;
    }
}

# bảng so sánh benchmark thực nghiệm (jmh)

Kết quả đo đạc thực tế bằng Java Microbenchmark Harness (JMH) trên tập dữ liệu N = 100,000 số nguyên (Apple M3 Max / Linux x86_64):

# mở rộng hệ thống phân tán: streaming two sum

Khi khối lượng dữ liệu không còn là mảng tĩnh nằm vừa trong RAM một máy chủ mà là một luồng dữ liệu thời gian thực (Real-time Stream) với hàng tỷ sự kiện đổ về mỗi giây (chẳng hạn như phát hiện giao dịch chuyển tiền bù trừ trong ngân hàng):

1. Stateful Windowing: Giới hạn phạm vi tìm kiếm theo cửa sổ thời gian (Sliding Window, ví dụ: 5 phút gần nhất). Các giao dịch ngoài phạm vi sẽ được tự động giải phóng khỏi bộ nhớ trạng thái.
2. Off-Heap Bloom Filters: Sử dụng Bloom Filter nằm ngoài Heap (Off-Heap) để lọc 99% các giao dịch không có khả năng bù trừ trước khi truy vấn vào ổ đĩa RocksDB.

# lời kết của kỹ sư hiệu năng cao

Một bài toán kinh điển như Two Sum không dừng lại ở mức O(N) trên giấy trắng mực đen.

Khi nâng tầm tư duy lên cấp độ Principal Engineer:

1. Bạn nhìn thấy chi phí vật lý của từng byte bộ nhớ bị lãng phí bởi Autoboxing.
2. Bạn thiết kế cấu trúc dữ liệu tôn trọng cấu trúc Cache Line 64-byte của CPU.
3. Bạn vận dụng Open Addressing và Vector API (SIMD) để đẩy hiệu năng lên tới giới hạn vật lý của phần cứng.

Tài liệu tham khảo chuyên sâu:

• Martin Thompson: CPU Cache Flushes and Cache Line Locality
• Agrona High-Performance Java Data Structures
• JEP 448: Vector API (Incubator)
• 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 😎 👍🏻 🚀 🔥.