In a linear probing hash table, all the keys must be rehashed when resizing the

Question

In a linear probing hash table, all the keys must be rehashed when resizing the array.

Question 2

Give the array that results after inserting the following sequence of 10 keys into an initially empty linear probing hash table.

Assume that the size of the hash table is 10 and that it does not grow or shrink.

Give you answer as a sequence of capital letters separated by spaces.

Question 3

Insert the following sequence of 12 keys, in order, into a separate chaining hash table with 3 chains:

Consider a search miss for the key F, whose hash value is 1. What is the sequence of keys that get compared with F? Give your answer as a sequence of capital letters separated by spaces.

Question 4

Suppose that the following keys are inserted into an initially empty linear probing hash table but not necessarily in the order given:

Assuming that the size of the hash table is 7 and that it does not grow or shrink, which one or more of the following could be the contents of the resulting array?

N L Z A W C H

C Z H N W A L

L N H W A C Z

L N A H W C Z

H N L W Z A C

Explanation / Answer

Solution :

1)

True

When array size is increased, the keys has to be put in correct places.

For example, consider array with size = 10

key = 17 will be at index 7.

but when we resize the array to length 20, 17 will be at index 17.

Hence all keys has to be rehashed when resizing array.

2)

- array is empty initially : x x x x x x x x x x

- P(0) : insert at index 0.

array : P x x x x x x x x x

- W(7) : insert at index 7.

array : P x x x x x x W x x

- L(6) : insert at index 6.

array : P x x x x x L W x x

- Y(9) : insert at index 9.

array : P x x x x x L W x Y

- H(2) : insert at index 2.

array : P x H x x x L W x Y

- Q(1) : insert at index 1.

array : P Q H x x x L W x Y

- C(7) : insert at index 7. But it is not empty, so insert at 8.

array : P Q H x x x L W C Y

- O(9) : insert at index 9. But it is not empty, so insert at next empty index, which is 3.

array : P Q H O x x L W C Y

- E(9) : insert at index 9. But it is not empty, so insert at next empty index, which is 4.

array : P Q H O E x L W C Y

- U(5) : insert at index 5.

array : P Q H O E U L W C Y

Answer : P Q H O E U L W C Y

3)

chain | keys

-----------------------------

0 : H Z K W T

1 : I L

2 : S D Y J P

Answer : keys that gets compared with F : I L

4) answer : option LNAHWCZ

when input sequence is A,H,N,W,C,Z,L the resulting array would be LNAHWCZ.

if you have any doubts then you can ask in comment section. If you find the solution helpful then you can upvote the answer. Thank you.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.