thuattoan.dev

Level 2 · Cấu trúc dữ liệu

Hash table

Hàm băm, xử lý va chạm, độ phức tạp trung bình O(1).

Độ khó: Trung bình Visualizer tương tác8 bài luyện tập

Ý tưởng chính

Hash table ánh xạ khoá tới giá trị thông qua hàm băm, cho phép tra cứu trung bình O(1) nhưng cần xử lý va chạm (collision).

Hình dung

Tủ gửi đồ siêu thị có 100 ngăn: số thẻ của bạn quyết định ngăn nào. Muốn lấy đồ, bạn đi thẳng tới ngăn đó thay vì mở từng ngăn.

Cách hoạt động

  1. 1

    Hàm băm biến khoá thành chỉ số ô, ví dụ h(key) = key % M.

  2. 2

    Thêm: tính h(key) và cất khoá vào ô đó.

  3. 3

    Tìm: tính lại h(key) và chỉ xem ô đó.

  4. 4

    Va chạm (hai khoá cùng ô): chaining — mỗi ô là một danh sách; hoặc linear probing — ô đã có người thì thử ô kế tiếp.

Độ phức tạp

Thêm, xoá, tìm trung bình O(1). Trường hợp xấu (quá nhiều va chạm) có thể thành O(n).

Khi nào dùng

Tra cứu nhanh theo khoá: đếm tần suất, kiểm tra đã xuất hiện chưa, ánh xạ ID → dữ liệu, loại trùng.

Lỗi hay gặp

  • Bảng quá đầy (hệ số tải cao) làm va chạm tăng và chậm đi.
  • unordered_map có thể bị test đặc biệt làm va chạm hàng loạt trên Codeforces — dùng hàm băm tuỳ chỉnh hoặc map.
  • Cần giữ thứ tự khoá thì hash table không phù hợp.

Liên hệ thực tế

Ứng dụng thực tế

Kỹ thuật này xuất hiện ở đâu ngoài đời — để bạn có sẵn một hình ảnh cụ thể khi học.

  • Cache

    Redis, Memcached hay cache trong ứng dụng lưu kết quả theo khoá để lần sau lấy ra gần như tức thì.

  • dict, HashMap, object hằng ngày

    Đếm tần suất từ, tra người dùng theo ID, gom đơn hàng theo khách — dict (Python), HashMap (Java) chính là hash table.

  • Kiểm tra trùng lặp

    Username đã tồn tại chưa, email này đã đăng ký chưa, phần tử này đã xử lý chưa — tất cả trả lời trong O(1) trung bình.

  • JOIN trong cơ sở dữ liệu

    Hash join băm một bảng theo khoá rồi dò bảng còn lại, nhanh hơn nhiều so với so từng cặp dòng.

Xem thuật toán chạy

Minh hoạ từng bước

Chạy tự động hoặc đi từng bước; theo dõi hình minh hoạ, lời giải thích, giá trị biến và dòng code tương ứng cùng lúc.

Tự làm

Luyện tập trên Codeforces

Sắp xếp từ dễ đến khó theo rating, mỗi bài kèm tóm tắt đề. Bí thì mở gợi ý — có 3 mức, từ hướng suy nghĩ tới gần lời giải.

  • Rating 1200

    Remove Two Letters(mở Codeforces trong tab mới)

    Cho chuỗi s độ dài n. Xoá đúng hai ký tự liên tiếp. Đếm số chuỗi khác nhau có thể thu được.

    Test mẫu & giải thích
    Input
    7
6
aaabcc
10
aaaaaaaaaa
6
abcdef
7
abacaba
6
cccfff
4
abba
5
ababa
    Output
    4
1
5
3
3
3
1

    1. Test 1

      Với s=aaabcc (n=6), có n-1=5 cách xoá 2 ký tự liên tiếp tại vị trí i (i=1..5); hai cách xoá tại i và i+1 cho cùng một chuỗi kết quả khi và chỉ khi s[i]=s[i+2]. Kiểm tra i=1..4: chỉ i=1 thoả (s1=a=s3=a), các i=2,3,4 đều khác nhau, nên chỉ có 1 cặp trùng, số chuỗi khác nhau = 5-1=4, khớp output.

    2. Test 2

      Với s=aaaaaaaaaa (n=10, toàn ký tự a), có 9 vị trí xoá nhưng mọi i=1..8 đều có s[i]=s[i+2]=a nên cả 8 cặp liên tiếp đều trùng, mọi kết quả xoá đều là chuỗi 8 chữ a giống hệt nhau, số chuỗi khác nhau = 9-8=1, khớp output.

  • Rating 1300

    Registration System(mở Codeforces trong tab mới)

    Hệ thống đăng ký nhận lần lượt n tên. Tên chưa có thì in OK; nếu đã có thì cấp tên mới là tên đó kèm số nhỏ nhất i ≥ 1 chưa dùng (name1, name2, …) và in ra.

    Test mẫu & giải thích
    Input
    4
