Bảng băm (Hash table)
Giáo viên: Nguyễn Văn Toàn
9-Apr-06
Nguyễn Văn Toàn - CTDL 2
1
Dẫn nhập
Một số nhận xét khi tìm kiếm trên mảng (cid:132) Nếu mảng chưa được sắp thứ tự (cid:198) tìm tuyển tính, thời
gian sẽ là O(n)
(cid:138) Nếu không tìm thấy, chúng ta phải duyệt n phần tử (cid:138) Nếu tìm thấy, trung bình sẽ duyệt n/2 phần tử
(cid:132) Nếu mảng được sắp xếp (cid:198) tìm nhị phân
(cid:138) Thời gian tìm kiếm O(log n) (cid:138) Nếu tìm được hay không thì thời gian tìm kiếm gần như
(cid:132) Có phương án nào hay hơn ?
(cid:138) Có phương pháp nào sẽ cho thời gian tìm kiếm là O(1) ? (cid:138) Câu trả lời là có nếu chúng ta tổ chức lại mảng theo cơ
nhau
9-Apr-06
Nguyễn Văn Toàn - CTDL 2
2
chế khác.
Băm (Hashing)
Giả sử chúng ta có một hàm đặc biệt (“magic function”), hàm có tham số là giá trị cần tìm x, trả về một vị trí trên mảng i : f(x)=i (cid:132) a[i] = x (cid:198) Tìm thấy (cid:132) a[i] <> x (cid:198) Không tìm thấy Các hàm băm thông dụng: (cid:132) Chia lấy dư. Ví dụ: f(x) = x % 100 (cid:132) Dãy số tuần tự. Ví dụ: f(123456789) = 258
9-Apr-06
Nguyễn Văn Toàn - CTDL 2
3
Ví dụ về hàm băm (hash function)
Khóa
Chỉ số
kiwi
0
1
2
banana watermelon
3
Hàm băm thực chất là một ánh xạ biến đổi khóa thành chỉ số của bảng. Hàm băm cho chúng ta các giá trị như sau: hashCode("apple")
4 = 5
5
6
7
8
apple mango cantaloupe grapes strawberry
9-Apr-06
Nguyễn Văn Toàn - CTDL 2
4
hashCode("watermelon") = 3 hashCode("grapes") = 8 hashCode("cantaloupe") = 7 hashCode("kiwi") = 0 hashCode("strawberry") = 9 hashCode("mango") = 6 hashCode("banana") = 2 9
Tại sao lại dùng bảng băm (hash tables)?
Key Value
. . .
141
142 robin robin info
143 sparrow sparrow info
144 hawk hawk info
145 seagull seagull info
146
Bảng băm là một mảng lưu giá trị. Thông thường người ta sử dụng cặp khóa/giá trị trong bảng (cid:132) Keyđể tìm một vị trí
trong mảng
147 bluejay bluejay info
(cid:132) Value: chứa thông tin thực sự ta muốn lưu
9-Apr-06
Nguyễn Văn Toàn - CTDL 2
5
148 owl owl info
Cách lựa chọn hàm băm
Làm thế nào để có thể chọn được hàm băm? Một cách tổng quát, chúng ta không thể chọn được (cid:47) (cid:132) Trong một số trường hợp đặc biệt, khi chúng ta hiểu rõ các giá trị trong bảng, chúng ta có thể tính toán được hàm băm một cách tương đối hiệu quả.
Cách đánh giá hàm băm? (cid:132) Một hàm băm được đánh giá là tốt khi nó cho chúng ta
biết chính xác vị trí cần tìm (cid:206) giảm đụng độ
(cid:132) Phân bố đều các giá trị trên bảng băm
9-Apr-06
Nguyễn Văn Toàn - CTDL 2
6
Ví dụ về hàm băm không hiệu quả
kiwi
0
1
2
Giả sử hàm băm cung cấp cho chúng ta các giá trị sau: (cid:132) hash("apple") = 5
banana watermelon
3
4
5
6
7
8
hash("watermelon") = 3 hash("grapes") = 8 hash("cantaloupe") = 7 hash("kiwi") = 0 hash("strawberry") = 9 hash("mango") = 6 hash("banana") = 2 hash("honeydew") = 6
apple mango cantaloupe grapes strawberry
• “Điều gì đã xảy ra”?
9-Apr-06
Nguyễn Văn Toàn - CTDL 2
7
9
Đụng độ (Collisions)
Khi xảy ra hiện tượng hai gía trị băm có cùng một vị trí trên mảng thì ta gọi đó làđụ ng độ, collision.
f(x1)= f(x2) = i (x1 <> x2)
Giải quyết vấn đề đụng độ theo cơ chế
Queue (“first come, first served”) — giá trị đầu tiên được băm sẽ được cấp phát vị trí trước. Còn giá trị cần băm thứ hai cấp phát vị trí
nào?
9-Apr-06
Nguyễn Văn Toàn - CTDL 2
8
Giải quyết đụng độ
Giải quyết như thế nào khi 2 phần tử được băm đều có cùng một vị trí trên bảng băm? f(x1) = f(x2) (cid:132) Giải pháp #1: Nếu một vị trí đã được cấp phát, ta bắt đầu từ đó để tìm một vị trí trống để cấp phát cho phần tử còn lại
(cid:138) Điều kiện để dừng tìm kiếm là khi gặp giá trị cần băm (đã
(cid:138) Tìm kiếm vòng
(cid:132) Giải pháp #2: Dùng hàm băm thứ hai
(cid:138) …và hàm băm thứ ba, thứ tư, thứ năm ...
(cid:132) Giải pháp #3: Dùng danh sách liên kết (DSLK) Việc thêm và tìm kiếm chỉ sử dụng cùng một giải pháp.
9-Apr-06
Nguyễn Văn Toàn - CTDL 2
9
có phần tử đó trong bảng) hay tìm được vị trí trống
Giải pháp 1: Ví dụ 1, Thêm
. . .
141
robin
142
sparrow
143
hawk
144
seagull
145
146
bluejay
147
owl
148
. . .
Giả sử chúng ta thêm từ seagull vào bảng băm Các bước: (cid:132) hashCode(seagull) = 143 (cid:132) table[143] đã có rồi (cid:47) (cid:132) table[143] != seagull (cid:132) table[144] đã có rồi (cid:47) (cid:132) table[144] != seagull (cid:132) table[145] rỗng Do đó, đặt seagull ở vị trí 145
9-Apr-06
Nguyễn Văn Toàn - CTDL 2
10
Giải pháp 1: Địa chỉ mở (Open-Addressing)
Có các phương pháp chính như sau: (cid:132) Thử tuyến tính (Linear Probing)
i0 = f(x1) ik = (i +k) % M (k = 1,…,M-1) (cid:132) Thử bậc hai (Quadratic Probing)
i0 = f(x1) ik = (i +k*k) % M (k = 1,…,M-1)
9-Apr-06
Nguyễn Văn Toàn - CTDL 2
11
Giải pháp 1: Ví dụ 2, Tìm kiếm
. . .
141
robin
142
sparrow
143
hawk
144
seagull
145
146
bluejay
147
owl
148
Giả sử chúng ta muốn tìm giá trị seagull trên bảng băm Các bước: (cid:132) hashCode(seagull) = 143 (cid:132) table[143] không rỗng (cid:132) table[143] != seagull (cid:132) table[144] không rỗng (cid:132) table[144] != seagull (cid:132) table[145] không rỗng (cid:132) table[145] == seagull ! Chúng ta tìm thấy giá trị seagull ở vị trí 145
9-Apr-06
Nguyễn Văn Toàn - CTDL 2
12
. . .
Giải pháp 1: Ví dụ 3, Tìm kiếm
. . .
141
robin
142
sparrow
143
hawk
144
seagull
145
146
bluejay
147
owl
148
Giả sử chúng ta tìm kiếm giá trị cow trong bảng băm Các bước: (cid:132) hashCode(cow) = 144 (cid:132) table[144] không rỗng (cid:132) table[144] != cow (cid:132) table[145] không rỗng (cid:132) table[145] != cow (cid:132) table[146] rỗng Nếu giá trị cow có trong bảng, chúng ta đã tìm ra nó Ngược lại, giá trị đó không ở trong bảng
9-Apr-06
Nguyễn Văn Toàn - CTDL 2
13
. . .
Giải pháp 1: Ví dụ 4, Thêm
. . .
141
robin
142
sparrow
143
hawk
144
seagull
145
146
bluejay
147
owl
148
. . .
Giả sử chúng ta thêm giá trị hawk vào bảng băm Các bước (cid:132) hashCode(hawk) = 143 (cid:132) table[143] không rỗng (cid:132) table[143] != hawk (cid:132) table[144] không rỗng (cid:132) table[144] == hawk hawk đã có trong bảng, do đó không cần thêm vào
9-Apr-06
Nguyễn Văn Toàn - CTDL 2
14
Giải pháp 1: Ví dụ 5, Thêm
Giả sử: (cid:132) Bạn muốn thêm cardinal vào
. . .
bảng băm
141
robin
(cid:132) hashCode(cardinal) = 147 (cid:132) Bảng băm có tất cả 148 phần
142
sparrow
tử
143
hawk
144
seagull
145
(cid:132) Vị trí 147 và 148 không rỗng Giải pháp: (cid:132) Xem bảng băm như một vòng
tròn; sau 148 trở lại 0
146
bluejay
147
owl
(cid:132) Do đó, cardinal sẽ được thêm vào vị trí 0 (hay 1, hay 2, hay ...)
9-Apr-06
Nguyễn Văn Toàn - CTDL 2
15
148
Giải pháp 1: Ví dụ 6, Xóa
. . .
cardinal
0 0
142 . . .
143 143
144 144
Giả sử: (cid:132) Bạn muốn xóa owl hashCode(bluejay) = 147 hashCode(owll) = 147 hashCode(cardinal) = 147 (cid:132) Bảng băm có tất cả 148 phần tử (cid:132) Nếu xóa vị trí 148 thì sẽ không tìm
sparrow sparrow hawk hawk seagull seagull
được cardinal
145 145
146 146
Giải pháp: (cid:132) Di chuyển cardinal về vị trí 148
147 147
bluejay bluejay owl owl
9-Apr-06
Nguyễn Văn Toàn - CTDL 2
16
148 148
Hiệu quả
Bảng băm thực sự có hiệu quả không ngờ Thậm chí bảng đã đầy khoảng 70%, số lần tìm kiếm khi đụng độ chỉ là 2 hay 3 lần Bằng các phân tích toán học phức tạp đã chứng minh rằng chi phí để thêm hay tìm kiếm trong bảng băm chỉ là O(1) Thâm chí khi bảng băm đã đầy, hiệu quả cũng vẫn cao
9-Apr-06
Nguyễn Văn Toàn - CTDL 2
17
Cài đặt
Qui ước (cid:132) hàmbămf(x) (cid:132) Kíchthướcbảngbăm: M (cid:132) Sốlượngphầntử thựcsựtrongbảngbăm: N Khởi tạo (cid:132) Cho bảng băm trống
N=0;
For (i=0;i
A[i].Key=-1
9-Apr-06
Nguyễn Văn Toàn - CTDL 2
18
Cài đặt (tt)
Thêm phần tử x vào bảng băm trả về vị trí đã thêm
vào
If (N == M-1)
// Thông báo đã đầy
Else
{ i = f(x);
}
While ((a[i].Key <> -1) && (a[i].Key<> x))
{
i=(i+1) % M;
if (a[i].Key <> x)
a[i].Key = x;
{
N++; }
return i;
}
9-Apr-06
Nguyễn Văn Toàn - CTDL 2
19
Cài đặt (tt)
Tìm phần tử x vào bảng băm trả về vị trí tìm
được
i = f(x);
While ((a[i].Key <> -1) &&
(a[i].Key<> x))
{
i=(i+1) % M;
return i;
}
if (a[i].Key == x)
else
return M;
9-Apr-06
Nguyễn Văn Toàn - CTDL 2
20
Cài đặt (tt)
Xóa
// Tìm
…
// Xóa
a[i].Key=-1;
N--;
While (a[i].Key <> -1 )
{
a[i].Key = a[(i-1) % M].Key-1;
i = (i-1) % M;
}
A[i].Key=-1
9-Apr-06
Nguyễn Văn Toàn - CTDL 2
21
Giải pháp #2: Băm lại (Rehashing)
Khi đụng độ xảy ra, một giải pháp khác là
rehash: tính toán một hàm băm khác
(cid:132) Do chúng ta có thể phải băm lại nhiều lần,
chúng ta cần một dãy hàm dễ tính toán
Ví dụ: Khi băm chuỗi (String), chúng ta có
thể lấy giá trị trả về của hàm băm trước
cộng vào chiều dài của chuỗi để tạo thành
chỉ số mới. f’(x)=f(x) + strlen(x)
Băm lại là một cách tiếp cận không thông
dụng.
9-Apr-06
Nguyễn Văn Toàn - CTDL 2
22
Giải pháp #3: Băm dùng DSLK
. . .
141
robin
142
sparrow
seagull
143
hawk
144
145
146
bluejay
147
owl
Các giải pháp trước
dùng bảng băm mở
(open hashing): tất
cả các mục được đưa
vào trong một mảng
bình thường
Giải pháp khác là làm
cho mỗi vị trí của
bảng là header của
một DSLK. DSLK này
sẽ chứa các giá trị
băm có cùng vị trí
148
9-Apr-06
Nguyễn Văn Toàn - CTDL 2
23
. . .
Giải pháp 3: Phương pháp nối kết
Có các phương pháp nối kết trực tiếp
(Direct Chaining, Seperate Chaining)
M << N
Có các phương pháp nối kết hợp nhất
(Coalesced Chaining)
M = N
9-Apr-06
Nguyễn Văn Toàn - CTDL 2
24
Hết – Cảm ơn
9-Apr-06
Nguyễn Văn Toàn - CTDL 2
25
A[i].Key=-1
9-Apr-06
Nguyễn Văn Toàn - CTDL 2
18
Cài đặt (tt)
Thêm phần tử x vào bảng băm trả về vị trí đã thêm vào
If (N == M-1)
// Thông báo đã đầy
Else { i = f(x);
}
While ((a[i].Key <> -1) && (a[i].Key<> x)) { i=(i+1) % M; if (a[i].Key <> x) a[i].Key = x; { N++; } return i;
}
9-Apr-06
Nguyễn Văn Toàn - CTDL 2
19
Cài đặt (tt)
Tìm phần tử x vào bảng băm trả về vị trí tìm
được i = f(x); While ((a[i].Key <> -1) &&
(a[i].Key<> x))
{
i=(i+1) % M;
return i;
} if (a[i].Key == x) else
return M;
9-Apr-06
Nguyễn Văn Toàn - CTDL 2
20
Cài đặt (tt)
Xóa // Tìm … // Xóa a[i].Key=-1; N--; While (a[i].Key <> -1 ) {
a[i].Key = a[(i-1) % M].Key-1; i = (i-1) % M;
} A[i].Key=-1
9-Apr-06
Nguyễn Văn Toàn - CTDL 2
21
Giải pháp #2: Băm lại (Rehashing)
Khi đụng độ xảy ra, một giải pháp khác là rehash: tính toán một hàm băm khác (cid:132) Do chúng ta có thể phải băm lại nhiều lần,
chúng ta cần một dãy hàm dễ tính toán
Ví dụ: Khi băm chuỗi (String), chúng ta có thể lấy giá trị trả về của hàm băm trước cộng vào chiều dài của chuỗi để tạo thành chỉ số mới. f’(x)=f(x) + strlen(x) Băm lại là một cách tiếp cận không thông dụng.
9-Apr-06
Nguyễn Văn Toàn - CTDL 2
22
Giải pháp #3: Băm dùng DSLK
. . .
141
robin
142
sparrow
seagull
143
hawk
144
145
146
bluejay
147
owl
Các giải pháp trước dùng bảng băm mở (open hashing): tất cả các mục được đưa vào trong một mảng bình thường Giải pháp khác là làm cho mỗi vị trí của bảng là header của một DSLK. DSLK này sẽ chứa các giá trị băm có cùng vị trí
148
9-Apr-06
Nguyễn Văn Toàn - CTDL 2
23
. . .
Giải pháp 3: Phương pháp nối kết
Có các phương pháp nối kết trực tiếp (Direct Chaining, Seperate Chaining)
M << N
Có các phương pháp nối kết hợp nhất (Coalesced Chaining)
M = N
9-Apr-06
Nguyễn Văn Toàn - CTDL 2
24
Hết – Cảm ơn
9-Apr-06
Nguyễn Văn Toàn - CTDL 2
25
![Đề thi cuối học kì 2 môn Cấu trúc dữ liệu và giải thuật [kèm đáp án/mới nhất]](https://cdn.tailieu.vn/images/document/thumbnail/2025/20251014/lakim0906/135x160/89711760416179.jpg)
![Tài liệu Nhập môn Học máy và Khai phá Dữ liệu [chuẩn nhất]](https://cdn.tailieu.vn/images/document/thumbnail/2025/20251001/kimphuong1001/135x160/531759303870.jpg)
