TCS Papers: Sample Questions 372 - 372 of 502

Examrace Placement Series prepares you for the toughest placement exams to top companies.

Question number: 372

» Basic CS » Data Structures

Essay Question▾

Describe in Detail

Classify the hashing functions based on the various methods by which the key value is found.

Explanation

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

  • 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