Bài giảng Câu trúc dữ liệu và giải thuật - Chương V: Bảng băm

26/03/12
1
CẤU TRÚC DỮ LIỆU 
VÀ GIẢI THUẬT
CHƢƠNG V: BẢNG BĂM
1. Bảng băm mở
1.1. Bảng băm
1.2. Hàm băm
1.3. Xung đột
1.4. Một số hàm băm thông dụng
2. Bảng băm đóng
2.1. Băm lại tuyến tính.
2.2. Băm lại bình phương
2.3. Băm lại bằng cách tạo vùng mới
26/03/12
2
1. Bảng băm mở
 Bảng băm (Hash Table): 
- Mảng B gồm m phần tử
-Lưu trữ chỉ số định vị phần tử dữ liệu có khóa 
phân biệt thuộc tập số nguyên { 0,1,2m-1}
Hash Tables - Structure
• Simplest case:
• Assume items have integer keys in the range 1 .. m
• Use the value of the key itself
to select a slot in a 
direct access table
in which to store the item
• To search for an item with key, k,
just look in slot k
• If there’s an item there,
you’ve found it
• If the tag is 0, it’s missing.
• Constant time, O(1)
1. Bảng băm mở
Hash Tables - Relaxing the constraints
• Keys are integers
• Need a hash function
h( key )  integer
 ie one that maps a key to 
an integer
• Applying this function to the
key produces an address
• If h maps each key to a unique
integer in the range 0 .. m-1
then search is O(1)
1. Bảng băm mở
 Hàm băm 
(Hash function):
H(x) cho giá trị là một chỉ số phần tử của B
1. Bảng băm mở
26/03/12
3
 Xung đột (collision): 
– x1x2 nhưng H(x1)=H(x2)
1. Bảng băm mở
Xung đột:Hash Tables - Collision handling
• Collisions
• Occur when the hash function maps 
two different keys to the same address
• The table must be able to recognise and resolve this
• Recognise
• Store the actual key with the item in the hash table
• Compute the address
• k = h( key )
• Check for a hit
• if ( table[k].key == key ) then hit
else try next entry
• Resolution
• Variety of techniques
We’ll look at various
“try next entry” schemes
1. Bảng băm mở
Xung đột:
 Giải quyết:
– liên kết các danh sách có các khóa khác
nhau nhưng có cùng giá trị hàm băm
thành một danh sách
– liên kết trong bẳng băm B sẽ trỏ tới danh
sách đầu tiên.
1. Bảng băm mở
Hash Tables - Linked lists
• Collisions - Resolution
Linked list attached 
to each primary table slot
• h(i) == h(i1)
• h(k) == h(k1) == h(k2)
• Searching for i1
• Calculate h(i1)
• Item in table, i,
doesn’t match
• Follow linked list to i1
• If NULL found, 
key isn’t in table
1. Bảng băm mở
26/03/12
4
Một số hàm băm thông dụng:
 Hàm cắt bỏ bỏ bớt một phần nào đó của
khóa.
– Ví dụ: x=842615, bỏ bớt chẳng hạn các
chữ số hàng lẻ (1,3,5), số còn lại sẽ là
821. Vậy H(x) = H(842615) = 821.
– Nhận xét: khó có phân bố đều.
1. Bảng băm mở
 Hàm gấp chia số nguyên đó thành một số
đoạn tùy chọn, sau đó kết hợp
 Ví dụ: Số các hàng lẻ: 465 và số các hàng
chẵn: 821, vậy H(x)=465+821=1286.
– Nhận xét: Tính chất thứ hai có thể thỏa mãn tốt
hơn
1. Bảng băm mở
 Hàm phần dƣ của phép chia x/m
 Nên chọn m là số nguyên tố.
– Nhận xét: Các cách lấy phần dư cho khả năng
tránh hiện tượng xung đột
1. Bảng băm mở
Hash Tables - Reducing the range to [ 0, m )
 Division 
• Use a mod function
 h(k) = k mod m
• Choice of m?
• Powers of 2 are generally not good!
h(k) = k mod 2n
selects last n bits of k
• All combinations are not generally equally likely
• Prime numbers close to 2n seem to be good choices
 eg want ~4000 entry table, choose m = 4093
0110010111000011010
k mod 28 selects these bits
1. Bảng băm mở
26/03/12
5
2. Bảng băm đóng
 Bảng băm mở: chỉ dùng để lưu trữ các liên 
kết trỏ đến các thành phần dữ liệu có khóa 
tương ứng. 
 Bảng băm đóng: bảng băm mà mỗi thành 
phần của nó lưu trữ chính các thành phần 
dữ liệu. 
Các phƣơng pháp xử lý:
a) Băm lại tuyến tính
Hi (x) = (H(x)+i) mod m
– Nhận xét: Các giá trị hàm băm xếp 
thành từng đoạn con, nên việc tìm kiếm 
ví trí rỗng sẽ rất chậm.
2. Bảng băm đóng
Hash Tables - Re-hash functions
The re-hash function
• Many variations
• Linear probing
• h’(x) is +1
• Go to the next slot
until you find one empty
• Can lead to bad clustering
• Re-hash keys fill in gaps
between other keys and exacerbate
the collision problem
2. Bảng băm đóng
b) Băm lại bình phương
Hi(x) = ( H(x)+i2) mod m 
Hash Tables - Re-hash functions
The re-hash function
• Many variations
• Quadratic probing
• h’(x) is c i2 on the ith probe
• Avoids primary clustering
• Secondary clustering occurs
• All keys which collide on h(x) follow the same 
sequence
• First 
• a = h(j) = h(k)
• Then a + c, a + 4c, a + 9c, ....
• Secondary clustering generally less of a problem
2. Bảng băm đóng
26/03/12
6
c) Băm lại bằng cách tạo vùng mới
 Ngoài bảng B cần tạo ra một vùng không gian mới
Hash Tables - Overflow area
Overflow area
• Linked list constructed
in special area of table
called overflow area
• h(k) == h(j)
• k stored first
• Adding j
• Calculate h(j)
• Find k
• Get first slot in overflow area
• Put j in it
• k’s pointer points to this slot
• Searching - same as linked list
2. Bảng băm đóng