2

I want to hash the following key "LOWELL" using a simple hash function that used 3 steps :

Step 1: transform the key into a number.

LOWELL = | L | O | W | E | L | L | | | | | | |
ASCII code: 76 79 87 69 76 76 32 32 32 32 32 32

my question here why it added more 6 empty positions with fixed ASCII code 32

Step 2: fold and add (chop off pieces of the number and add them together) 

7679|8769|7676|3232|3232|3232|
7679+8769+7676+3232+3232+3232 = 33,820

Step 3: take the mod by a prime number

33,820 mod 19937 = 13,883

Another question here for why dividing by prime numbers i found this answer : Dividing by a number is good when there are sequences of consecutive numbers. If there are many dierent sequences of consecutive numbers, dividing by a number that has many small factors may result in lots of collisions. A prime number is a better choice. but i didn't get it

Step 4: divide by the size of the address space (preferably a prime number). 13,883 mod 101 = 46

finally why it divided the address space ?!

You can find detailed steps here (Slide 350) Many Thanks in advance for helping

Ahmed Gamal
  • 1,666
  • 1
  • 17
  • 25

1 Answers1

1

Since your address space contains only 101 slots, you cannot put your record in a position whose address exceeds this limit.

So you take the reminder of division of the output from the hash function (13,883 in your case) by the address space, to make sure that the location of the record falls in the allowed address space.

So h(s) % address_space will always give allowed position within your address space.

Regarding your first question, why do we use a prime number in hashing, this thread will help you: Why use a prime number in hashCode?

Community
  • 1
  • 1
Mostafa Abdullah
  • 11
  • 5