TCS Placement: Sample Questions 304 - 304 of 502
Get unlimited access to the best preparation resource for competitive exams : get questions, notes, tests, video lectures and more- for all subjects of your exam.
Question 304
Describe in Detail Essay▾
Classify the hashing functions based on the various methods by which the key value is found.
EditExplanation
There are 7 hashing functions based on how key value is found.
- Direct Method
- Key is the address without algorithmic manipulation
- Data structure contains element for possible key
- Example problems
- To analyze total monthly sales by days of month
- For each sale we need date and amount of sale
- To calculate sales record for month, we need day of month as key for array and add sales amount to accumulator
- Daily Sales [Sale Day] = Daily Sales [Sale Day] + Sale Amount
- Subtraction Method
- Direct and subtraction hash functions guarantee search effort without no collisions
- In one to one hashing method only one key hashes to each address
- Example
- Company has 100 employees, employee number starts from 1001 to 1100
- Hashing function subtracts 1000 from key to determine address
- Modulo-Division Method
- Divides the key by array size and use remainder for address
- Algorithm works with any list size, but a prime number produces fewer collisions
- Address = key MODULO list Size
- Digit-Extraction Method
- Digits are extracted from key and used as address
- Example:
- Six-digit employee number is used to hash three digit address (000 - 999)
- For example, select first, third, and fourth digits as key
- 379452 - 394
- 121267 - 112
- 378845 - 388
- 160252 - 102
- 045128 - 051
- Mid-square Method
- Key is squared and the address is selected from the middle of the squared number
- Example
- Given a key of 9452, midsquare address calculation is shown using four digit address (0000 - 9999)
- 94522 = 89340304: address is 3403
- Select first three digits and then use midsquare method
- 379452: 3792 = 143641 - 364
- 121267: 1212 = 014641 - 464
- 378845: 3782 = 142884 - 288
- 160252: 1602 = 025600 - 560
- 045128: 0452 = 002025 - 202
- Folding Method
- Two folding methods
- Fold shift
- Fold boundary
- Fold shift key value is divided into parts whose size matches size of required address
- Left and right parts are shifted and added with middle part
- In fold boundary, left and right numbers are folded on a fixed boundary between them and the center number
- Two folding methods
- Pseudo-random Method
- Key is used as seed in pseudorandom number generator and the random number is scaled into possible address range using modulo-division.
- A common random number generator is y = ax + c
- Example
- Assume a = 17, c = 7, x = 121267, Prime number = 307
- y = ( (17 ⚹ 121267) + 7) modulo 307
- y = (2061539 + 7) modulo 307
- y = 2061546 modulo 307
- y = 41