Chapter 5 (Hashing)

Question 1

Table size should be a ____ ____

Answer 1

Prime number

Question 2

In perfect hashing, what is the worst case access time?

Answer 2

O(1)

Question 3

What is a drawback of the chaining method?

Answer 3

Allocating new nodes

Question 4

What is the formula for the expected number of probes in a linear probing strategy?

Answer 4

1/(1-lambda)

Question 5

What is the worst case running time for a find in hopscotch hashing?

Answer 5

O(1)

Question 6

T/F Java hash tables require the “equals” and “hashCode” methods to be defined on the hashed objects

Answer 6

T

Question 7

How many hash tables does cuckoo hashing use?

Answer 7

2

Question 8

How does separate chaining handle collisions?

Answer 8

Each index contains a list. Each item that collides is contained in this list

Question 9

What is primary clustering?

Answer 9

A large list of values clustered around the same cell

Question 10

What is the primary drawback of linear probing?

Answer 10

Primary clustering

Question 11

What is it called when two keys map to the same location?

Answer 11

Collision

Question 12

What is lambda?

Answer 12

The ratio of the number of elements to the table size

Question 13

What is the job of the hash function?

Answer 13

Mapping

Question 14

What is the average running time for inserts, deletes, and finds for hashing?

Answer 14

O(1)

Question 15

T/F Hashing supports operations like findMin and findMax

Answer 15

F

Question 16

What is the worst case access time in cuckoo hashing?

Answer 16

O(1)

Question 17

What is rehashing?

Answer 17

When a table is 50% full, create a new table twice the size of the old one and rehash everything to the new table

Question 18

How can duplicates be handled with separate chaining?

Answer 18

Having a counter on each element

Question 19

What does Horner’s rule give us?

Answer 19

A simple way to compute a polynomial using multiplication and addition

Question 20

In perfect hashing, what is the space required?

Answer 20

O(n)

Question 21

What is the strategy of quadratic probing?

Answer 21

First look 1 away, then 4, 9, 16, 25, etc.

Question 22

If we want to hash 100 elements into a table size of 100, what would lambda be?

Answer 22

1.0

Question 23

T/F Open addressing requires a large table

Answer 23

T

Question 24

How can you keep the likelihood of a cycle in cuckoo hashing very small?

Answer 24

Keep the load < 0.5

Question 25

In double hashing, what is done to resolve a collision?

Answer 25

A second hash function

Question 26

What is the scheme of perfect hashing?

Answer 26

Each secondary table can be constructed several times until it is collision free

Question 27

What problem does quadratic probing introduce?

Answer 27

Secondary clustering

Question 28

What is a downside of double hashing?

Answer 28

Likely to be slower than quadratic probing

Question 29

T/F The hashing function should be a simple algorithm that distributes the keys evenly among the cells

Answer 29

T

Question 30

What are three common collision resolution strategies?

Answer 30

Linear probing Quadratic probing Double hashing

Question 31

What is done if sliding in hopscotch hashing is unsuccessful?

Answer 31

Rehash

Question 32

How does open addressing resolve collisions?

Answer 32

By storing a colliding element in an alternate cell

Question 33

In universal hashing, what is the probability of a collision if a hash function is chosen at random?

Answer 33

1/M

Question 34

T/F Each secondary table can be constructed several times until it is collision free

Answer 34

T

Question 35

In linear probing, cells are tried ____ until an empty cell is found

Answer 35

Sequentially

Question 36

With a lambda of 1.0, what should the average list be?

Answer 36

1 node

Question 37

What does quadratic probing help prevent?

Answer 37

Primary clustering

Question 38

In open addressing, how is the alternate cell chosen?

Answer 38

By another function called the collision resolution strategy

Question 39

For ints, how does a hash function convert keys to indices?

Answer 39

key % tableSize