abacaba
acaba
abacaba
acab
    Output
    OK
OK
abacaba1
OK

    Xử lý lần lượt 4 tên: 'abacaba' và 'acaba' chưa từng xuất hiện nên in OK cho cả hai, đồng thời khởi tạo bộ đếm hậu tố =1 cho mỗi tên. Tên thứ ba lại là 'abacaba', đã tồn tại với bộ đếm hiện tại là 1, nên hệ thống cấp tên mới 'abacaba'+'1'='abacaba1' rồi tăng bộ đếm lên 2. Tên thứ tư 'acab' chưa xuất hiện nên in OK. Kết quả OK, OK, abacaba1, OK khớp đúng thứ tự output.

  • Rating 1400

    String Equality(mở Codeforces trong tab mới)

    Cho hai chuỗi a, b và số k. Trên a được: đổi chỗ hai ký tự kề nhau; hoặc chọn k ký tự liên tiếp cùng là c (c ≠ 'z') và đổi hết thành c + 1. Hỏi có biến a thành b được không.

    Test mẫu & giải thích
    Input
    4
3 3
abc
bcd
4 2
abba
azza
2 1
zz
aa
6 2
aaabba
ddddcc
    Output
    No
Yes
No
Yes

    1. Test 1

      Vì phép đổi chỗ kề nhau cho phép sắp xếp lại a tuỳ ý, chỉ số lượng mỗi ký tự trong a mới quan trọng; phép biến đổi thứ hai chuyển đúng k bản sao ký tự c thành k bản sao c+1, nên xử lý lan truyền phần dư từ 'a' đến 'z': tại mỗi ký tự, số lượng dư ra sau khi giữ đúng số lượng ký tự đó theo b phải chia hết cho k để chuyển hết lên ký tự kế tiếp. Với test 1 (k=3, a='abc', b='bcd'): tại ký tự 'a', a có 1 ký tự 'a' nhưng b cần 0, phần dư 1 không chia hết cho k=3 nên không thể chuyển hết lên 'b', in 'No'.

    2. Test 2

      Với test 2 (k=2, a='abba' có 2 'a' và 2 'b', b='azza' có 2 'a' và 2 'z'): số 'a' khớp ngay (dư 0); 2 chữ 'b' dư ra chia hết cho k=2 nên chuyển hết thành 2 chữ 'c', rồi tiếp tục lan truyền nguyên vẹn 2 đơn vị qua từng ký tự cho đến 'z' thì vừa khớp đúng 2 chữ 'z' mà b yêu cầu, không còn dư, nên in 'Yes'.

  • Rating 1500

    Winner(mở Codeforces trong tab mới)

    Có n lượt ghi điểm dạng "tên điểm" (điểm có thể âm). Người thắng có điểm cuối cùng cao nhất; nếu nhiều người bằng nhau, ai đạt ít nhất số điểm đó sớm nhất trong quá trình chơi thì thắng. In tên người thắng.

    Test mẫu & giải thích
    Input
    3
mike 3
andrew 5
mike 2
    Output
    andrew

    Sau dòng 1, mike có 3 điểm. Sau dòng 2, andrew có 5 điểm - đây là lần đầu tiên có người đạt mốc điểm cuối cùng cao nhất (5). Sau dòng 3, mike được cộng thêm 2 điểm, đạt tổng 3+2=5, bằng andrew nhưng đạt mốc 5 muộn hơn (ở lượt thứ 3, so với lượt thứ 2 của andrew). Vì hai người hoà điểm cuối cùng, người thắng là người đạt đúng mức điểm cao nhất đó sớm nhất trong quá trình chơi, tức andrew, khớp output 'andrew'.

  • Rating 1600

    Palindrome Pairs(mở Codeforces trong tab mới)

    Cho n chuỗi. Đếm số cặp (i, j), i < j, sao cho chuỗi ghép s_i + s_j có một hoán vị ký tự là palindrome.

    Test mẫu & giải thích
    Input
    3
