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