Week 06 Lecture (31)

31

Exercise 3: Insertion into Static Hashed File

Consider a file with b=4, c=3, d=2, h(x) = bits(d,hash(x))

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.