32. Give the density of the two structures described in Exercise 31. 31.Objects

Question

32. Give the density of the two structures described in Exercise 31.

31.Objects to be stored in a data structure each have 1000 bytes of information, which includes the key field comprised of 5 digits. A maximum of 1500 nodes will be in the structure at one time. How many elements will be in the primary storage area array, if the nodes are stored using a:

a) Direct hashing function?

1500 elements will be in the primary storage area array

b) Division hashing function?

In the primary storage area array will be less than 1500 elements

Explanation / Answer

(a).

Direct hashing function:

using direct hashing if the keys are unique we can store 1000 bytes of each object in hash table using direct hashing.

there are some constraints for the key in direct hashing function.

the keys must be unique, and

In direct hashing the elements are stored without any algorithm rather it directly stored in the empty field.

the range of the key must be severely bounded.

Otherwise,

If the keys are not unique, then we can simply construct a set of m lists and store the heads of these lists in the direct address table. The time to find an element matching an input key will still be O (1).

Since there are 1500 node can be stored in the structure at a time.

Therefore, total 1500 elements will be in the primary storage rea array.

b)

Division hashing function:

In division hashing the keys are stored in the structure using the modules of the keys which is divided by the total size of the structure.

The formula to find the location of the key in the structure as below:

Location = key modulus table_size + 1

Where keys may be the duplicate.

Therefore, there may be the collision in the table.

Thus, the location = (key modulus 1500) +1;

Therefore, the elements in the primary storage will be less than the 1500.

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

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