Login

Bảng băm (hash table) và dictionary: bí quyết tra cứu cực nhanh

  • author-image

    Nguyễn Đình Cường

  • blog-tag
  • blog-comment 0 comment
  • created-date 09 Nov, 2026
blog-thumbnail

Bạn có bao giờ thắc mắc vì sao tra một số điện thoại theo tên trong danh bạ điện thoại lại gần như tức thì, dù có hàng nghìn liên hệ? Trong lập trình, bí quyết đó nằm ở bảng băm, cấu trúc đứng sau dictionary của Python và object, Map của JavaScript.

Ý tưởng cốt lõi: cặp khóa - giá trị

Thay vì truy cập bằng chỉ số 0, 1, 2, bảng băm cho phép bạn truy cập bằng khóa (key) bất kỳ như chuỗi hay số, và lấy ra giá trị (value) tương ứng.

diem = {"An": 8, "Bình": 6.5, "Chi": 9}
print(diem["Chi"])          # 9
diem["Dũng"] = 7            # thêm mới
diem["An"] = 8.5            # cập nhật
print("Bình" in diem)       # True
print(diem.get("Hà", 0))    # 0 nếu không có khóa
del diem["Bình"]

Các thao tác thêm, tìm, xóa theo khóa thường chạy rất nhanh, gần như không phụ thuộc số lượng phần tử.

Bên trong nó hoạt động thế nào?

Bảng băm dùng một mảng bên dưới và một hàm băm (hash function). Hàm băm nhận khóa và biến thành một con số, rồi dùng phép chia lấy dư để chọn vị trí trong mảng:

  1. Cho khóa "An", hàm băm trả về số, ví dụ 123456.
  2. Lấy 123456 chia dư cho kích thước mảng (ví dụ 8) để được ô số 0.
  3. Cất giá trị vào ô đó. Khi tra cứu, tính lại đúng ô và lấy ra ngay.

Giống như nhân viên thư viện nhìn mã sách là biết đi thẳng đến kệ nào, không cần lục từng cuốn.

Va chạm (collision)

Hai khóa khác nhau có thể cho cùng một vị trí; đó gọi là va chạm. Có hai cách xử lý phổ biến:

  • Chaining: mỗi ô giữ một danh sách các cặp khóa-giá trị cùng ô.
  • Open addressing: nếu ô bị chiếm, tìm ô trống kế tiếp theo một quy tắc.

Khi bảng quá đầy, nó tự cấp phát bảng lớn hơn và băm lại mọi phần tử, nhờ đó vẫn giữ tốc độ ổn định. Người dùng như chúng ta hầu như không phải bận tâm, nhưng biết điều này giúp hiểu vì sao đôi lúc một lần thêm phần tử bỗng chậm hơn thường lệ.

Ứng dụng thực tế

def dem_tan_suat(cau):
    dem = {}
    for tu in cau.lower().split():
        dem[tu] = dem.get(tu, 0) + 1
    return dem

print(dem_tan_suat("mèo và chó và gà"))
# {'mèo': 1, 'và': 2, 'chó': 1, 'gà': 1}

def hai_so_co_tong(ds, muc_tieu):
    da_thay = {}
    for i, x in enumerate(ds):
        if muc_tieu - x in da_thay:
            return da_thay[muc_tieu - x], i
        da_thay[x] = i

print(hai_so_co_tong([2, 7, 11, 15], 9))   # (0, 1)

Bài "hai số có tổng bằng mục tiêu" cho thấy sức mạnh của bảng băm: thay vì hai vòng lặp lồng nhau, ta chỉ duyệt một lần. Ngoài ra bảng băm còn dùng cho bộ nhớ đệm (cache), đếm tần suất, tìm phần tử trùng và lưu cấu hình.

Giới hạn cần biết

  • Khóa phải băm được: trong Python, list không thể làm khóa vì nó thay đổi được; chuỗi, số, tuple thì được.
  • Không phù hợp để duyệt theo thứ tự khóa: bảng băm không tự sắp xếp theo khóa.
  • Tốn bộ nhớ hơn mảng do cần chừa chỗ trống để giảm va chạm.
  • Trường hợp xấu nhất: nếu rất nhiều khóa va chạm, tốc độ có thể giảm; hàm băm tốt tránh được điều này.

Set: người anh em của dictionary

Set (tập hợp) cũng dùng bảng băm nhưng chỉ lưu khóa, không có giá trị. Nó rất tiện để loại trùng và kiểm tra tồn tại:

so = [1, 2, 2, 3, 3, 3]
print(set(so))        # {1, 2, 3}
print(2 in set(so))   # True

Lỗi thường gặp với dictionary

  1. KeyError. Truy cập khóa không tồn tại làm chương trình sập. Dùng .get(khoa, mac_dinh) hoặc kiểm tra khoa in d trước.
  2. Sửa dictionary khi đang duyệt. Thêm hoặc xóa khóa trong lúc lặp gây lỗi; hãy duyệt trên bản sao list(d).
  3. Dùng khóa thay đổi được, như list, sẽ báo TypeError: unhashable. Hãy đổi sang tuple.
  4. Nhầm khóa số và khóa chuỗi: d[1] và d["1"] là hai khóa khác nhau.
nhom = {}
for ten, lop in [("An", "A"), ("Bình", "B"), ("Chi", "A")]:
    nhom.setdefault(lop, []).append(ten)
print(nhom)   # {'A': ['An', 'Chi'], 'B': ['Bình']}

Đoạn trên là mẫu "gom nhóm" rất hay gặp: setdefault tạo danh sách rỗng nếu khóa chưa có. Hãy thử viết lại bằng collections.defaultdict(list) để thấy cách gọn hơn.

Kết luận

Bảng băm đánh đổi một chút bộ nhớ để lấy tốc độ tra cứu gần như tức thì. Khi bạn thấy mình phải duyệt cả danh sách chỉ để tìm một phần tử, hãy tự hỏi: có thể dùng dictionary hoặc set không? Câu hỏi này là một trong những cải tiến hiệu năng đơn giản nhất và hiệu quả nhất.

Khi đã sẵn sàng đi sâu hơn, bạn có thể tham khảo lộ trình học trong các khóa học tại codebem.com.

author_photo
Nguyễn Đình Cường

0 comment