Ch.22 - Introducing Hashing Test Bank

Chapter 22 - Introducing Hashing

True/False (22)

1. Most hash tables are not full.
2. Any function can be a hash function if it produces an integer that is suitable to be used as an array index.
3. A search key cannot be a primitive data type.
4. The default hash code returned by the method hashCode in Java’s base class Object is a good choice for hashing.
5. All classes inherit the method hashCode.
6. The Java Object method hashCode returns an integer.
7. Real-world data is uniformly distributed.
8. Duplicate hash codes create collisions.
9. If a class overrides the method equals, it should not override the method hashCode.
10. If the method equals considers two objects to be equal, then the method hashCode must return the same value for both objects.
11. Calling the method hashCode more than once on an object that has not been altered should return the same value.
12. Calling the method hashCode during different program executions will not affect the value returned.
13. The size of a hash table should always be an odd number.
14. Using a hash table size that is a prime number distributes values through the index range better than if the size is an even number.
15. Linear probing can examine every location in a hash table.
16. You will never encounter a full table when linear probing is used.
17. In open addressing with linear probing, a successful search for an entry that corresponds to a given search key could potentially follow a different probe sequence used to add the entry to the hash table.
18. Linear probing is apt to cause secondary clustering.
19. Quadratic probing is apt to cause secondary clustering.
20. Secondary clustering increases search time.
21. Separate chaining requires less memory than opening addressing.
22. Separate chaining is an efficient way to resolve collisions.

Short Answer (7)

1. Explain the two steps that typical hash functions perform.
2. Assume you are using a hash function that takes strings and sums the Unicode values of each letter to create a hash code. Give an example of two strings that produce the same hash code.
3. Assume the following hash function. Multiply the Unicode value of each character by a factor, g, based on the character’s position within the string. The hash code is the sum of these products.
   u₀g^n-1 + u₀g^n-2 + … + u_n-2g + u_n-1
   The Unicode value for uppercase ‘A’ = 65. Calculate the hash code for “ACE” with g = 7.
4. Assume the following hash function. Multiply the Unicode value of each character by a factor, g, based on the character’s position within the string. The hash code is the sum of these products.
   u₀g^n-1 + u₀g^n-2 + … + u_n-2g + u_n-1
   The Unicode value for uppercase ‘A’ = 65. Calculate the hash code for “FACE” with g = 7.
5. Assume you have a hash table length of 53. Given the value 216, what index will the entry map to?
6. Assume you have a hash table length of 29. Given the value 371, what index will the entry map to?
7. In open addressing with linear probing, explain why the remove method should not place null in the hash table.

Multiple Choice (28) WARNING: CORRECT ANSWERS ARE IN THE SAME POSITION AND TAGGED WITH . YOU SHOULD RANDOMIZE THE LOCATION OF THE CORRECT ANSWERS IN YOUR EXAM.

1. The technique for determining an array index using only a search key and not searching is called
   1. hashing
   2. direct indexing
   3. search key indexing
   4. stealth searching
2. When you use a search key to directly access an array without searching, the array is called a(n)
   1. hash table
   2. search array
   3. search table
   4. direct access array
3. A(n) _____ takes a search key and produces the integer index of an element in a hash table.
   1. hash function
   2. search function
   3. transformation function
   4. black box
4. A(n) _____ maps each search key into a different integer that is suitable as an index to the hash table.
   1. perfect hash function
   2. search key index
   3. hash index
   4. black box
5. A hash function converts a search key into an integer called a(n)
   1. hash code
   2. key code
   3. search index
   4. ideal number
6. When two search keys map to the same index, it is called a(n)
   1. collision
   2. duplicate mapping
   3. duplicate index
   4. index error
7. Typical hash functions are not perfect because
   1. they allow more than one hash key to map to the same index
   2. they allow collisions
   3. both a & b
   4. none of the above
8. A good hash function should
   1. minimize collisions
   2. be fast to compute
   3. distribute entries uniformly throughout the table
   4. all of the above
9. To reduce the chance of a collision in a hash table
   1. distribute entries uniformly throughout the table
   2. use a Poisson distribution
   3. use a random number generator
   4. all of the above
10. A search key can be
    1. a primitive data type
    2. an instance of a class
    3. both a & b
    4. none of the above
11. The Java Object method hashCode returns
    1. an integer
    2. an Object
    3. a search key
    4. none of the above
12. The Java Object method hashCode returns a value based on
    1. the memory address of the object used to invoke it
    2. a random number generator
    3. the memory address of the hash table
    4. the size of the hash table
13. Duplicate hash code
    1. create collisions
    2. are necessary for a perfect hash table
    3. destroy the hash table
    4. all of the above
14. If a search key’s data type is _____ you can use the key itself as the hash code.
    1. int
    2. float
    3. double
    4. String
15. If a search key is an instance of _____ , it can be cast to an int to get a hash code.
    1. byte
    2. short
    3. char
    4. all of the above
16. Dividing a long search key into pieces and combining them through addition or a bit-wise boolean operation is called
    1. folding
    2. combining
    3. optimizing
    4. hashing
17. We want to distribute hash codes throughout the index range
    1. 0 through n-1
    2. 0 through n
    3. 1 through n-1
    4. 1 through n
18. The recommended size of a hash table is a(n)
    1. prime number greater than 2
    2. Fibonacci number
    3. number that is a power of 2
    4. all of the above
19. Finding an unused location in the hash table is called
    1. open addressing
    2. hash searching
    3. both a & b
    4. none of the above
20. Resolving a collision in a hash table by examining consecutive locations in the table to find the next available one, beginning at the original hash index, is called
    1. linear probing
    2. open hashing
    3. hash walking
    4. collision resolution
21. In open addressing with linear probing, what happens if the search key is not in the table?
    1. it depends on the implementation of the remove method
    2. the search probe sequence encounters a null location
    3. the search probe encounters an occupied marker
    4. it throws an exception
22. In open addressing with linear probing, we must consider how to encode
    1. occupied positions
    2. empty positions
    3. available positions
    4. all of the above
23. In open addressing, collisions that are resolved with linear probing cause groups of occupied consecutive locations in the hash table called
    1. clusters
    2. bundle
    3. collection
    4. hash knot
24. In open addressing with linear probing, the increment is
    1. 1
    2. 2
    3. based on a secondary hash function
    4. j2
25. Using a second hash function to compute increments for probe increments is called
    1. double hashing
    2. probe counting
    3. sequence hashing
    4. function hashing
26. Given a hash function h(key) = key modulo 11, what index does the key 47 hash to?
    1. 3
    2. 5
    3. 7
    4. 1
27. When each location of a hash table can represent more than one value, that location is called a(n)
    1. bucket
    2. open slot
    3. overloaded index
    4. linked slot
28. Resolving collisions by using buckets that are linked chains is called
    1. separate chaining
    2. bucket chaining
    3. list resolution
    4. joint chaining