True or False? Explain your answers. a. When a hash function is used to determin

Question

True or False? Explain your answers. a. When a hash function is used to determine the placement of elements array, the order in which the elements are added does not affect the array. b. When hashing is used, increasing the size of the array always reduces the number of collisions. c. If we use buckets in a hashing scheme, we do not have to worry about collision resolution. d. If we use chaining in a hashing scheme, we do not have to worry about collision resolution. e. The goal of a successful hashing scheme is an 0(1) search.

Explanation / Answer

a. When a hash function is used to determine the placement of elements in an array, the order in which the elements are added does not affect the resulting array. False. This is false because, multiple values may be inserted with the same hash value. And the first element that is inserted with the same hash value will be inserted in the actual index in the array, where as the the other elements with the same hash value will be inserted in positions depending on the hashing technique we are using.

b. When hashing is used, increasing the size of the array always reduces the number of collisions. True. When the table size is increased, obviously the number of collisions will be decreased, as there are more number of empty spaces.

c. If we use buckets in a hashing scheme, we do dont have to worry about collision resolution. False. In bucket hashing the actual table is divided into multiple slots. The element will be inserted in the slot to which the hash function evaluates to. The element will be inserted in the first empty position in the slot. If the position is filled, it will keep on searching for the next empty position within that bucket. And if the bucket is full/overflowing, now we have to insert elements in some other place like overflow bucket.

d. If we use chaining in a hashing scheme, we do not have to worry about collision resolution. True. This is called open hashing. In open hashing, the values are not actually stored in the table, instead the table contains a pointer to a set of values, at which the actual values will be stored as chains/linked lists. Therefore, we will not have the problem of collision in this case.

e. The goal of a successful hashing scheme is an O(1) search. True. The goal of hashing is to find the element in the list by simply applying the hash function. And ofcourse, the best case complexity of hashing scheme search technique is O(1).

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.