1) The array of a non-perfect hashed data structure contains 769 elements. What

Question

1) The array of a non-perfect hashed data structure contains 769 elements. What element does the key 351,956 map into if no preprocessing is performed, and the division hashing function is used? _____________________________________

2) 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)

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

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

2c) Give the loading factor when the structure is full and perfect hashing is used ______________

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

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

Explanation / Answer

1)

The key 351,956 the element having remainder that matches or mapped to the given key.

If collision occurs then chaining and linear probing is done due to same index values in array.

Simple Hash Function is used which is

2)

a)

Perfect Hashing means no collision occurs.

Size of storage=4532*60 bytes

=>271920 bytes

=>265.55 KB

b)

In Non perfect hashing size of storage area increases or more than that of perfect hashing because of extra data structure is required in case of collision.

size >=265.55 KB

c)

Loading Factor=no of entries / no of buckets

which is 1 in case of perfect hashing.

Loading Factor=1 in perfect Hashing

d) Density is uniform in perfect hashing.

e)

Density is non-uniform in non-perfect hashing.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

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