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.
Ok. Soweit verstanden. Aber wo ziehst du die 6 in deiner letzten Antwort her? Wo kommt die her?
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?
Ja, ich meinte genau die 6 :-) Jetzt ist es aber klar...
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 :-)
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.
Hans Wurst schrieb: > h(k,i)=((k mod m) + i) mod m Das lässt sich auch so schreiben: h(k,i) = (k + i) mod m
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?
i wird IMMER auf 0 zurückgesetzt für einen neuen Wert, sonst bringt das mit der HAshfunktion ja garnix.
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...
Richtig, das i startet immer bei 0. Wenn du drüber nachdenkst wie das wiederabrufen von Werten funktioniert wird dir auch klar warum das so sein muss.
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 ;-)
Beitrag #5189726 wurde von einem Moderator gelöscht.
Beitrag #5189728 wurde von einem Moderator gelöscht.
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.