Bảng băm¶
Một bảng băm (hash table), còn được gọi là bảng băm (hash map), lưu trữ các ánh xạ từ các khóa (key) đến các giá trị (value), cho phép truy vấn hiệu quả. Cụ thể, khi cho trước một khóa key, ta có thể lấy được giá trị value tương ứng từ bảng băm trong thời gian \(O(1)\).
Như hình bên dưới, giả sử chúng ta có \(n\) học sinh, mỗi học sinh có hai thông tin: tên và mã số học sinh. Nếu muốn hỗ trợ truy vấn "cho mã số học sinh, trả về tên tương ứng", chúng ta có thể sử dụng bảng băm được hiển thị dưới đây.
Ngoài bảng băm, mảng và danh sách liên kết cũng có thể triển khai chức năng truy vấn. Bảng dưới đây so sánh hiệu suất giữa chúng.
- Thêm phần tử: Chỉ đơn giản là thêm phần tử vào cuối mảng (danh sách liên kết), mất thời gian \(O(1)\).
- Truy vấn phần tử: Vì mảng (danh sách liên kết) không được sắp xếp, cần phải duyệt qua tất cả phần tử, mất thời gian \(O(n)\).
- Xóa phần tử: Đầu tiên phải định vị phần tử, sau đó xóa nó khỏi mảng (danh sách liên kết), mất thời gian \(O(n)\).
Bảng
| Mảng | Danh sách liên kết | Bảng băm | |
|---|---|---|---|
| Tìm phần tử | \(O(n)\) | \(O(n)\) | \(O(1)\) |
| Thêm phần tử | \(O(1)\) | \(O(1)\) | \(O(1)\) |
| Xóa phần tử | \(O(n)\) | \(O(n)\) | \(O(1)\) |
Có thể thấy, các thao tác chèn, xóa, tìm kiếm và cập nhật trong bảng băm đều có độ phức tạp thời gian là \(O(1)\), giúp bảng băm đạt hiệu suất rất cao.
Các thao tác phổ biến trên bảng băm¶
Các thao tác phổ biến trên bảng băm bao gồm: khởi tạo, thao tác truy vấn, thêm cặp khóa-giá trị và xóa cặp khóa-giá trị. Mã nguồn ví dụ như sau:
# Khởi tạo bảng băm
hmap: dict = {}
# Thao tác thêm
# Thêm cặp khóa-giá trị (key, value) vào bảng băm
hmap[12836] = "XiaoHa"
hmap[15937] = "XiaoLuo"
hmap[16750] = "XiaoSuan"
hmap[13276] = "XiaoFa"
hmap[10583] = "XiaoYa"
# Thao tác truy vấn
# Nhập khóa vào bảng băm để lấy giá trị
name: str = hmap[15937]
# Thao tác xóa
# Xóa cặp khóa-giá trị (key, value) khỏi bảng băm
hmap.pop(10583)
/* Khởi tạo bảng băm */
unordered_map<int, string> map;
/* Thao tác thêm */
// Thêm cặp khóa-giá trị (key, value) vào bảng băm
map[12836] = "XiaoHa";
map[15937] = "XiaoLuo";
map[16750] = "XiaoSuan";
map[13276] = "XiaoFa";
map[10583] = "XiaoYa";
/* Thao tác truy vấn */
// Nhập khóa vào bảng băm để lấy giá trị
string name = map[15937];
/* Thao tác xóa */
// Xóa cặp khóa-giá trị (key, value) khỏi bảng băm
map.erase(10583);
/* Khởi tạo bảng băm */
Map<Integer, String> map = new HashMap<>();
/* Thao tác thêm */
// Thêm cặp khóa-giá trị (key, value) vào bảng băm
map.put(12836, "XiaoHa");
map.put(15937, "XiaoLuo");
map.put(16750, "XiaoSuan");
map.put(13276, "XiaoFa");
map.put(10583, "XiaoYa");
/* Thao tác truy vấn */
// Nhập khóa vào bảng băm để lấy giá trị
String name = map.get(15937);
/* Thao tác xóa */
// Xóa cặp khóa-giá trị (key, value) khỏi bảng băm
map.remove(10583);
/* Khởi tạo bảng băm */
Dictionary<int, string> map = new() {
/* Thao tác thêm */
// Thêm cặp khóa-giá trị (key, value) vào bảng băm
{ 12836, "XiaoHa" },
{ 15937, "XiaoLuo" },
{ 16750, "XiaoSuan" },
{ 13276, "XiaoFa" },
{ 10583, "XiaoYa" }
};
/* Thao tác truy vấn */
// Nhập khóa vào bảng băm để lấy giá trị
string name = map[15937];
/* Thao tác xóa */
// Xóa cặp khóa-giá trị (key, value) khỏi bảng băm
map.Remove(10583);
/* Khởi tạo bảng băm */
hmap := make(map[int]string)
/* Thao tác thêm */
// Thêm cặp khóa-giá trị (key, value) vào bảng băm
hmap[12836] = "XiaoHa"
hmap[15937] = "XiaoLuo"
hmap[16750] = "XiaoSuan"
hmap[13276] = "XiaoFa"
hmap[10583] = "XiaoYa"
/* Thao tác truy vấn */
// Nhập khóa vào bảng băm để lấy giá trị
name := hmap[15937]
/* Thao tác xóa */
// Xóa cặp khóa-giá trị (key, value) khỏi bảng băm
delete(hmap, 10583)
/* Khởi tạo bảng băm */
var map: [Int: String] = [:]
/* Thao tác thêm */
// Thêm cặp khóa-giá trị (key, value) vào bảng băm
map[12836] = "XiaoHa"
map[15937] = "XiaoLuo"
map[16750] = "XiaoSuan"
map[13276] = "XiaoFa"
map[10583] = "XiaoYa"
/* Thao tác truy vấn */
// Nhập khóa vào bảng băm để lấy giá trị
let name = map[15937]!
/* Thao tác xóa */
// Xóa cặp khóa-giá trị (key, value) khỏi bảng băm
map.removeValue(forKey: 10583)
/* Khởi tạo bảng băm */
const map = new Map();
/* Thao tác thêm */
// Thêm cặp khóa-giá trị (key, value) vào bảng băm
map.set(12836, 'XiaoHa');
map.set(15937, 'XiaoLuo');
map.set(16750, 'XiaoSuan');
map.set(13276, 'XiaoFa');
map.set(10583, 'XiaoYa');
/* Thao tác truy vấn */
// Nhập khóa vào bảng băm để lấy giá trị
let name = map.get(15937);
/* Thao tác xóa */
// Xóa cặp khóa-giá trị (key, value) khỏi bảng băm
map.delete(10583);
/* Khởi tạo bảng băm */
const map = new Map<number, string>();
/* Thao tác thêm */
// Thêm cặp khóa-giá trị (key, value) vào bảng băm
map.set(12836, 'XiaoHa');
map.set(15937, 'XiaoLuo');
map.set(16750, 'XiaoSuan');
map.set(13276, 'XiaoFa');
map.set(10583, 'XiaoYa');
console.info('\nSau khi thêm, bảng băm là\nKhóa -> Giá trị');
console.info(map);
/* Thao tác truy vấn */
// Nhập khóa vào bảng băm để lấy giá trị
let name = map.get(15937);
console.info('\nNhập mã sinh viên 15937, truy vấn được tên ' + name);
/* Thao tác xóa */
// Xóa cặp khóa-giá trị (key, value) khỏi bảng băm
map.delete(10583);
console.info('\nSau khi xóa 10583, bảng băm là\nKhóa -> Giá trị');
console.info(map);
/* Khởi tạo bảng băm */
Map<int, String> map = {};
/* Thao tác thêm */
// Thêm cặp khóa-giá trị (key, value) vào bảng băm
map[12836] = "XiaoHa";
map[15937] = "XiaoLuo";
map[16750] = "XiaoSuan";
map[13276] = "XiaoFa";
map[10583] = "XiaoYa";
/* Thao tác truy vấn */
// Nhập khóa vào bảng băm để lấy giá trị
String name = map[15937];
/* Thao tác xóa */
// Xóa cặp khóa-giá trị (key, value) khỏi bảng băm
map.remove(10583);
use std::collections::HashMap;
/* Khởi tạo bảng băm */
let mut map: HashMap<i32, String> = HashMap::new();
/* Thao tác thêm */
// Thêm cặp khóa-giá trị (key, value) vào bảng băm
map.insert(12836, "XiaoHa".to_string());
map.insert(15937, "XiaoLuo".to_string());
map.insert(16750, "XiaoSuan".to_string());
map.insert(13276, "XiaoFa".to_string());
map.insert(10583, "XiaoYa".to_string());
/* Thao tác truy vấn */
// Nhập khóa vào bảng băm để lấy giá trị
let _name: Option<&String> = map.get(&15937);
/* Thao tác xóa */
// Xóa cặp khóa-giá trị (key, value) khỏi bảng băm
let _removed_value: Option<String> = map.remove(&10583);
/* Khởi tạo bảng băm */
val map = HashMap<Int,String>()
/* Thao tác thêm */
// Thêm cặp khóa-giá trị (key, value) vào bảng băm
map[12836] = "XiaoHa"
map[15937] = "XiaoLuo"
map[16750] = "XiaoSuan"
map[13276] = "XiaoFa"
map[10583] = "XiaoYa"
/* Thao tác truy vấn */
// Nhập khóa vào bảng băm để lấy giá trị
val name = map[15937]
/* Thao tác xóa */
// Xóa cặp khóa-giá trị (key, value) khỏi bảng băm
map.remove(10583)
# Khởi tạo bảng băm
hmap = {}
# Thao tác thêm
# Thêm cặp khóa-giá trị (key, value) vào bảng băm
hmap[12836] = "XiaoHa"
hmap[15937] = "XiaoLuo"
hmap[16750] = "XiaoSuan"
hmap[13276] = "XiaoFa"
hmap[10583] = "XiaoYa"
# Thao tác truy vấn
# Nhập khóa vào bảng băm để lấy giá trị
name = hmap[15937]
# Thao tác xóa
# Xóa cặp khóa-giá trị (key, value) khỏi bảng băm
hmap.delete(10583)
Minh họa thực thi
https://pythontutor.com/render.html#code=%22%22%22Driver%20Code%22%22%22%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20%23%20%E5%88%9D%E5%A7%8B%E5%8C%96%E5%93%88%E5%B8%8C%E8%A1%A8%0A%20%20%20%20hmap%20%3D%20%7B%7D%0A%20%20%20%20%0A%20%20%20%20%23%20%E6%B7%BB%E5%8A%A0%E6%93%8D%E4%BD%9C%0A%20%20%20%20%23%20%E5%9C%A8%E5%93%88%E5%B8%8C%E8%A1%A8%E4%B8%AD%E6%B7%BB%E5%8A%A0%E9%94%AE%E5%80%BC%E5%AF%B9%20%28key,%20value%29%0A%20%20%20%20hmap%5B12836%5D%20%3D%20%22%E5%B0%8F%E5%93%88%22%0A%20%20%20%20hmap%5B15937%5D%20%3D%20%22%E5%B0%8F%E5%95%B0%22%0A%20%20%20%20hmap%5B16750%5D%20%3D%20%22%E5%B0%8F%E7%AE%97%22%0A%20%20%20%20hmap%5B13276%5D%20%3D%20%22%E5%B0%8F%E6%B3%95%22%0A%20%20%20%20hmap%5B10583%5D%20%3D%20%22%E5%B0%8F%E9%B8%AD%22%0A%20%20%20%20%0A%20%20%20%20%23%20%E6%9F%A5%E8%AF%A2%E6%93%8D%E4%BD%9C%0A%20%20%20%20%23%20%E5%90%91%E5%93%88%E5%B8%8C%E8%A1%A8%E4%B8%AD%E8%BE%93%E5%85%A5%E9%94%AE%20key%20%EF%BC%8C%E5%BE%97%E5%88%B0%E5%80%BC%20value%0A%20%20%20%20name%20%3D%20hmap%5B15937%5D%0A%20%20%20%20%0A%20%20%20%20%23%20%E5%88%A0%E9%99%A4%E6%93%8D%E4%BD%9C%0A%20%20%20%20%23%20%E5%9C%A8%E5%93%88%E5%B8%8C%E8%A1%A8%E4%B8%AD%E5%88%A0%E9%99%A4%E9%94%AE%E5%80%BC%E5%AF%B9%20%28key,%20value%29%0A%20%20%20%20hmap.pop%2810583%29&cumulative=false&curInstr=2&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=311&rawInputLstJSON=%5B%5D&textReferences=false
Có ba cách phổ biến để duyệt bảng băm: duyệt qua các cặp khóa-giá trị, duyệt qua các khóa và duyệt qua các giá trị. Mã ví dụ như sau:
/* Duyệt bảng băm */
// Duyệt qua các cặp khóa-giá trị key->value
for (auto kv: map) {
cout << kv.first << " -> " << kv.second << endl;
}
// Duyệt qua cặp khóa-giá trị key->value bằng iterator
for (auto iter = map.begin(); iter != map.end(); iter++) {
cout << iter->first << "->" << iter->second << endl;
}
/* Duyệt bảng băm */
// Duyệt qua các cặp khóa-giá trị key->value
for (Map.Entry<Integer, String> kv: map.entrySet()) {
System.out.println(kv.getKey() + " -> " + kv.getValue());
}
// Chỉ duyệt qua các khóa
for (int key: map.keySet()) {
System.out.println(key);
}
// Chỉ duyệt qua các giá trị
for (String val: map.values()) {
System.out.println(val);
}
/* Duyệt bảng băm */
// Duyệt qua các cặp khóa-giá trị Key->Value
foreach (var kv in map) {
Console.WriteLine(kv.Key + " -> " + kv.Value);
}
// Chỉ duyệt qua các khóa
foreach (int key in map.Keys) {
Console.WriteLine(key);
}
// Chỉ duyệt qua các giá trị
foreach (string val in map.Values) {
Console.WriteLine(val);
}
/* Duyệt bảng băm */
console.info('\nDuyệt qua các cặp khóa-giá trị Key->Value');
for (const [k, v] of map.entries()) {
console.info(k + ' -> ' + v);
}
console.info('\nDuyệt qua các khóa');
for (const k of map.keys()) {
console.info(k);
}
console.info('\nDuyệt qua các giá trị');
for (const v of map.values()) {
console.info(v);
}
/* Duyệt bảng băm */
console.info('\nDuyệt qua các cặp khóa-giá trị Key->Value');
for (const [k, v] of map.entries()) {
console.info(k + ' -> ' + v);
}
console.info('\nDuyệt qua các khóa');
for (const k of map.keys()) {
console.info(k);
}
console.info('\nDuyệt qua các giá trị');
for (const v of map.values()) {
console.info(v);
}
Minh họa thực thi
https://pythontutor.com/render.html#code=%22%22%22Driver%20Code%22%22%22%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20%23%20%E5%88%9D%E5%A7%8B%E5%8C%96%E5%93%88%E5%B8%8C%E8%A1%A8%0A%20%20%20%20hmap%20%3D%20%7B%7D%0A%20%20%20%20%0A%20%20%20%20%23%20%E6%B7%BB%E5%8A%A0%E6%93%8D%E4%BD%9C%0A%20%20%20%20%23%20%E5%9C%A8%E5%93%88%E5%B8%8C%E8%A1%A8%E4%B8%AD%E6%B7%BB%E5%8A%A0%E9%94%AE%E5%80%BC%E5%AF%B9%20%28key,%20value%29%0A%20%20%20%20hmap%5B12836%5D%20%3D%20%22%E5%B0%8F%E5%93%88%22%0A%20%20%20%20hmap%5B15937%5D%20%3D%20%22%E5%B0%8F%E5%95%B0%22%0A%20%20%20%20hmap%5B16750%5D%20%3D%20%22%E5%B0%8F%E7%AE%97%22%0A%20%20%20%20hmap%5B13276%5D%20%3D%20%22%E5%B0%8F%E6%B3%95%22%0A%20%20%20%20hmap%5B10583%5D%20%3D%20%22%E5%B0%8F%E9%B8%AD%22%0A%20%20%20%20%0A%20%20%20%20%23%20%E9%81%8D%E5%8E%86%E5%93%88%E5%B8%8C%E8%A1%A8%0A%20%20%20%20%23%20%E9%81%8D%E5%8E%86%E9%94%AE%E5%80%BC%E5%AF%B9%20key-%3Evalue%0A%20%20%20%20for%20key,%20value%20in%20hmap.items%28%29%3A%0A%20%20%20%20%20%20%20%20print%28key,%20%22-%3E%22,%20value%29%0A%20%20%20%20%23%20%E5%8D%95%E7%8B%AC%E9%81%8D%E5%8E%86%E9%94%AE%20key%0A%20%20%20%20for%20key%20in%20hmap.keys%28%29%3A%0A%20%20%20%20%20%20%20%20print%28key%29%0A%20%20%20%20%23%20%E5%8D%95%E7%8B%AC%E9%81%8D%E5%8E%86%E5%80%BC%20value%0A%20%20%20%20for%20value%20in%20hmap.values%28%29%3A%0A%20%20%20%20%20%20%20%20print%28value%29&cumulative=false&curInstr=8&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=311&rawInputLstJSON=%5B%5D&textReferences=false
Triển khai bảng băm đơn giản¶
Hãy bắt đầu với trường hợp đơn giản nhất: triển khai bảng băm chỉ bằng một mảng. Trong bảng băm, mỗi vị trí trống trong mảng được gọi là một ngăn (bucket), và mỗi ngăn có thể lưu trữ một cặp khóa-giá trị. Do đó, thao tác tìm kiếm bao gồm việc tìm ngăn chứa key và đọc value được lưu trữ ở đó.
Vậy làm thế nào để tìm được ngăn phù hợp cho một key cho trước? Chúng ta thực hiện việc này bằng một hàm băm (hash function). Hàm băm ánh xạ một không gian đầu vào lớn hơn sang một không gian đầu ra nhỏ hơn. Trong bảng băm, không gian đầu vào là tập hợp tất cả các key, và không gian đầu ra là tập hợp tất cả các ngăn (chỉ số của mảng). Nói cách khác, khi cho trước một key, hàm băm sẽ cho biết cặp khóa-giá trị tương ứng nên được lưu trữ ở đâu trong mảng.
Cho một key, việc tính toán chỉ số của ngăn bao gồm hai bước sau:
- Sử dụng một thuật toán băm
hash()để tính toán một giá trị băm. - Lấy giá trị băm đó chia lấy dư cho số lượng ngăn (độ dài mảng)
capacityđể có được ngăn (chỉ số mảng)indextương ứng vớikey.
Sau đó, chúng ta có thể sử dụng index để truy cập ngăn tương ứng trong bảng băm và lấy ra value.
Giả sử độ dài của mảng là capacity = 100 và thuật toán băm là hash(key) = key. Khi đó hàm băm là key % 100. Hình dưới đây minh họa cách hoạt động của hàm băm này, sử dụng mã số sinh viên làm key và tên làm value.
Đoạn mã dưới đây triển khai một bảng băm đơn giản. Tại đây, chúng ta đóng gói key và value vào một lớp Pair để biểu diễn cặp khóa-giá trị.
Đụng độ mã băm và Thay đổi kích thước¶
Về cơ bản, hàm băm ánh xạ không gian đầu vào gồm tất cả các key sang không gian đầu ra gồm tất cả chỉ số mảng, và không gian đầu vào thường lớn hơn nhiều so với không gian đầu ra. Do đó, về mặt lý thuyết, các đầu vào khác nhau đôi khi phải ánh xạ đến cùng một đầu ra.
Đối với hàm băm trong ví dụ trên, khi các key đầu vào có hai chữ số cuối giống nhau, hàm băm sẽ tạo ra cùng một đầu ra. Ví dụ, khi truy vấn hai sinh viên có mã số 12836 và 20336, chúng ta có:
Như hình bên dưới, hai mã số sinh viên bây giờ đều trỏ đến cùng một tên, điều này rõ ràng là không chính xác. Chúng ta gọi tình huống này, khi nhiều đầu vào ánh xạ đến cùng một đầu ra, là đụng độ mã băm (hash collision).
Dễ thấy rằng dung lượng bảng băm \(n\) càng lớn thì xác suất nhiều key được phân bổ vào cùng một ngăn càng thấp và số lần đụng độ càng ít. Do đó, chúng ta có thể giảm thiểu đụng độ mã băm bằng cách mở rộng bảng băm.
Như hình bên dưới, trước khi mở rộng, các cặp khóa-giá trị (136, A) và (236, D) bị đụng độ, nhưng sau khi mở rộng, đụng độ đã biến mất.
Tương tự như việc thay đổi kích thước của mảng, việc thay đổi kích thước của bảng băm yêu cầu di chuyển toàn bộ các cặp khóa-giá trị từ bảng cũ sang bảng mới, điều này rất tốn kém. Ngoài ra, do dung lượng bảng băm capacity thay đổi, chúng ta phải tính toán lại vị trí lưu trữ của từng cặp khóa-giá trị bằng hàm băm, điều này làm tăng thêm chi phí thay đổi kích thước. Vì lý do này, các ngôn ngữ lập trình thường dự trữ một dung lượng bảng băm đủ lớn để tránh việc thay đổi kích thước thường xuyên.
Hệ số tải (load factor) là một khái niệm quan trọng trong bảng băm. Nó được định nghĩa là số lượng phần tử hiện có trong bảng băm chia cho số lượng ngăn, và được dùng để đo lường mức độ nghiêm trọng của đụng độ mã băm. Nó cũng thường được sử dụng làm ngưỡng để kích hoạt việc thay đổi kích thước bảng băm. Ví dụ, trong Java, khi hệ số tải vượt quá \(0.75\), hệ thống sẽ mở rộng bảng băm lên gấp đôi kích thước ban đầu.