Extendible hashing (1)

2

00

01

10

11

B = 4

h(k) = d_last_binary_digits(k modulo 8)

k ? {4, 5, 7, 10, 13, 15, 16, 19, 32} ? at least 3 buckets

d = 2 : 00, 01, 11, 10, 01, 11, 00, 11, 00

four “x0” ? 1 bucket (d=1)

five “x1” ? 2 buckets (d=2)

directory

buckets

2

2

depth

7

15

5

13

19

[Fagin, R.

et al.

1979]

Diapositive précédente

Diapositive suivante

Revenir à la première diapositive

Afficher la version graphique