Lesson test: Hash tables

Sign in

Libre University uses your GitHub account. Signing in is only needed to sit a final test, so the score is kept on your profile.

Hash tables

1.[2p]
Why is a direct-address table unusable for ten thousand records keyed by a nine-digit identifier?

It costs memory proportional to the universe of keys, a billion slots, rather than to the number stored

Correct

The keys would collide too often

The answer is: It costs memory proportional to the universe of keys, a billion slots, rather than to the number stored

Nine-digit numbers cannot be used as array indices

The answer is: It costs memory proportional to the universe of keys, a billion slots, rather than to the number stored

It would need to be resized on every insertion

The answer is: It costs memory proportional to the universe of keys, a billion slots, rather than to the number stored

2.[2p]
A sufficiently well designed hash function can avoid collisions entirely when the key universe is larger than the table.

True

The answer is: False

False

Correct

3.[3p]
About how many random keys go into a table of 1,000,000 slots before a collision is more likely than not? Use $1.177 \sqrt{m}$ .

CorrectNot quite: 1177

4.[2p]
A chained hash table has 500 slots and holds 900 keys. What is its load factor?

CorrectNot quite: 1.8

5.[3p]
Under linear probing at load factor 0.75, an unsuccessful search costs about $\frac{1}{2} (1 + 1 / (1 - α)^{2})$ probes. How many is that?

CorrectNot quite: 8.5

6.[3p]
Which of these are true of open addressing compared with separate chaining?

Select all that apply

Its cost rises far more steeply as the load factor approaches 1

Correct

Its load factor can never exceed 1

Correct

Deleting a record requires a tombstone rather than simply emptying the slot

Correct

It stores an extra pointer for every record

The answer is: Its cost rises far more steeply as the load factor approaches 1, Its load factor can never exceed 1, Deleting a record requires a tombstone rather than simply emptying the slot

7.[2p]
Why must every key be reinserted when a hash table is resized?

A key's slot is computed from the table size, so no old position is still correct

Correct

The old table is freed before the new one is allocated

The answer is: A key's slot is computed from the table size, so no old position is still correct

The hash function is reseeded on every resize

The answer is: A key's slot is computed from the table size, so no old position is still correct

Resizing changes the load factor threshold

The answer is: A key's slot is computed from the table size, so no old position is still correct

8.[3p]
What does a hash-flooding attack exploit?

Keys chosen to collide turn the table into a list, so $n$ insertions cost $Θ (n^{2})$

Correct

A weakness in the birthday bound

The answer is: Keys chosen to collide turn the table into a list, so $n$ insertions cost $\Theta(n^2)$

The cost of rehashing when the table doubles

The answer is: Keys chosen to collide turn the table into a list, so $n$ insertions cost $\Theta(n^2)$

The tombstones left behind by deletion

The answer is: Keys chosen to collide turn the table into a list, so $n$ insertions cost $\Theta(n^2)$

9.[3p]
Match each query to whether a hash table can answer it efficiently.

Is this exact key present
What is the smallest key
List all keys in order
Insert a new key

no, every slot must be scanned
no, hashing destroys order
yes, expected constant time
yes, amortised constant time

Show the answer

Is this exact key present: yes, expected constant time What is the smallest key: no, every slot must be scanned List all keys in order: no, hashing destroys order Insert a new key: yes, amortised constant time

1.[2p] Why is a direct-address table unusable for ten thousand records keyed by a nine-digit identifier?

2.[2p] A sufficiently well designed hash function can avoid collisions entirely when the key universe is larger than the table.

3.[3p] About how many random keys go into a table of 1,000,000 slots before a collision is more likely than not? Use 1.177m.

4.[2p] A chained hash table has 500 slots and holds 900 keys. What is its load factor?

5.[3p] Under linear probing at load factor 0.75, an unsuccessful search costs about 12(1+1/(1-α)2) probes. How many is that?

6.[3p] Which of these are true of open addressing compared with separate chaining?

7.[2p] Why must every key be reinserted when a hash table is resized?

8.[3p] What does a hash-flooding attack exploit?

9.[3p] Match each query to whether a hash table can answer it efficiently.

1.[2p]
Why is a direct-address table unusable for ten thousand records keyed by a nine-digit identifier?

2.[2p]
A sufficiently well designed hash function can avoid collisions entirely when the key universe is larger than the table.

3.[3p]
About how many random keys go into a table of 1,000,000 slots before a collision is more likely than not? Use $1.177 \sqrt{m}$ .

4.[2p]
A chained hash table has 500 slots and holds 900 keys. What is its load factor?

5.[3p]
Under linear probing at load factor 0.75, an unsuccessful search costs about $\frac{1}{2} (1 + 1 / (1 - α)^{2})$ probes. How many is that?

6.[3p]
Which of these are true of open addressing compared with separate chaining?

7.[2p]
Why must every key be reinserted when a hash table is resized?

8.[3p]
What does a hash-flooding attack exploit?

9.[3p]
Match each query to whether a hash table can answer it efficiently.