Hashfunktion i mod N (N Prim) Beispiel

Wissenschaft Informatik
#1

Moin zusammen!

Ich beschäftige mich derzeit mit Hashing und habe eine Anwendungsaufgabe samt Lösung gefunden, die ich allerdings nicht nachvollziehen kann

_Ein Programm benötige sehr schnell die Information, ob eine Zahl prim ist oder nicht. Daher sollen alle Primzahlen kleiner einem N in eine Hastabelle mit 100 Pläten (0 bis 10) eingefügt werden.
a)Alle Primzahlen

Lösung:
0 | 11
1 | 23
2 | 2
3 | 3
4 | 13
5 | 5
6 | 17
7 | 7
8 | 19
9 | 29
10 | leer

Mittlerer Aufwand zum Zugriff: 1,4

Wie man die rechte Seite kommt, ist mir unklar, eigentlich muss man doch rechnen
0 mod 11 = 0
1 mod 11 = 1
2 mod 11 = 2
3 mod 11 = 3
…
10 mod 11 = 1

Und wie kommt man so auf die Tabelle? Das s in (s mod 11) sind ja die Werte 0 bis 10. Irgendwie bin ich total auf dem verkehrten Weg, eine Kollision sehe ich nämlich nirgens. Kann mir jemand sagen, wie ich die rechte Seite der Tabelle errechne?

Viele Grüße
Disap_

#2

Lösung:
0 | 11
1 | 23
2 | 2
3 | 3
4 | 13
5 | 5
6 | 17
7 | 7
8 | 19
9 | 29
10 | leer

Mittlerer Aufwand zum Zugriff: 1,4

Hi,

sieht für mich so aus, als wenn in der Tabelle jeweils die Box ( Ergebnis der Berechnung s mod 11 ) der Anzahl der enthaltenen Elemente zugeordnet wird.

#3

Hallo,

Ich beschäftige mich derzeit mit Hashing und habe eine
Anwendungsaufgabe samt Lösung gefunden, die ich allerdings
nicht nachvollziehen kann

Ein Programm benötige sehr schnell die Information, ob
eine Zahl prim ist oder nicht. Daher sollen alle Primzahlen
kleiner einem N in eine Hastabelle mit 100 Pläten (0 bis 10)
eingefügt werden.
a)Alle Primzahlen

2, 3, 5, 7, 11, 13, 17, 19, 23
2, 3, 5, 7, 0, 2, 5, 8, 1

Jetzt trägst du sie nacheinander ein.

Wenn du die ersten fünf eingetragen hast, bist du hier:
0: 11
1:
2: 2
3: 3
4:
5: 5
6:
7: 7
8:
9:
10:

Die 13 müsstest du jetzt bei ‚2‘ eintragen, da steht aber schon was. Also schaust du bei ‚3‘, und da steht auch schon was. Also schaust du bei ‚4‘, da ist’s leer, also schreibst du die 13 bei der ‚4‘ rein.
Den Rest kann man ohne Kollisionen eintragen.

HTH,
Moritz