) Discuss the square and extract n-bits method for calculating hash addresses in
ID: 673545 • Letter: #
Question
) Discuss the square and extract n-bits method for calculating hash addresses in detail. Your discussion should include but not be limited all restrictions associated with the table size, selecting the bits for the key, limitations imposed by differed data types (e.g., character, numeric, etcetera), utilizing keys whose size exceeds the number of bits in an integer. ) Discuss the square and extract n-bits method for calculating hash addresses in detail. Your discussion should include but not be limited all restrictions associated with the table size, selecting the bits for the key, limitations imposed by differed data types (e.g., character, numeric, etcetera), utilizing keys whose size exceeds the number of bits in an integer. ) Discuss the square and extract n-bits method for calculating hash addresses in detail. Your discussion should include but not be limited all restrictions associated with the table size, selecting the bits for the key, limitations imposed by differed data types (e.g., character, numeric, etcetera), utilizing keys whose size exceeds the number of bits in an integer.Explanation / Answer
Hi
Introduction to Hashing Hashing is the application of a function to the key value that results in mapping the range of possible key values into a smaller range of relative addresses.
Choosing a hash function The two principal criteria in selecting a hash function are that it should be easy and quick to compute, and that it should achieve aneven distribution of the keys that actually occur across the range of indices. If we know in advance exactly what keys will occur, then it is possible to construct hash functions that will be very efficient, but generally we do not know in advance what keys will occur. Therefore, the usual way is for the hash function to take the key, chop it up, mix the pieces together in various ways, and thereby obtain an index that will be uniformally distributed over the range of indices.
Hashing Functions Several kinds of uniform hashing function are in use.
9452 * 9452 = 89340304 = 3403
As a variation on the midsqaure method, we can select a portion of the key, such as the middle three digits, and then use them rather than the whole key. This allows the method to be used when the key is too large to square. 379452: 379 * 379 = 143641 = 364
121267: 121 * 121 = 014641 = 464
a. Fold Shift Key: 123456789
123
456
789
---
1368 ( 1 is discarded)
b. Fold Boundary Key:
123456789
321 (digit reversed)
456
987 (digit reversed)
---
1764 ( 1 is discarded)
379452 = 394
121267 = 112
Answer is reasonably short.
Thanks
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.