Exercise 5: Insertion into Linear Hashed File
Consider a file with b=4, c=3, d=2, sp=0, hash(x) as above
Insert tuples in alpha order with the following keys and hashes:
k | hash(k) |
|
k | hash(k) |
|
k | hash(k) |
|
k | hash(k) |
a | 10001 |
|
g | 00000 |
|
m | 11001 |
|
s | 01110 |
b | 11010 |
|
h | 00000 |
|
n | 01000 |
|
t | 10011 |
c | 01111 |
|
i | 10010 |
|
o | 00110 |
|
u | 00010 |
d | 01111 |
|
j | 10110 |
|
p | 11101 |
|
v | 11111 |
e | 01100 |
|
k | 00101 |
|
q | 00010 |
|
w | 10000 |
f | 00010 |
|
l | 00101 |
|
r | 00000 |
|
x | 00111 |
The hash values are the 5 lower-order bits from the full 32-bit hash.
|