[toc]
## Khái niệm
- Bảng băm là một CTDL thường được sử dụng như một từ điển: mỗi phần tử trong bảng băm là một cặp <khóa, giá trị>. Ta có thể tìm được giá trị thông qua khóa của nó.
- Hàm băm (hash function) là một hàm chuyển đổi các khóa của một tập dữ liệu có kích thước tùy ý thành các giá trị số nguyên thực tế nhỏ để được sử dụng làm chỉ mục (index) trong bảng băm. Các giá trị được trả về bởi hàm băm được gọi là giá trị băm.

- Hàm băm đủ tốt:
+ Tính toán nhanh (không phải là thuật toán)
+ Các khóa được phân bố đều trong bảng
+ Ít xảy ra đụng độ
+ Giải quyết vấn đề băm với các khóa không là số nguyên
## Các dạng hàm băm
- **Hàm băm sử dụng Phương pháp chia:** $h(key)=key\%M$
Với $k$ là khóa, $M$ là kích thước của bảng băm.
- **Hàm băm sử dụng Phương pháp nhân:** $h(key)=[M*(key*A\%1)]$
Với $A$ là hằng số: $0<A<1$ , $key$ là khóa, $M$ là kích thước của bảng băm.
Ví dụ:
$key = 12345$
$A = 0.357840$
$M = 100$
$h(12345) = floor[ 100*(12345*0.357840 mod 1)]$
$= floor[ 100 (4417.5348 mod 1) ]$
$= floor[ 100 (0.5348) ]$
$= floor[ 53.48 ]$
$= 53$
## Các phương pháp giải quyết đụng độ
- Khái niệm sự đụng độ: Hiện tượng các khóa khác nhau nhưng băm cùng địa chỉ như nhau.

### 1. Phương pháp nối kết
- Nối kết trực tiếp
+ Các khóa bị băm vào cùng một địa chỉ sẽ gom thành danh sách.
- Nối kết hợp nhất
+ Bảng băm trong trường hợp này cũng được cài đặt bằng danh sách liên kết. Nhưng các nút bị xung đột địa chỉ được kết nối với nhau qua danh sách liên kết.

### 2. Phương pháp băm lại (địa chỉ mở)

Với hàm băm $h_1(key)=key\%M$
$h(key, i)$ là địa chỉ băm của khóa $key$ nếu tiến hành băm lại lần $i$.
- Phương pháp dò tuyến tính: $h(key, i)=(h_1(key)+i)\%M$
- Phương pháp dò bậc hai: $h(key, i)=(h(key)+i^2)\%M$
- Phương pháp băm kép:
$h_2(key)=(M-2)-key\%(M-2)$
$h(key, i)=(h_1(key)*i+h_2(key))\%M$

**Ví dụ:** Cho bảng băm ở trạng thái vừa khởi tạo có M = 11 nút, lần lượt thêm các khóa 30, 42, 24, 13, 3, 2, 10, 20 vào bảng theo thứ tự từ trái sang.

| Chỉ mục | Khóa - Dò tuyến tính | Khóa - Dò bậc hai | Khóa - Băm kép |
| ------- | -------------------- | ----------------- | -------------- |
| 0 | 20 | 20 | 2 |
| 1 | NULL | NULL | NULL |
| 2 | 24 | 24 | 24 |
| 3 | 13 | 13 | 3 |
| 4 | 3 | 3 | NULL |
| 5 | 2 | NULL | 20 |
| 6 | NULL | 2 | NULL |
| 7 | NULL | NULL | 13 |
| 8 | 30 | 30 | 30 |
| 9 | 42 | 42 | 42 |
| 10 | 10 | 10 | 10 |