Hi I have a few questions on hashed data structures in Java and there are a few

Question

Hi I have a few questions on hashed data structures in Java and there are a few answers on chegg already but none of them seem to be right.

1)   A hashed data structure will store a maximum of 4,352 nodes, the keys are numeric in the range is 0 to 999,999, and the node width is 60 bytes. (show your work)

   a) Give the size of the primary storage area array if perfect hashing is used _________________

   b) Give the size of the primary storage area array if non-perfect hashing is used _____________

c) Give the density when the structure is full and perfect hashing is used ___________________

d) Give the density when the structure is full and non-perfect hashing is used _______________

Thank you any help is appreacted

Explanation / Answer

Solution:

a)

Perfect hashing promises no collision to occur.

so,

storage size=4532*60 bytes

= 271920 bytes= 271920/1024 KB

= 265.55 KB

b)

b) Give the size of the primary storage area array if non-perfect hashing is used

In this case, there is a possibility of collision

so the size here can be

so, the size will be 1000000*60 = 60 MB

c)

The density of a hash function is defined as,

the quotient between the total number of elements stored in the table and the total size of the array implementing the hash table.

The density here

will be 4352/(265.65 KB)

d)

THe density will be

4352/(60MB)

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects