nên xem video để hiểu dễ hơn

Hiểu Sâu HashMap: Cách HashMap Hoạt Động Bên Trong (Hash Implementation)¶

Bạn muốn tự tin phỏng vấn và làm bài về cấu trúc dữ liệu HashMap? Hãy đọc bài này – mình sẽ giúp bạn hiểu từ gốc đến ngọn, không chỉ biết dùng mà còn nắm rõ cách HashMap làm việc bên trong!

1. HashMap là gì & tại sao lại "thần thánh" đến vậy?¶

HashMap là một cấu trúc dữ liệu dùng để lưu trữ các cặp key-value (khóa-giá trị).
Bạn có thể tra cứu, thêm, xóa một phần tử theo key một cách cực kỳ nhanh – trung bình chỉ mất O(1).
Được sử dụng ở khắp mọi nơi: từ đếm tần suất, tra cứu dữ liệu, cache, đến các bài toán xử lý chuỗi, mảng...

2. HashMap hoạt động như thế nào? (Từ tư duy đến thực tế)¶

2.1. Ý tưởng cốt lõi¶

Bạn hình dung HashMap bên trong là một cái mảng (array). Nhưng thay vì truy xuất theo số thứ tự (array[0], array[1]...), bạn sẽ truy xuất theo key (ví dụ: "username", "email"...).
Để chuyển từ key (có thể là chuỗi, số, tuple...) thành chỉ số trong mảng, cần một bước "băm" (hashing).

2.2. Hash Function (Hàm băm)¶

Hash function là hàm nhận key và trả ra một số nguyên.
Số nguyên này sẽ được dùng để xác định index trong mảng:
index = hash(key) % capacity
(capacity là kích thước mảng hiện tại)

Ví dụ đơn giản:¶

Key: "lelongc"
Hash: (giả sử) 123456
Nếu capacity = 8 thì index = 123456 % 8 = 0

2.3. Chèn (insert), Tìm kiếm (get), Xóa (delete)¶

Chèn: Tính chỉ số bằng hash function → thêm cặp key-value vào đúng ô mảng đó.
Tìm kiếm: Hash key lấy chỉ số → kiểm tra ô mảng đó có key bạn cần hay không.
Xóa: Tương tự tìm kiếm, sau đó xóa cặp key-value nếu có.

3. Va chạm (Collision): Tại sao và xử lý ra sao?¶

3.1. Collision là gì?¶

Collision xảy ra khi 2 key khác nhau cho ra cùng index sau khi hash (vd: "abc" và "xyz" cùng ra index 0).
Va chạm là điều không thể tránh khỏi vì số lượng key có thể rất lớn, nhưng mảng thì có giới hạn.

3.2. Các cách xử lý va chạm¶

Chaining (dùng linked list):
Mỗi ô trong mảng chứa một danh sách (list) các cặp key-value.
Khi collision, chỉ cần thêm key-value mới vào danh sách này.
Khi tìm kiếm, duyệt trong danh sách để tìm đúng key.
Open Addressing (địa chỉ mở):
Nếu index bị chiếm, tìm ô trống tiếp theo trong mảng (linear probing/quadratic probing/double hashing).
Đa số các ngôn ngữ hiện đại dùng chaining vì dễ cài đặt & ổn định.

4. Khi nào cần mở rộng mảng (rehashing)?¶

4.1. Load factor (tải trọng)¶

Load factor = số phần tử đã lưu / dung lượng mảng.
Khi load factor quá cao (vd: 0.75), nguy cơ collision tăng mạnh → cần mở rộng mảng.

4.2. Rehashing (tăng kích thước mảng)¶

Tạo mảng mới lớn hơn (thường gấp đôi & là số nguyên tố nếu tối ưu).
Băm lại tất cả các key cũ theo capacity mới và chuyển sang mảng mới.
Đây là thao tác tốn thời gian (O(n)), nhưng không diễn ra thường xuyên.

