Tài liệu BẢNG BĂM (Hashing Table) pptx

1

BẢNG BĂM

(Hashing Table) (Hashing Table)

Chương 5

2

Kh

ái ni

ệ

m

z Gi

ả

s

ử ta có 100 s

ố nguyên có giá

t

rị b

ất k

ỳ

n

ằm trong kho

ảng t

ừ

0 . . 999

z

N

ếu s

ử

d

ụng m

ảng

a

g

ồm 1000 ph

ần t

ử để lưu tr

ữ các s

ố nguyên này sao cho a[i]

=

i

thì

s

ố lần tìm ki

ếm s

ố nguyên b

ất k

ỳ trong

100 s

ố này là 1 l

ầ

n

z Tuy nhiên, ch

ỉ có 1/10

b

ộ nh

ớ được s

ử

d

ụng, d

ẫn đến lãng phí

b

ộ nh

ớ

z Phép bi

ến đổi khóa là phương pháp tham

kh

ảo tr

ực ti

ếp các ph

ần t

ử trong m

ột b

ảng

(

b

ảng b

ă

m) thông qua vi

ệc bi

ến đổi s

ố

h

ọc

trên nh

ững khoá để có được địa ch

ỉ tương

ứng c

ủa nh

ững ph

ần tử ở trong b

ảng