1. Briefly describe what hash tables and keys are. 2. T/F Two collision resoluti
ID: 3547127 • Letter: 1
Question
1. Briefly describe what hash tables and keys are.
2. T/F Two collision resolution techniques are open addressing and chaining.
3. Write an example of the function that gives the address of an item in a hash table.
4. Which of the following is true about linear probing:
a. The array is circular.
b. A random number generator is used to find the next available slot
c. If a collision occurs, the next step is to search the array sequentially for the next available slot.
d. It causes primary clustering.
5. Short Answer: Why are collisions unavoidable in hashing?
6. Multiple Choice: Hash tables are stored in
a. an array
b. a vector
c. a class
d. an integer
7. Short Answer: Why are hash functions necessary when organizing hash tables?
8. When creating a hash table what types of data structures can be pointed to by the table?
a. Hash Table
b. Linked List
c. Vector
d. Deque
e. All of the above
9. The hash table has a Big O notation of O(_____).
10. While traversing a hash table with linked lists the Big O notation for the worst case scenario is O(____).
Explanation / Answer
2. True
3. h(key) = key % n
4. A random number generator is used to find the next available slot
5 Collisions are practically unavoidable when hashing a random subset of a large set of possible keys. Therefore, most hash table implementations have some collision resolution strategy to handle such events. The performance of most collision resolution methods does not depend directly on the number n of stored entries, but depends strongly on the table's load factor, the ratio n/s between n and the size s of its bucket array. With a good hash function, the average lookup cost is nearly constant as the load factor increases from 0 up to 0.7 or so. Beyond that point, the probability of collisions and the cost of handling them increase. On the other hand, as the load factor approaches zero, the size of the hash table increases with little improvement in the search cost, and memory is wasted.
6. array
7.A good hash function is essential for good hash table performance. A poor choice of hash function is likely to lead to clustering, in which probability of keys mapping to the same hash bucket (i.e. a collision) is significantly greater than would be expected from a random function. Nonzero probability of collisions is inevitable in any hash implementation, but usually the number of operations to resolve collisions scales linearly with the number of keys mapping to the same bucket, so excess collisions will degrade
8. linked lists
9. to extract all the entries O(N) and sort them O(NlogN) whereas you can traverse a binary search tree in natural order in O(N).
10.O(n)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.