c++: The success of a hash-table implementation of the ADT table is related to t

Question

c++:

The success of a hash-table implementation of the ADT table is related to the choice of a good hash function. A good hash function is one that is easy to compute and will evenly distribute the possible data. Comment on the appropriateness of the following hash functions. What patterns would hash to the same location. The hash table has size 10000 entries long. The search keys are integers in the range 0 through 9999. The hash function is h(key) = (key * random) truncated to an integer where random represents a sophisticated random-number generator that returns a real value between 0 and 1. The hash table has size 10000 entries long (HASH_TABLE_SIZE is 10000). The search keys are integers in the range 0 through 9999. The hash function is given by the following C++ function: int hashIndex(int x) {for int i=1; i

Explanation / Answer

a)

The hash function here is implemented as h(key)=key*random

where random can be any real value between 0 and 1 and the key can take any value from 0 to 9999.

For example consider a case where key = 2000 and random =0.5 the hash (key) value = 2000*0.5 = 1000.

So for this particular data the value will be stored at 1000th location in the hash table or 999th location as the location range for this hash function will be from 0 to 9999.

Now let us consider key=2001 and random=0.5 value will be = 2001*0.5 = 1000.5 which will be truncated to 1000. Now for different key 2000,2001 they are mapping to same hash location which is not good for a hash table.

b)

The above c++ function is wrong. we are using i in for loop and in hash function variable x is used. Considering variable x is similar to i hash will be calculated on square value of the number mod 10,000.

so this will give us values in range of 0 to 9999 always because of mod function usage.

Now consider x=2 it will be 2*2 mod 10000 = 4 so it will be stored at location 4.

The problem in this hash function will come with higher powers of numbers which exceeds the hash table size thereby causing collision.

for example let us take two values 200 and 300.

for 200 hash key will be 200*200 % 10000 = 40,000 % 10,000 = 0

for 300 hash key value will be 300*300 % 10000 = 90,000 % 10,000 = 0

again they both are pointing to same location in hash table.

Collision will be frequent for most of the numbers whose square exceeds hash table size.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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