Question

ANSWER THE FOLLOWING QUESTIONS:

Problem 2 Assume that you want to design a hashtable to store data of employees in a company. The ID of each worker is his primary phone mumber in the form of 10 digit number (Area code-three digits carrier-4 digits id). Knowing the following constraints (information). a) Employees can differ only on the three low significant digits, the fifth and the sixth digits; they all have the same digits for the fourth, seventh, eighth, ninth and tenth digit. b) No more than three (3) employees can have all the five digits the same (digit 1, 2, 3, 5, and 6). c) At most 20% of the employees will have a duplicate Question: What would be the ideal size of the table, the best hash function you would use in designing your hash table? How would you deal with duplicate indexes in the case you use a fixed array with no chaining?

Answer 1

IF YOU HAVE ANY DOUBTS COMMENT BELOW I WILL BE TTHERE TO HELP YOU..ALL THE BEST..

Since only the three low significant digits, the fifth and the sixth digit differ and the other digits in the employee Id remain the same, we only need to take into consideration the digits that differ.

So while calculating the hash value, we would only be using the digits that can/will change and ignore the rest.

Now since only 5 digits can change, the max size of the table required to store all possible employees would be 100000.

The naive way would be to just have an array with one entry for each possible unique ID. But the problem is that you only have maybe a few thousand employees at most, so most of your array is empty and you're wasting a lot of space.

The idea is that, instead of storing an ID's details at employee[id], you store it at employee[h(id)] for some function h which is fairly easy to compute.

The best hash function for the problem would be Knuth multiplicative hash where the key is multiplied by the golden ratio of 2^32 (2654435761) to produce a hash result.

Now if you have a fixed size array with no chaining, you could opt for open addressing inside the array. In Open Addressing, all elements are stored in the hash table itself. However, while using open addressing some care has to be given to avoid clustering. Open addressing also requires more computation than chaining.

I HOPE YOU UNDERSTAND..

PLS RATE THUMBS UP..ITS HELPS ME ALOT..

THANK YOU...!!