5. Demo code HashMap đơn giản (Python)¶

class Pair:
    def __init__(self, key, value):
        self.key = key
        self.value = value

class SimpleHashMap:
    def __init__(self, capacity=8):
        self.capacity = capacity
        self.size = 0
        self.buckets = [[] for _ in range(capacity)]

    def _hash(self, key):
        # Hash đơn giản (không tối ưu)
        return hash(key) % self.capacity

    def put(self, key, value):
        index = self._hash(key)
        bucket = self.buckets[index]
        for pair in bucket:
            if pair.key == key:
                pair.value = value  # cập nhật nếu đã tồn tại
                return
        bucket.append(Pair(key, value))
        self.size += 1

    def get(self, key):
        index = self._hash(key)
        bucket = self.buckets[index]
        for pair in bucket:
            if pair.key == key:
                return pair.value
        raise KeyError(f"Key {key} không tồn tại")

    def remove(self, key):
        index = self._hash(key)
        bucket = self.buckets[index]
        for i, pair in enumerate(bucket):
            if pair.key == key:
                del bucket[i]
                self.size -= 1
                return
        raise KeyError(f"Key {key} không tồn tại")

Sử dụng:¶

hm = SimpleHashMap()
hm.put("username", "lelongc")
hm.put("email", "abc@gmail.com")
print(hm.get("username"))  # lelongc
hm.remove("email")

6. Rehashing (tăng kích thước HashMap)¶

def _rehash(self):
    old_buckets = self.buckets
    self.capacity *= 2
    self.buckets = [[] for _ in range(self.capacity)]
    self.size = 0
    for bucket in old_buckets:
        for pair in bucket:
            self.put(pair.key, pair.value)

Sau khi số phần tử vượt quá ngưỡng (load factor), ta gọi _rehash.

7. Tổng kết: Khi nào HashMap nhanh, khi nào chậm?¶

Nhanh (O(1)): Khi hash function phân phối tốt, load factor thấp, ít collision.
Chậm (O(n)): Khi nhiều collision (hash function tệ hoặc load factor cao), tất cả key cùng vào một bucket → phải duyệt hết list trong bucket.
Rehashing tốn O(n), nhưng không xảy ra thường xuyên nên không ảnh hưởng hiệu suất trung bình.

8. Mẹo ghi nhớ và trả lời phỏng vấn¶

Tôi sẽ triển khai HashMap bằng một mảng, dùng hash function để ánh xạ key thành index. Nếu collision, tôi dùng chaining để lưu nhiều cặp key-value trong cùng một bucket. Khi load factor cao, tôi sẽ rehash để tăng capacity.
Độ phức tạp trung bình O(1), tệ nhất O(n), nhưng rehashing và collision được xử lý tốt thì luôn rất nhanh.

9. So sánh nhanh các khái niệm:¶

Thuật ngữ	Nghĩa là gì?	Ví dụ
Hashing	Băm key thành số nguyên	hash("user") = 123456
Collision	2 key cho cùng index	"abc", "xyz" cùng vào bucket 0
Chaining	Nhiều key-value trong một bucket	bucket 2: [("apple", 5), ("cat", 8)]
Open Addressing	Tìm ô trống tiếp theo trong array	Nếu bucket 3 trùng, thử bucket 4, 5...
Load factor	% lấp đầy của mảng	6 phần tử, capacity 8, LF = 0.75
Rehashing	Tăng size mảng & băm lại toàn bộ	từ 8 lên 16, chuyển lại hết dữ liệu

10. Kết luận¶

HashMap cực kỳ hiệu quả nhờ hashing, xử lý collision và rehashing hợp lý.
Hiểu bản chất bên trong giúp bạn giải thích, debug, tối ưu và tự tin phỏng vấn.
Muốn master? Hãy thử tự code lại 1 hashmap đơn giản!

Chúc bạn tự tin phỏng vấn, code và sử dụng HashMap như một pro!