Hashing with division remainder method

Question

I don't understand this exercise.

Hash the keys: (13,17,39,27,1,20,4,40,25,9,2,37) into a hash table of size 13 using the division-remainder method. a) find a suitable value for m. b) handle collisions using linked lists andvisualize theresult in a table like this

0→ 1→ 2→ 3→ 4→ 5→ 6→ ...

c) c) Handle collision with linear probing using the sequence s(j) = j and illustrate the development in a table by starting a new column for every insert (don’t forget to copy the cells already filled to the right) and by using downwards arrows to show the probing steps in case of collisions.

my attempt: a) if the table size is 13, m also have to be 13 because of remaining classes b) for example 0→ 39 -> 13 .... c) I have no idea

It would be really great if someone could help me solve it. :)

Answer 1

Let me give a brief overview of all topics which will be used here.

Hash-map is a data structure that uses a hash function to map identifying values, known as keys, to their associated values. It contains “key-value” pairs and allows retrieving value by key.

Like in array you can get any element using index, similarly you can get any value using a key in hash-map.

Basically something like this happens, you are given a key which is string here, then it is hashed and we put the value at that index in array.

In our example image, if you want what is value for "Billy", we again hash "Billy" we get 03. Now we just check the value at index 3 and that's the stored value for "Billy" (key)

In your case you have to hash integers not strings.

Now how to hash keys?

There can be several methods like you may sum ascii values of characters of string, or anything what you can think of.

let's say you have this array [100, 1, 3, 56, 80] and you have to store it in bucket of size 13. We directly can't use those array values as an index because we will need index 1 and index 100, it will make bucket have 100 size.

But if you take remainder of each array number with 13 then the remainder is always guaranteed to be from 0 to 13, thus you can use a 13 size bucket if you has keys using division method

[100, 1, 3, 56, 80] remainder with 13 -> [9, 1, 3, 4, 5] Thus you store 100's value at index 9, and so on.

Collision:

But what if in array we have a value 5 and 80, both after will give remainder 5. What to store at index 5 now?

In our example image,
Now let's say "SACHU" this also gives 03 after hashing now two keys gave same index so this is called collision which can be resolved using two methods

1. linkedlist like storage (store both values at same index using linkedlist, like this)

2. linear probing: in simple words 03 index is already occupied we try to find next empty index, like using the most simplest probing our in image example will be, 06 is empty so we store "SACHU" value at 06 not 03.
   (now this is a little hard so I highly suggest you to read hashing and collisions on internet)

Now, there is one method where we h(x) denotes the hash of an integer x. if number is x, first hash will be, h1 = h(x) If h1 index is not empty we again hash same index, h2 = h(h1) An so on, I am not sure, but I guess this is what is meant by s[j] = j method.

THESE ARE THE METHODS WHICH YOU HAVE TO USE IN YOUR PROBLEM.
I prefer you to give it a try first.

You can read more about it online and and comment if still you were not able to solve it.