Hash with division remainder method

Erste Frage Aufrufe: 509     Aktiv: 09.12.2022 um 04:35

0

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) (1 point) Give 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→ ...

gefragt

Punkte: 10

 
Kommentar schreiben
1 Antwort
0

what is m here? If it is the hash table size, try to google "choose hash tab size", you will find good answers. Basically you that m is much smaller than your highest possible number. And you want to minimize collisions, by leaving enough space, such that the number of values you hash are distributed and not end up at the same value.

hashing with division reminder work like this: Since the hash table is if size 13 you will need to divide each number by 13 and use the remainder of the devision to decide where it gets hashed to.

eg

13 % 13 = 0
17 % 13 = 4
39 % 13 = 0

where % is the modulo operator, which gives you the remainder (der Rest) of a division.

now you know where the values get hashed to.

b)

now 13 abd 39 have the SAME hash value. This is called a collision.

They will both be in the hash table at value 0. Which looks like this:

0: 13, 39
1:
2:
3:
. .
.
12:

Now a usual hash table only stores one thing, So writing:

0: 13,39

is not correct, instead what would happen is:

0: 13

then

0: 39

but we have to store 2 values, because of the collision. We need to do something about that, to not lose the furst value, because it gets overwritten.

And our solution is to use a linked list. Basically instead of storing a single value, we store a linked list. This allows us to store multiple values in the list. While we still only store one thing (the list) in the hash table.

To visualise a linked list, often these arrows are use:

0: 13 -> 39

Diese Antwort melden
geantwortet

Punkte: 10

 

Kommentar schreiben