aa
bb
cd
    Output
    1

    Với 3 chuỗi aa, bb, cd: một chuỗi ghép có hoán vị palindrome khi và chỉ khi số ký tự có tần suất lẻ ≤ 1. Ghép aa+bb = "aabb" có a:2, b:2 (đều chẵn) → có hoán vị palindrome (abba), tính là 1 cặp hợp lệ. Ghép aa+cd = "aacd" có c:1, d:1 (hai ký tự lẻ) → không thể. Ghép bb+cd = "bbcd" cũng có c:1, d:1 → không thể. Vậy chỉ đúng 1 cặp thỏa, khớp sampleOutput = 1.

  • Rating 1600

    Binary String Copying(mở Codeforces trong tab mới)

    Cho chuỗi nhị phân s và m bản sao. Ở bản sao thứ i, sắp xếp đoạn [l_i, r_i]. Đếm số chuỗi khác nhau trong m bản sao sau khi sắp.

    Test mẫu & giải thích
    Input
    3
6 5
101100
1 2
1 3
2 4
5 5
1 6
6 4
100111
2 2
1 4
1 3
1 2
1 1
0
1 1
    Output
    3
3
1

    Với test đầu s=101100 (n=6), mỗi truy vấn luôn tác động lên s gốc chứ không tích lũy: truy vấn "1 2" sắp s1s2='10' thành '01' cho chuỗi '011100'; truy vấn "1 3" sắp s1s3='101' thành '011' cũng ra '011100' — trùng bản trước. Truy vấn "2 4" có s2s4='011' đã sắp sẵn nên chuỗi giữ nguyên '101100', truy vấn "5 5" (đoạn 1 ký tự) cũng không đổi '101100'. Truy vấn "1 6" sắp toàn bộ chuỗi (3 số 0, 3 số 1) thành '000111'. Vậy 5 bản sao chỉ tạo 3 chuỗi phân biệt: '011100', '101100', '000111', khớp đáp án 3.

  • Rating 1700

    Equivalent Strings(mở Codeforces trong tab mới)

    Hai chuỗi cùng độ dài là tương đương nếu bằng nhau, hoặc (khi độ dài chẵn) chia mỗi chuỗi làm hai nửa a1a2, b1b2 và (a1 ~ b1, a2 ~ b2) hoặc (a1 ~ b2, a2 ~ b1). Kiểm tra hai chuỗi cho trước có tương đương không.

    Test mẫu & giải thích
    Input
    aaba
abaa
    Output
    YES

    Với s1='aaba', s2='abaa' (độ dài 4, chẵn): chia s1 thành 'aa'+'ba', s2 thành 'ab'+'aa'. So khớp chéo: 'aa' tương đương 'aa' (giống hệt), còn 'ba' tương đương 'ab' vì tách tiếp 'ab'='a'+'b' và 'ba'='b'+'a' khớp theo định nghĩa đệ quy đổi chỗ hai nửa. Vì tồn tại một cách chia thỏa mãn cả hai điều kiện đệ quy nên hai chuỗi tương đương, in YES.

  • Rating 1700

    Password(mở Codeforces trong tab mới)

    Cho chuỗi s. Tìm chuỗi t dài nhất vừa là tiền tố, vừa là hậu tố của s, và còn xuất hiện ở giữa (không phải tiền tố cũng không phải hậu tố). Không có thì in "Just a legend".

    Test mẫu & giải thích
    Input
    fixprefixsuffix
    Output
    fix

    s='fixprefixsuffix' dài 15 ký tự. Tiền tố dài nhất trùng hậu tố là 'fix' (3 ký tự đầu 'f-i-x', 3 ký tự cuối cũng 'f-i-x' vì s kết thúc bằng 'suffix'). 'fix' còn xuất hiện ở giữa, nằm trong 'prefix' (p-r-e-f-i-x), tại một vị trí không phải occurrence tiền tố (1-3) cũng không phải hậu tố (13-15). Vì vừa là border vừa xuất hiện độc lập ở giữa nên đáp án là 'fix'.