Hi Leute!
Ich hab eine Frage zum Hashing.
Wie Hashing im Allgemeinen funktioniert hab ich soweit verstanden. Wenn
mir nun eine Hashfunktion h(s) gegeben ist, berechnet diese ja den
Zielort oder den neuen Speicherort.
Sagen wir mal die Hashfunktion lautet so: h(s) = s mod 9. Nun sind mir
mehrere Werte s gegeben (5,28,19,15,20,33,12,17,10) die ich in eine
Hashtabelle mit 9 Positionen einfügen soll. Ich setze also nun die Werte
der Reihe nach in die Hashfunktion ein und schreibe den Wert an die
errechnete Stelle.
So nun kann es ja sein, dass ein Wert auf eine Position soll die aber
schon belegt ist. Nun gibt es aber doch 3 verschiedene Arten zur
Kollisionsauflösung: lineares sondieren, quadratisches sondieren und
doppeltes Hashing.
Wie funktioniert das genau? In Wikipedia hab ich für alle 3 Arten eine
Formel gefunden. Wann muss ich diese Formel anwenden? Vor oder nach der
eigentlich Hashfunktion? Was berechnet sie mir dann? Was mache ich mit
dem berechneten Werte?
Hans Wurst schrieb:> So nun kann es ja sein, dass ein Wert auf eine Position soll die aber> schon belegt ist. Nun gibt es aber doch 3 verschiedene Arten zur> Kollisionsauflösung: lineares sondieren, quadratisches sondieren und> doppeltes Hashing.>> Wie funktioniert das genau? In Wikipedia hab ich für alle 3 Arten eine> Formel gefunden.
Hast du dir auch die jeweiligen Beschreibungen dazu durchgelesen? Die
sind eigentlich recht anschaulich. Vergiss die Formeln, die beschreiben
nur mathematisch, was da passiert.
> Wann muss ich diese Formel anwenden? Vor oder nach der> eigentlich Hashfunktion?
Gar nicht.
Die Formeln sind nur mathematischer Asudruck dessen, was dein
Algorithmus mit dem Index macht um den nächsten Index zu erhalten, an
dem er probiert den Zahlenwert abzuspeichern.
lineares sondieren bedeutet beispielsweise einfach nur:
an der Stelle, an der du den Wert speichern willst, ist schon einer
eingetragen. Gut, dann benutze einfach das nächste Arrayelement. Was, da
ist auch schon was - dann eben das nächste. usw. usw. Solange bis du ein
freies Fach für den Wert gefunden hast.
Ich hab jetzt bezüglich dem linearen sondieren nochmal nachgeschaut:
Wenn mir in einer Aufgabe eine übliche Hashfunktion gegeben ist, dann
muss ich diese in die Hashfunktion für lineares probieren einsetzen.
Sieht dann wohl so aus:
Aufgabe:
Gegeben sei die übliche Hashfunktion h'(k)=k mod m. Bestimmen sie nun
die Hashfunktion für lineares probieren!
Die Hashfunktion für lines sondieren lautet nach Wikipedia:
h(k,i)=(h'(k) + i) mod m. Hier muss ich dann wohl das h'(k) durch die
gegebene übliche Hasfunktion k mod m ersetzen, oder? Das sieht dann so
aus: h(k,i)=((k mod m) + i) mod m
Was mich nun noch etwas verwirrt ist der Formelbuchstabe m. m muss doch
in der üblichen Hashfunktion gegeben sein, oder? Ist dann das m in der
Hashfunktion für lineares probieren automatisch gleich dem m aus der
gegebenen Hashfunktion?
Wenn mir jemand diese Frage beantworten könnte wär das super! Danke!
Edit: Gerade die Formeln sind interessant weil in meiner Aufgabe kein
Algorithmus zu überlegen ist, sondern ich das mit Papier lösen soll und
zu muss was passiert und da brauch ich die Formel!
In deinem Beispiel
> h(s) = s mod 9.> mehrere Werte s gegeben (5,28,19,15,20,33,12,17,10)
Kollissionsstrategie: linear
Das ist deine Hashtabelle
0 1 2 3 4 5 6 7 8
+----+----+----+----+----+----+----+----+----+
| | | | | | | | | |
+----+----+----+----+----+----+----+----+----+
Am Anfang sind alle Fächer leer. Gut
Einzufügen ist: 5
5 mod 9 ergibt 5. Also wird die 5 beim Index 5 eingetragen
0 1 2 3 4 5 6 7 8
+----+----+----+----+----+----+----+----+----+
| | | | | | 5 | | | |
+----+----+----+----+----+----+----+----+----+
Einzufügen ist: 28
28 mod 9 ergibt 1. Also werden die 28 eingetragen
0 1 2 3 4 5 6 7 8
+----+----+----+----+----+----+----+----+----+
| | 28 | | | | 5 | | | |
+----+----+----+----+----+----+----+----+----+
Nächster Wert: 19
19 mod 9 ergibt 1. Also wird die 19 beim Index 1 ....
Huch das geht nicht. Da liegt schon die 28 drinnen. Das nächste freie
Feld ist das mit dem Index 2. Also kommt die 19 dort rein
0 1 2 3 4 5 6 7 8
+----+----+----+----+----+----+----+----+----+
| | 28 | 19 | | | 5 | | | |
+----+----+----+----+----+----+----+----+----+
Weiter gehts mit 15
15 mod 9 ergibt 6. ALso Eintrag bei 6
0 1 2 3 4 5 6 7 8
+----+----+----+----+----+----+----+----+----+
| | 28 | 19 | | | 5 | 15 | | |
+----+----+----+----+----+----+----+----+----+
Nächster: 20
20 mod 9 ergibt 2. Also beim Feld mit dem Index 2
huch, geht nicht. Da liegt schon was. Also. nächstes freies Feld, das
mit dem Index 3
0 1 2 3 4 5 6 7 8
+----+----+----+----+----+----+----+----+----+
| | 28 | 19 | 20 | | 5 | 15 | | |
+----+----+----+----+----+----+----+----+----+
Nächster: 33
33 mod 9 ergibt 6. 6 geht nicht, da ist schon die 15. Also: nächstes
freies Feld: 7
0 1 2 3 4 5 6 7 8
+----+----+----+----+----+----+----+----+----+
| | 28 | 19 | 20 | | 5 | 15 | 33 | |
+----+----+----+----+----+----+----+----+----+
Weiter im Text: 12
12 mod 9 macht 3. 3 geht nicht, das nächste freie Feld ist das mit dem
Index 4
0 1 2 3 4 5 6 7 8
+----+----+----+----+----+----+----+----+----+
| | 28 | 19 | 20 | 12 | 5 | 15 | 33 | |
+----+----+----+----+----+----+----+----+----+
Der nächste zum rasieren: 17
17 mod 9 ergibt 8
0 1 2 3 4 5 6 7 8
+----+----+----+----+----+----+----+----+----+
| | 28 | 19 | 20 | 12 | 5 | 15 | 33 | 17 |
+----+----+----+----+----+----+----+----+----+
Bleibt noch: 10
10 mod 9 ergibt 1
1 geht nicht, 2 geht nicht, 3 geht nicht, 4 geht nicht, ..., 8 geht
nicht, 0 ... ist frei. Also dort rein
0 1 2 3 4 5 6 7 8
+----+----+----+----+----+----+----+----+----+
| 10 | 28 | 19 | 20 | 12 | 5 | 15 | 33 | 17 |
+----+----+----+----+----+----+----+----+----+
linear bedeutet also einfach: von dem Feld welches du mit der
Hash-Funktion ausgerechnet hast und such solange einfach weiter, bis du
auf ein freies Feld stösst.
Hans Wurst schrieb:> Die Hashfunktion für lines sondieren lautet nach Wikipedia:> h(k,i)=(h'(k) + i) mod m. Hier muss ich dann wohl das h'(k) durch die> gegebene übliche Hasfunktion k mod m ersetzen, oder? Das sieht dann so> aus: h(k,i)=((k mod m) + i) mod m>> Was mich nun noch etwas verwirrt ist der Formelbuchstabe m.
m ist ganz offensichtlich die Größe der Tabelle.
(wenn im Zusammenhang mit Arrays eine Modulo Funktion auftaucht, dann
kannst du deinen Allerwertesten darauf verwetten, dass dies deshalb da
drinn vorkommt, damit man das Array quasi zu einem Ring schliesst. Der
Nachfolger des letzten Array-Elements ist das erste Array Element)
Ist dein Array also 9 Elemente groß (m gleich 9) dann hat das Feld
welches 6 Elemente hinter dem Feld mit dem Index 7 liegt den Index (7 +
6) mod 9 oder ausgerechnet 13 mod 9 bzw. 4.
Probiers aus
0 1 2 3 4 5 6 7 8
+----+----+----+----+----+----+----+----+----+
| | | | | | | | | |
+----+----+----+----+----+----+----+----+----+
Finger auf das Feld Nummer 7. Dann 6 Felder weiterzählen, wobei du beim
ersten wieder anfängst, wenn du am Ende angekommen bist. Du landest beim
Feld mit der Nummer 4. Genau wie berechnet.
Hans Wurst schrieb:> Edit: Gerade die Formeln sind interessant weil in meiner Aufgabe kein> Algorithmus zu überlegen ist, sondern ich das mit Papier lösen soll und> zu muss was passiert und da brauch ich die Formel!
Wenn du den jeweiligen Algorithmus verstanden hast, verstehst du auch
wie die Formeln zu Stande kommen. Das i in deinen Formeln ist nichts
anderes als der i-te Versuch das Element in der Hash-Tabelle
unterzubringen.
Ich denke das mit dem linearen probieren hab ich soweit verstanden. Nun
gibt's ja noch dieses quadratische probieren.
Das ist meine Hashtabelle:
0 1 2 3 4 5 6 7 8
+----+----+----+----+----+----+----+----+----+
| | | | | | | | | |
+----+----+----+----+----+----+----+----+----+
Am Anfang sind alle Fächer leer. Gut
Einzufügen ist: 5
5 mod 9 ergibt 5. Also wird die 5 beim Index -25(?) bzw. +25(?)
eingetragen?
0 1 2 3 4 5 6 7 8
+----+----+----+----+----+----+----+----+----+
| | | | | | 5 | | | |
+----+----+----+----+----+----+----+----+----+
Einzufügen ist: 28
28 mod 9 ergibt 1. Also wird die 28 bei -1(?) bzw. +1(?) eingetragen?
0 1 2 3 4 5 6 7 8
+----+----+----+----+----+----+----+----+----+
| | 28 | | | | 5 | | | |
+----+----+----+----+----+----+----+----+----+
Woher weiß ich nun ob ich den jeweiligen negativen oder positiven Wert
nehmen muss?
Hans Wurst schrieb:> Ok. Soweit verstanden. Aber wo ziehst du die 6 in deiner letzten Antwort> her? Wo kommt die her?
welche 6?
Meinst du die hier
> Ist dein Array also 9 Elemente groß (m gleich 9) dann hat das> Feld welches 6 Elemente hinter dem Feld mit dem Index 7 liegt den> Index (7 + 6) mod 9 oder ausgerechnet 13 mod 9 bzw. 4.
Die hab ich erfunden, damit wir konkrete Zahlen haben und du mit den
Fingern am Bildschirm Fächer zählen kannst. Du kannst auch jede andere
Zahl zwischen 0 und 8 (inklusive) nehmen. Es geht ja nur darum, welche
praktische Begründung hinter dem mod steckt.
Hans Wurst schrieb:> 28 mod 9 ergibt 1. Also wird die 28 bei -1(?) bzw. +1(?) eingetragen?
Seit wann ist denn das Ergebnis eines mod negativ?
mod ist der Rest bei einer Division!
Eine Mutter hat 12 Torten und 5 Kinder.
Wieviele Torten bleiben der Mutter, wenn jedes Kind gleich viele Torten
bekommt?
Es gibt auch noch Kollisionsauflösung durch verkettete Listen, das ist
meistens zu bevorzugen. Sondieren ist ekelhaft sobald man Elemente auch
wieder löschen muss. Wenn die Hashtabelle eine gewisse Auslastung (75%
und mehr erreicht) ist es gängig die Hashtabelle zu verdoppeln und zu
rehashen.
Hallo,
genau deshalb gibt es häufig neben Modulo auch noch Remainder-Funktionen
in verschiedenen Programmiersprachen. Einige sind 0-symmetrisch, andere
so, daß immer positive Reste entstehen.
Lies mal nach, wie das Runden funktioniert.....noch mehr Varianten je
nach Anwendung.
Gruß,
Michael
Hans Wurst schrieb:> Wenn ich inmeinen TR -5 mod 9 eingebe, bekomm -5/9 als Ergebnis.>> Das stimmt irgendwie alles nicht zusammen. aber genau deswegen frag ich> ja :-)
Tja. Dann musst du die Bedienungsanleitung deines Taschenrechners
befragen, wie man mit dem modulo rechnet.
Eines ist klar. Das Ergebnis kann nur eine ganze Zahl sein. -5/9 ist
aber keine ganze Zahl. Noch nicht mal, wenn ich das - ignoriere.
Hm, das ist natürlich interessant, aber ich möchte jetzt vorerst mal
wissen, wie das genau mit diesem quadratischen sondieren geht, weil ich
das anscheinend noch nicht verstanden habe. Wenn ich das kapiert habe,
kann ich mich über andere Strategien kümmern, weil's ja auch wirklich
ein interessantes Themengebiet ist!
Ich hab hier ja auch eine Aufgabe:
Gegeben sie die Hashfunktion h(s) = s mod 9. Zeigen sie quadratisches
sondieren mit den Parametern c1=1 und c2=3. Geben sie die Hashtabelle
mit der Größe m = 11 an, die nach Einfügen der Werte
10,22,31,4,15,28,17,88,59 entsteht.
Damit ich so eine Hastabelle angeben kann, muss ich die Position an
denen die Werte eingetragen werden sollen ja erst wieder mit dieser
ominösen Formel berechnen. Wie soll das denn sonst gehen?
Hans Wurst schrieb:> Hm, das ist natürlich interessant, aber ich möchte jetzt vorerst mal> wissen, wie das genau mit diesem quadratischen sondieren geht, weil ich> das anscheinend noch nicht verstanden habe.
Wenn eine Kollision besteht, dann wird versucht
im nächsten Feld hinter dem per Hash-Funktion errechneten
geht das auch nicht, dann im Feld 4 Felder hinter dem Ausgangsfeld
geht das auch nicht, dann im Feld 9 Felder hinter dem Ausgangsfeld
geht das auch nicht, dann im Feld 16 Felder hinter dem Ausgangsfeld
Warum?
Weil 1 quadrat 1 ist
2 zum quadrat 4 ist
3 zum quadrat 9 ist
4 zum quadrat 16 ist
etc.
Bzw. beim alternierenden dann eben
+1, -1, +4, -4, +9, -9, +16, -16, ....
ALso die Quadratzahlen, nur eben 2 mal und abwechselnd dazugezählt bzw.
weggezählt. Was wiederrum gleichwertig ist mit: einmal geht man mit dem
Finger vom ausgerechneten Feld nach rechts (und wieder an den Anfang
wenn man hinten ist) und das andere mal dann eben nach links (und ans
Ende wenn man am Anfang des Array angelangt ist).
> ominösen Formel berechnen. Wie soll das denn sonst gehen?
Indem du verstehst, wie sich die Formel in "wieviele Felder weiter"
umsetzen lässt. Bzw. umgekehrt wenn du verstanden hast, dass es nur
darum geht ein freies Feld hinter dem eigentlich angedachten (und der
Hash-Funktion entsprechenden) Feld zu finden, dann gibt es da eine
Beziehung, die sich als Formel ausdrücken lässt.
Wenn ich nun eine Hashtabelle mit Größe 10 hab und dort mit
quadratischen probieren eben diese auffüllen will, dann bekomm ich doch
bei 9 ein Problem, oder? 9^2=81! Ich hab aber keine 81...
Nochmal zur Formel:
Ich hab hier jetzt noch immer diese Aufgabe wie gerade oben:
Auf der Wikipedia hab ich die Formel für das quadratische probieren in
die ich ja die in der Aufgabe gegebene Hashfunktion einsetzen muss.
Aber: Wo soll ich nun mit den Parametern c1 und c2 hin? Weder meine
Hashfunktion an sich noch die Formel auf Wikipedia für das quadratische
(alternierende) sondieren bieten mir eine Möglichkeit die Parameter
einzusetzen!
Kannst du mir vielleicht mal das Beispiel kurz aufzeigen?
Hans Wurst schrieb:> Wenn ich nun eine Hashtabelle mit Größe 10 hab und dort mit> quadratischen probieren eben diese auffüllen will, dann bekomm ich doch> bei 9 ein Problem, oder? 9^2=81! Ich hab aber keine 81...
die 81 heißt, dass du von der aktuell berechneten position aus 81
stellen weiter läufst. Bei Größe 10 läuft man halt ein paar Runden
umsonst...
Hans Wurst schrieb:> Wenn ich nun eine Hashtabelle mit Größe 10 hab und dort mit> quadratischen probieren eben diese auffüllen will, dann bekomm ich doch> bei 9 ein Problem, oder? 9^2=81! Ich hab aber keine 81...
81 = 1 mod 10
Daher also auch
9^2 = 1 mod 10
Hans Wurst schrieb:> Wenn ich nun eine Hashtabelle mit Größe 10 hab und dort mit> quadratischen probieren eben diese auffüllen will, dann bekomm ich doch> bei 9 ein Problem, oder? 9^2=81! Ich hab aber keine 81...
Und?
Du kannst ja auch auf einer Uhr mit Sekundenzeiger den Zeiger um 657824
Sekunden weiterstellen und landest trotzdem wieder auf einer Zahl
zwischen 0 und 59. Wo ist das Problem?
PS: Der Sekundenzeiger einer Uhr ist eine konkrete 'Implementierung' der
Operation x mod 60
Bei einer analogen Uhr drehst du halt dein Zeiger wie ein Wilder im
Kreis, wenn du die 657824 Sekunden einzeln abzählst. Aber da du jetzt
weißt, dass diese Operation sich mittels
Neue_Sekunde = ( Aktuelle_Sekunde + Differenz ) mod 60
berechnen lässt, kannst du dir auch ganz einfach ausrechnen, wo der
Sekundenzeiger letzten Endes zum Stillstand kommen wird, wenn man ihn
von der aktuellen Stellung ausgehend um 657824 Sekunden weiterstellt.
Vielleicht nimmt dir dieses Beispiel ein wenig die Verwirrung, die du
scheinbar mit der mod-Operation verbindest.
> Aber: Wo soll ich nun mit den Parametern c1 und c2 hin?
mit denen kann ich auch nix anfangen. Vor allen Dingen, weil ich für 2
derartige Konstanten im ganzen Verfahren keinen Platz, keine
Verwendungsmöglichkeit sehe.
Aber: Diese Aufgabe fällt ja nicht vom heiteren Himmel. Da muss es ja
Unterlagen dazu geben, aus denen du die Aufgabe her hast. Was sagt denn
die zum Thema? Wie wird dort c1 und c2 in der theoretischen Abhandlung
verwendet?
Edit.
Was ich mir vorstellen könnte, ist die allgemeine Form eines
quadratsichen Polynoms. Die Kollisionsfunktion ist dann nicht einfach
nur durch x^2 charakterisiert, sondern durch c1*x^2 + c2*x + c3
Aber dazu würde man dann wieder 3 Konstanten benötigen.
Vielleicht ist es auch nur x^2 + c1*x + c2
Oder c1*x^2 + c2*x
Oder c1*x^2 + c2
Wie gesagt: Sieh dort nach, wo du die Aufgabe her hast. Da findet sich
sicher was.
Hm, die Unterlagen haben mir bisher dabei nicht weitergeholfen weil ich
das System von "einer gegebenen Hashfunktion einsetzen in die Formel für
die Kollisionsauflösung" nicht verstanden habe".
So steht es bei mir in den Unterlagen:
Es sei eine Hashfunktion gegeben: h':U -> {0,1,...,m-1}
lineares Probieren: h(s,i)=(h'(s)+i) mod m
quadratische Probieren: h(s,i)=(h'(s)+c1*i+c2*i^2) mod m
Das einzige was daraus doch noch nicht hervorgeht, ist, ob bei diesem
quadratischen Probieren nun auch negative Werte für die Positionen
vorkommen. Aber doch eigentlich nicht weil ja die modulo-Funktion dies
schon verhindert, oder?
Noch eine Frage: i ist ja der Laufindex. Beginnt dieser bei beiden
Probierarten bei 0 oder 1?
Jetzt hab ich hier mal eine konkrete Aufgabe:
Gegeben ist: s=49,22,6,52,76,33,34,13,29,11,83 mit m=11 und h'(s)=s mod
m sowie c1=0 und c2=1.
Aus diesen Angaben lassen sich dann diese Funktionen basteln:
lineares Probieren: h(s,i)=((s mod 11)+i) mod m
quadratisches Probieren: h(s,i) = ((s mod 11) + i^2) mod m
Nun berechne ich die Positionen für lineares Probieren:
h(49,0)=...=4
h(22,1)=...=3
h(6,2)=...=2
h(52,3)=...=7
h(76,4)=...=10
h(33,5)=...=8
h(34,6)=...=9
h(13,7)=...=8 (Fehler hier sitzt schon ein Wert also mach nun lineares
Probieren mit i=8 weiter, richtig?
h(13,8)=...=9 (ebenfalls Fehler!)
h(13,9)=...=10 (wieder Fehler!)
h(13,10)=...=0 (hier kann nun die 13 eingefügt werden)
So nun wäre der Schlüssel 29 an der Reihe zum Einfügen. Welches i wird
nun benutzt? Wird i auf 0 zurückgesetzt, auf die Stelle an der der erste
Fehler (also 7) war oder wird einfach weitergezählt, also i=11?
Hans Wurst schrieb:> Jetzt hab ich hier mal eine konkrete Aufgabe:>> Gegeben ist: s=49,22,6,52,76,33,34,13,29,11,83 mit m=11 und h'(s)=s mod> m sowie c1=0 und c2=1.>> Aus diesen Angaben lassen sich dann diese Funktionen basteln:>> lineares Probieren: h(s,i)=((s mod 11)+i) mod m> quadratisches Probieren: h(s,i) = ((s mod 11) + i^2) mod m>> Nun berechne ich die Positionen für lineares Probieren:>> h(49,0)=...=4
Wo kriegst du die 4 her?
49 mod 11 ergibt doch 5
Denn 4 mal 11 wären 44 und dann fehlen noch 5 auf 49
mod ergibt den REST bei einer ganzzahligen Division!
> h(22,1)=...=3
Wieso 1?
i ist die Nummer des Versuchs mit dem du probierst 22 in der Hashtabelle
unterzubringen. Und du startest natürlich erst mal mit Versuch Nummer 0
für die 22. Wenn das nicht klappt, dann kommt Versuch 1, wenn das auch
nicht klappt dann kommt Versuch 2, etc...
Ausserdem ergibt h(22,1) nicht 3
Sag mal, welche Schule machst du eigentlich?
Das ganze Hashing ist ziemlich simpel. Und wenn man den Vorgang
verstanden hat, dann müsste man eigentlich auch die Formeln verstehen,
weil sich in ihnen der ganze Vorgang wiederfindet. h(s,i) beschreibt
nichts anderes als den i-ten Versuch die Zahl s in der Hashtabelle
unterzubringen. Wenn der i-te Versuch klappt, ist alles gut. Wenn er
nicht klappt dann wird i eben um 1 erhöht und ein neuer Versuch startet.
Aber mit jeder Zahl s beginnt man erst mal mit Versuch 0, sie in der
Tabelle unterzubringen. Du machst da gerade eine enorme Wissenschaft
draus.
Was ich überhaupt nicht verstehe, dass ist das du mit der mod Funktion
so dermassen Schwierigkeiten hast. Das ist einfach nur der (positive)
Rest bei einer Division! Mehr ist das doch nicht. Bei deinen Pipifax
Zahlen, kann man das doch ganz einfach im Kopf ausrechnen.
Beispiel:
56 mod 11
welches ist das nächste Vielfache von 11, welches gerade noch kleiner
oder gleich 56 ist? Na das wären 55, denn 5 * 11 sind 55. Auf 56 fehlt
noch 1. Also ist das Ergebnis von 56 mod 11 gleich 1.
Beispiel:
49 mod 11
welches ist das nächste Vielfache von 11, welches gerade noch kleiner
oder gleich 49 ist? Das wären 44, denn 4 * 11 sind 44. 5 * 11 wäre schon
zu groß, denn 5 * 11 sind 55 und 55 ist größer als 49. Also 44. Von den
44 fehlen noch 5 auf 49. Ergo ist das Ergebnis von 49 mod 11 gleich 5,
weil 5 Rest bleiben wenn ich 49 durch 11 dividiere.
Kopfrechnen! Leg deinen Taschenrechner zur Seite, den brauchst du im
Zahlenraum 0 bis 100 nicht. Benutz lieber deinen Kopf. Da hast du (auch
auf lange Sicht) mehr davon als stumpfsinnig Zahlen in einen
Taschenrechner einzutippen und jedes Ergebnis davon unkritisch und
gedankenlos zu übernehmen. Ein gewisses Gefühl für Zahlen und
Größenordnungen zu haben, hat noch nie geschadet. Das kriegst du aber
mit Tipseln am Taschenrechner nicht. (und genau deswegen bin ich strikt
dagegen, dass in der Grundschule Taschenrechner und Computer im
Mathe-Unterricht benutzt werden! Das kleine EinmalEins muss jeder nach
der 3. Klasse Grundschule beherrschen. Dazu braucht man keinen
Tschenrechner). 22 mod 11 kann doch nicht 3 ergeben, wenn 22 schon ein
genaues Vielfaches von 11 ist. Selbst wenn du da noch 1 dazu oder
wegzählst, kann da nicht 3 rauskommen. Unglaublich, dass ich mit dir
jetzt den Stoff aus der 3-ten Klasse Grundschule(!) wiederholen muss!
Dort hat dich die Lehrerin gefragt: Wieviel ergibt 39 durch 4 und
wieviel bleibt Rest? Und die Kinder haben gerechnet: 39 durch 4 ergibt
9, denn 9 mal 4 macht 36; plus 3 macht 39. 39 durch 4 ergibt 9, Rest 3.
Und jetzt schreibst du das Ganze ein bischen mathematischer
39 / 4 = 9
39 mod 4 = 3
und du stehst da, wie der Ochs vorm Tor, wenn dir der Taschenrechner
nicht die Zahlen ausspuckt (aus welchen Gründen auch immer -
wahrscheinlich Bedienungsfehler)
> Hm, die Unterlagen haben mir bisher dabei nicht weitergeholfen
Versteh ich nicht.
Da ...
> quadratische Probieren: h(s,i)=(h'(s)+c1*i+c2*i^2) mod m
... stehst doch in den Unterlagen, wie c1 und c2 zu verwenden sind
c1 mal i + c2 mal i_zum_quadrat
Was brauchst du denn noch?
Deine Aufgabe gibt dir die Zahlenwerte für c1 und c2 und die setzt du
ein.
Dass ich hier die falschen Modulo-Werte ausgerechnet habe, war ich
selber Schuld selber, da ich nicht den Rest abgelesen habe, sondern den
Ganzzahlwert.
Wenn ich nun die modulorechnung richtig mache, bekomme ich bei h(33,5)
=...=5 die erste Doppelbelegung. Nun muss ich also h(33,6) = ... = 6
berechnen. 6 ist frei also kommt die 33 auf Position 33.
Was ist nun mit i? Wird i nun beim nächsten Schlüssel wieder
weitergezählt i=7, oder für den nächsten Schlüssel i=0 gesetzt?
Ah, hier steht die Antwort auf mein i:
>Wenn der i-te Versuch klappt, ist alles gut. Wenn er>nicht klappt dann wird i eben um 1 erhöht und ein neuer Versuch startet.>Aber mit jeder Zahl s beginnt man erst mal mit Versuch 0, sie in der>Tabelle unterzubringen.
Ich verstehe, das nun so: Ich nehme einen neuen Schlüssel beginne bei
i=0 egal auf welcher Zahl i vorher gestanden hat. Wenn die berechnete
Position mit i=0 sofort passt, dann wird der nächste Schlüssel genommen
und wieder mit i=0 berechnet. Wenn da dann ein Fehler kommt weil die
Position schon belegt ist, wird i hochgezählt und zwar so lange bis eine
Position kommt die leer ist. Beim wiederum nächsten Schlüssel wird dann
wieder i=0 gesetzt.
Richtig???
Und jetzt hab ich auch erst das Hashing richtig verstanden, dass du mir
vorher breit erklärt hast... Aber gut, jetzt passt's ja. Beim
quadratischen probieren wird wohl das Vorgehen mit dem i nicht anders
sein...
Danke adsf! Ich gehe also davon aus, dass ich jetzt die Sache mit dem i
richtig verstanden habe! Warten wir mal noch ab was kbuchegg dazu zu
sagen hat.
Ansonsten schon mal vielen Danke an euch!
Karl Heinz Buchegger schrieb:> Sag mal, welche Schule machst du eigentlich?> Unglaublich, dass ich mit dir> jetzt den Stoff aus der 3-ten Klasse Grundschule(!) wiederholen muss!
Nichts gegen deinen Lerneifer, aber der Stoff wird erst in der 5.Klasse
behandelt. Eventuell auch mal in der 4., aber sicher nicht in der
3.Stufe.
Mein Nachwuchs hatte schon Computer im Kindergarten und das war ne gute
Sache. Mathe machen die außer 1+2 am PC auch nicht. Google mal nach
"Schlaumäuse".
In großen Versandlagern werden die Regalplätze übrigens völlig
unregelmäßig vergeben, so daß man ohne EDV nichts mehr wiederfinden
würde. Diese Strategie ergibt besseren Durchsatz als eine lineare
Sortierung a la Bastlerregal.
Abdul K. schrieb:> Karl Heinz Buchegger schrieb:>> Sag mal, welche Schule machst du eigentlich?>>> Unglaublich, dass ich mit dir>> jetzt den Stoff aus der 3-ten Klasse Grundschule(!) wiederholen muss!>> Nichts gegen deinen Lerneifer, aber der Stoff wird erst in der 5.Klasse> behandelt.
Divisionen mit Rest?
Echt?
Also ich hab das vor 45 Jahren mit Sicherheit in der Grundschule
gelernt. Kann mich noch gut erinnern, auch wenn ich nicht mehr viel aus
dieser Zeit weiß. Eine Mutter hat 13 Äpfel und 4 Kinder. Wieviele Äpfel
kriegt jedes Kind und wieviele Äpfel bleiben der Mutter übrig, wenn alle
Kinder gleich viele Äpfel bekommen.
Haben wir haufenweise mit dem Rechenmaxi in der Klasse um die Wette
gerechnet. Gibt auch keinen Grund, warum man das nicht rechnen können
soll, wenn man Multiplikationen im Zahlenraum bis 100 auswendig gelernt
hat. Und die waren auswendig zu lernen!
Mit scheint, dass man früher scheinbar doch mehr für das Leben relevante
Dinge in der Grundschule gelernt hat. Viel Üben anstatt alle 2 Jahre
einen neuen Schulversuch, aus dem dann Hauptschulabgänger rauskommen,
die weder Lesen, noch Schreiben noch wenigstens ein bischen Kopfrechnen
können. Ok, die Bauernkinder waren immer ein bischen arm drann, weil
ihre Eltern auf dem Hof arbeiten mussten anstatt sich nachmittags mal
eine Stunde zu den Kinern zu setzen (was meine Frau Mutter grundsätzlich
getan und die Hausübungen kontrolliert hat). Um die hat sich die Frau
Lehrer dann immer besonders gekümmert, und die kamen beim Lesen auch
öfter drann, um so ihre Übungseinheiten zu kriegen.
Und in der 4. Klasse war dann die Ausweitung auf beliebige Stellenanzahl
samt zugehörigem Turmrechnen.
Die Kinder kloppen sich um diese Äpfel bis alle Äpfel Apfelmus wurden,
dann kommt die Kelle zum Verteilen ;-)
Mir schwand auch das ich in der 5.Klasse deutlich weiter war. Damals
wurden weniger Fähigkeiten stärker trainiert.
Und nachmittags gabs Testbild und Telefonieren durfte man erst nach
fragen der Eltern...
Aktuell ist es so, daß in der Klasse meines Nachwuchses nur einige
wenige Schüler die Fußspitzen mit den Fingern im Stand erreichen
können!!
DE hat echt ein Problem!!
Es ist egal was wir drüber denken, denn nicht wir sondern die Kinder
bestimmen die Zukunft. Allenfalls können wir unterstützend wirken. Ist
halt so.
Mehrfache Reschulversuche sind die Regel geworden!
Karl Heinz Buchegger schrieb:> Echt?> Also ich hab das vor 45 Jahren mit Sicherheit in der Grundschule> gelernt. Kann mich noch gut erinnern, auch wenn ich nicht mehr viel aus> dieser Zeit weiß. Eine Mutter hat 13 Äpfel und 4 Kinder. Wieviele Äpfel> kriegt jedes Kind und wieviele Äpfel bleiben der Mutter übrig, wenn alle> Kinder gleich viele Äpfel bekommen.
Theoretisch, ja
"Kompetenzerwartungen am Ende der Klasse 4 Die Schülerinnen und Schüler
erläutern die schriftlichen Rechenverfahren der Addition (mit mehreren
Summanden), der Subtraktion (mit einem Subtrahenden), der Multiplikation
(mit mehrstelligen Faktoren) und der Division mit Verwendung der
Restschreibweise (durch einstellige und wichtige zweistellige
Divisoren, z. B. 10, 12, 20, 25, 50), indem sie die einzelnen
Rechenschritte an Beispielen in nachvollziehbarer Weise beschreiben"
http://www.standardsicherung.schulministerium.nrw.de/lehrplaene/lehrplaene-gs/mathematik/lehrplan-mathematik/kompetenzen/
wie es praktisch aussieht, steht auf einem anderen Blatt
Karl Heinz Buchegger schrieb:> Eine Mutter hat 13 Äpfel und 4 Kinder. Wieviele Äpfel kriegt jedes> Kind und wieviele Äpfel bleiben der Mutter übrig, wenn alle Kinder> gleich viele Äpfel bekommen?
Das ist einfach: Jedes Kind 1 Apfel und die Mama 9 Äpfel. Immerhin ist
die Mama schon erwachsen.
Und bei einer rechenfaulen Mama oder der Rabenmutter: Jedes kind 0 Äpfel
und die Mutti 13 ;-)
