Give a True or False Collision resolution is the main contributor to the cost of

Question

Give a True or False Collision resolution is the main contributor to the cost of hashing. In separate chaining, X has no maximum value. Any function can be a hash function if it produces an integer that is suitable to be used as an array index. Most hash tables are not full. Real-world data is uniformly distributed. 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. In a sequential search of a sorted array, you must examine the entire array if an item is not present in the array. A binary search is usually slower than a sequential search on sorted array of data. Sorting data typically takes more time than scorching it. What is X for a hash table with 500 locations and 200 entries that uses open addressing? Explain why resizing a hash table that has 751 entries to double the size, or 1502, is a bad idea. Explain why a binary search implementation of a sorted chain is impractical.

Explanation / Answer

8.

a)True

b) In Separate chaining also, lambda has a maximum possible value of 1,so false.

c)False ,For a function to be a hash function,it doesn't necessarily needs to provide integer.

d) FALSE, it depends on the Size of hash table & effectiveness in handling collisions.

e) False, it can be assumed to be uniformly distributed for ease of calculations.

f)True as table size = prime number: helps in good distribution

g)True

h)True

i)True

10.

the array must be increased in size and all the element rehashed into the new buckets using an appropriate hash function when the load factor exceeds some constant factor max. Because resizing is not visible to the client, it is a benign side effect. Each resizing operation takes O(n) time where n is the size of the hash table being resized. Therefore the O(1) performance of the hash table operations no longer holds in the case of add: its worst-case performance is O(n).

11. chain contained 1000 nodes? In general, you need to traverse the chain, beginning at the first

node, until you reach the middle node. How will you know when you get there? If you know the

length of the chain, you can divide the length in half and count nodes as you traverse. The

details are not as important as a realization that it takes a bit of work to access the middle node.

After looking at the entry in the middle node, you probably need to ignore half of the chain and

search the other half. Do not change the chain when ignoring part of it. Remember that you want to

search the chain, not destroy it. Once you know which half to search, you must find its middle

node, again by traversing the chain. It should be clear to you that a binary search of a linked chain

of nodes would be challenging to implement and less efficient than a sequential search. That is why

binary search of a chain of linked nodes is impractical.

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

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