BẢNG BĂM
(HASH TABLES)
Nhóm 1:
Trần Ngự Bình
Tô Thanh Hải
Trần Văn Long
Đoàn Thị Thu Minh
Vũ Đức Tuấn
Mục tiêu

Hiểu được cơ sở lý thuyết về cấu trúc
dữ liệu Bảng băm

Áp dụng cho các bài toán hỗ trợ các
phép toán chính trên từ điển: Chèn,
Xóa, Tìm kiếm
Nội dung

Bảng địa chỉ trực tiếp

Bảng băm

Hàm băm

Giải quyết xung đột: Dây chuyền & Định địa chỉ
mở

Kỹ thuật băm hoàn hảo
Mở đầu: Một số khái niệm

Tập hợp động

bảng địa chỉ trực
tiếp
Bảng địa chỉ trực tiếp (2)
0
1
2
3
4
5
6
7
8
9
9  0  7 
1  4  6 
2  3 
5 
8 
U
K
T[0 9]
Khe, vị trí
Khe k trỏ đến phần tử
trong tập hợp có khóa k
T[k] = NIL khi
tập hợp không
có thành phần
nào có khóa k
Bảng địa chỉ trực tiếp (3)
0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
…
         
           
            
            
             
              
              


Tập hợp các khóa K có thể sẻ nhỏ hơn U rất nhiều

Khi tập các khóa K được chứa trong từ điển nhỏ hơn rất
nhiều so với các trường hợp có thể xảy ra U, bảng băm
sẻ tiêu tốn ít không gian lưu trữ hơn bảng địa chỉ trực
tiếp

Θ(|K|) không gian nhớ

O(1) thời gian trung bình để tìm kiếm 1 phần tử

Θ(1) thời gian xấu nhất để tìm kiếm một phần tử trong bảng địa
chỉ trực tiếp
Bảng băm

Đối với địa chỉ trực tiếp: Một phần tử với khóa k 
T[k]

Bảng băm: một phần tử với khóa k  T[
h(k)
]

h(k): hàm băm; tường được tính toán với độ phức tạp O(1)

h: U  {0, 1, , m-1}

Một phần tử với khóa k được băm vào khe h(k)

h(k) là hàm băm của khóa k


Kỹ thuật băm hoàn hảo
Hàm băm

Điều gì tạo nên một hàm băm tốt

Chuyển các khóa dưới dạng các số
tự nhiên

Phương pháp chia

Phương pháp nhân

Phổ băm
Thế nào là hàm băm tốt

Tính đơn giản

Giảm thiểu các khóa được băm cùng
khe

Độ phức tạp O(1)
Điều gì tạo nên một hàm băm
tốt

Một hàm băm tốt thỏa (xấp xỉ) giả thiết của
kỹ thuật băm đều đơn giản: mỗi khóa có
khả năng như nhau để băm vào bất kỳ vị
trí nào trong số m khe.


Như vậy, nếu các khóa không phải là các số
tự nhiên, ta phải có 1 cách nào đó để chuyển
chúng về dưới dạng các số tự nhiên. Ví dụ, 1
khóa là một chuỗi ký tự, được chuyển về dưới
dạng một số nguyên được biểu diễn theo cơ
số thích hợp.
Phương pháp chia

Ánh xạ một khóa k vào một trong số m khe
bằng cách lấy số dư của k chia cho m:
h(k) = k mod m.

Phương pháp này có
độ phức tạp O(1)
do
nó chỉ yêu cầu 1 phép chia đơn lẻ

Ví dụ, nếu bảng băm có kích cỡ m = 12 và
khóa là k = 100, thì h(k) = 4. Bởi vì nó yêu
cầu một phép chia đơn lẻ, kỹ thuật băm bằng
phép chia chạy khá nhanh.
Ví dụ của phương pháp chia

Giả sử cần chèn các khóa k có giá trị
như sau: 5, 28, 19, 15, 20, 33, 12, 29,
10 vào bảng băm có 9 khe. Sử dụng
phương pháp chia, ta có hàm băm như
sau:
h(k) = k mod 9
Nhận xét đối với phương pháp

Nhân giá trị này với m và lấy sàn của kết quả.
h(k) = m(kA mod 1)⌊ ⌋
Trong đó “kA mod 1” có nghĩa là phần phân số của
kA, tức là, kA – kA .⌊ ⌋

Phương pháp này có
độ phức tạp O(1)
Nhận xét đối với phương pháp
nhân

Giá trị của m là không tới hạn. Ta
thường chọn giá trị m là một lũy thừa
của 2 (m = 2
p
với một số nguyên p).

Chọn lựa tối giá trị của A ưu tùy thuộc
vào các đặc tính của dữ liệu đang được
băm. Knuth đề cập chi tiết sự lựa chọn
của A và gợi ý rằng: A≈ (√5 -1)/2 =
0.6180339887…
Ví dụ

Giả sử ta có k = 123456, m = 10000.

Lúc này hàm băm h(k) sẽ được xác định theo
phương pháp nhân như sau:
h(k) = m(kA mod 1)⌊ ⌋
Với A≈ (√5 -1)/2 = 0.6180339887… (theo đề xuất của
Knuth)