Answer TRUE or FALSE.

For the string hash functions, the size of the hash table limits the length of the string that can be hashed.

• True
• False

The simple mod hash function makes use of:

• The low order digits or bits in the key
• The high order digits or bits in the key
• The middle digits or bits of the key
• All of the digits or bits in the key

The binning hash function makes use of:

• The high order digits or bits in the key
• The low order digits or bits in the key
• The middle digits or bits of the key
• All of the digits or bits in the key

The mid-squares method hash function makes use of:

• All of the digits or bits of the key
• The high order digits or bits of the key
• The middle digits or bits of the key
• The low order digits or bits of the key

For the simple string hash function that sums the ASCII values for the letters, does the order of the letters in the string affect the result?

• Yes
• No
• Usually

Which is the best definition for collision in a hash table?

• Two records with different keys have the same hash value
• Two records are identical except for their keys
• Two records have the same key
• Two records have the same key and the same hash value
• Two records with the same key have different hash values

(Recall that $m$ refers to the size of a hash table.) A hash function must:

• Return a value between 0 and $m-1$
• Return a value between 1 and $m$
• Return the position of a free slot in the table
• Return the hash value for the key
• Return values in equal distribution throughout the table

If you double the size of a hash table, can you keep using the same hash function?

• Yes, but you will not hash to the new slots
• Yes, it works fine since the table size does not matter to the hash function
• No, the hash function would now generate illegal values

Answer TRUE or FALSE.

A company wants to use a system where they randomly assign each customer a 9-digit ID (so there are 1 billion possible ID numbers). Of course, there is a chance that two customers will be assigned the same ID. But the company figures that risk is OK if the odds are small enough. They expect to assign IDs to 1000 customers. The chance of a collision is therefore one in a million.

• True
• False

Answer TRUE or FALSE.

A company wants to use a system where they randomly assign each customer a 9-digit ID (so there are 1 billion possible ID numbers). Of course, there is a chance that two customers will be assigned the same ID. But the company figures that risk is OK if the odds are only one in a million. They expect to assign IDs to 1000 customers. But the chance of collision is much higher than one in a million.

• True
• False

Answer TRUE or FALSE.

Hashing has the advantage that it can answer range queries or questions like what is the largest key in the database.

• True
• False

Which of the following is true of open addressing?

• All records are stored directly within the hash table
• Records are stored on a list associated with a slot in the hash table

Answer TRUE or FALSE.

Separate chaining works well for disk-based hash systems.

• True
• False

Answer TRUE or FALSE.

Open addressing works well for disk-based hash systems.

• True
• False

What is the expected worst-case cost for a search on a properly tuned hash system that stores $n$ records?

• $O(1)$
• $O(n^2)$
• $O(n)$
• $O(\log n)$

What is a disadvantage of linear probing?

• It can lead to allocating a lot of extra memory
• You tend to get primary clustering
• You tend to get secondary clustering
• The algorithm is difficult to program

Which of the following is true of separate chaining?

• Records are stored on a list associated with a slot in the hash table
• All records are stored directly within the hash table
• The algorithm running time is determined by probes of different slots until an empty one is found

A separate chaining table has an array size of $n$. What is the maximum number of records that can be stored in the table?

• There is no maximum
• $n/2$
• $n$
• $n-1$
• $n-2$

Which is the best definition for a probe sequence?

• The order in which collision resolution will visit the slots of the hash table
• It is another name for a hash function
• The order in which the hash function will visit the slots of the hash table
• It is another name for collision resolution

What is one disadvantage of quadratic probing as a collision resolution method?

• Insertions can fail even if there are empty slots in the hash table
• You have to check whether or not a node needs to be split
• Memory usage increases with each insertion
• Primary clustering can degrade performance

Hashing is good for which queries?

• Exact match queries
• Range queries
• Finding the maximum key value
• All of these
• None of these

The special value used to signal a position in a hash table from which a record has been deleted is called a:

• Tombstone
• Flag
• Sentinal
• Gravestone

Answer TRUE or FALSE.

When deleting a record from a hash table, we can just do a normal search and then remove the record from the slot where we find it.

• True
• False

Answer TRUE or FALSE.

A problem with using tombstones is that they take up slots in the table that cannot be reused, so that over time the effective table size shrinks.

• True
• False

Answer TRUE or FALSE.

A problem with using tombstones is that they take up slots in the table, so they slightly increase the search and insert time.

• True
• False

Which is true about deletion from a hash table using tombstones?

• It causes a slight increase in the average time to insert and search
• It causes a large decrease in the average time to insert and search
• It causes a slight decrease in the average time to insert and search
• It has no effect on the average time to insert and search
• It causes a slight increase in the average time to insert and search
• It causes a large increase in the average time to insert and search