How many words will be used for the hash table itself

Assignment Help Computer Engineering

Reference no: EM131847310

Problem

Suppose that each entry in a hash table occupies s words of storage (exclusive of the pointer member needed if chaining is used), where we take one word as the amount of space needed for a pointer. Also suppose that there are n occupied entries in the hash table, and the hash table has a total of t possible positions (t is the same as hash_size), including occupied and empty positions.

(a) If open addressing is used, determine how many words of storage will be required for the hash table. (b) If chaining is used, then each node will require s + 1 words, including the pointer member. How many words will be used altogether for the n nodes?

(c) If chaining is used, how many words will be used for the hash table itself? (Recall that with chaining the hash table itself contains only pointers requiring one word each.)

(d) Add your answers to the two previous parts to find the total storage requirement for chaining.

(e) If s is small (that is, the entries have a small size), then open addressing requires less total memory for a given load factor λ = n/t , but for large s (large entries), chaining requires less space altogether. Find the break-even value for s , at which both methods use the same total storage. Your answer will be a formula for s that depends on the load factor λ, but it should not involve the numbers t or n directly.

(f) Evaluate and graph the results of your formula for values of λ ranging from 0.05 to 0.95.

Reference no: EM131847310

Questions Cloud

What is the probability that at least two people in the room : What is the probability that at least two people in the room will have that same random birthday?

Study about the horizontal integration : In this chapter, we studied horizontal integration and the build-borrow-or-buy framework. One industry currently consolidating is furniture manufacturing.

How does acid rebound occur : How does acid rebound occur? What are the therapeutic actions of sulcrafate and misoprostol?

What are the therapeutic actions for drugs : What are the therapeutic actions for drugs used to decrease acid content( H2 receptor antagonists, antacids, proton pump inhibitors and prostaglandins)?

How many words will be used for the hash table itself : If chaining is used, how many words will be used for the hash table itself? How many words will be used altogether for the n nodes?

Theories about the pathophysiologic process : Question: What are the current theories about the pathophysiologic process for peptic ulcer disease?

What is the state of michigan structure system : What is the state of Michigan's structure system? Include a description of what courts exist and their relationships to each other

What are the two primary lines of security defense : Explain the differences between the types of security offered by the banks in the case. Which bank would you open an account with and why?

Adjustment in pain medication : QUESTION 1: Which adjustment in pain medication may be needed for an elderly person with elevated liver enzymes due to anticonvulsant therapy?

User Account

All Pages