Diskussion:Multiplikative Methode

Die Berechnung in der ersten Funktion "multiplication_hash(Key)" Sollte man nicht verändern. Bei Hashverfahren macht die Hashfunktion ca. 80% der Rechenzeit aus und sollte deshalt möglichtst effizient implementiert werden. Zusätzliche deklarationen von Variablen macht die Funktion wohl übersichtlicher aber verlangsamt die Funltion und damit das Hashverfahren. Wenn ich dann an eine Datenbank mit mehreneren Millionen Einträge denken, h.d. einige Millionen mal überflüssige Speicher Belegunen und Freigaben.

Für ein korrektes Ergebnis ist die Reihenfolge der Berechnungen, sprich die Klammerung wichtig und die Konvertierung der Variablen in die Richtigen Datentypen, sonst kann es zu Überläufe oder falsche Divisionen kommen. An stelle eines Ergebnisses in Datentyp "double" kann es zu einem abgeschnittenen "double" zu einem "integer" kommen. (nicht signierter Beitrag von 85.212.149.91 (Diskussion) 04:02, 13. Jan 2006)

Mach' Dir keine Sorgen um Performance-Einbußen durch lokale Variablen, dafür hat man heutzutage optimierende Compiler.--Gunther 04:09, 13. Jan 2006 (CET)

Ach ja, eine effiziente Implementierung ist hier ohnehin nicht gefragt, es geht höchstens darum, den Algorithmus zu verdeutlichen, dafür genügt Pseudocode. Im vorliegenden Fall ist das wohl insgesamt entbehrlich.--Gunther 04:11, 13. Jan 2006 (CET)

Warum Goldener Schnitt?

Wieso verteilt der Goldene Schnitt als Faktor die Hashwerte besser als jede andere irrationale Zahl? Irgendwie geht das aus dem Artikel nicht so recht hervor, da die Aussagen in der Begründung doch für alle irrationalen Zahlen gelten, oder? --RokerHRO 17:54, 28. Aug. 2007 (CEST)

Also laut Knuth ist diese 'nette' Streuung durch Multiplikation mit dem Goldenen Schnitt ein Spezialfall des zitierten Satzes und gilt laut Satz für alle irrationalen Zahlen. Wobei der Goldene Schnitt auch nicht für alle Eingabedaten am besten geeignet ist, und Knuth auch für bestimmte Daten andere irrationale Zahlen vorschlägt. --Gms 14:06, 15. Jun. 2008 (CEST)

Bewertung

'Die Gleichverteilung erreicht man nur unzureichend, und dadurch werden die Schlüssel, gerade von gut sortierten Mengen (z.B. 1, 2, 3, ..), ungleichmäßig auf die Hashtabelle verteilt, was lange Ketten und leere Adressplätze zur Folge haben kann und damit einen langsameren Zugriff auf die Daten.

Den goldenen Schnitt kann man auf beliebig viele Stellen genau berechnen und damit gut annähern, hat jedoch das Problem, dass gleichverteilte Mengen nicht optimal auf die Hashtabelle verteilt werden, da nach dem Satz von Vera Turan Sós[3] nur gut sortierte Mengen optimal zwischen [0,1] verteilt werden.'

Die beiden Sätze kann man IMHO als Widerspruch interpretieren. Zuerst wird gesagt das sortierte Daten vermehrt Kollisionen verursachen ('lange Ketten' interpretiere ich mal so), dann wird ein Satz zitiert, nachdem nur 'gut sortierte Mengen optimal' verteilt werden ...

Vielleicht sollte man sowieso lieber mit Kollisionshäufigkeit argumentieren, als mit 'ungleichmäßig' und 'lange Ketten'. Da sonst der Leser sich sowieso fragt, 'welche Ketten?!?'. Und ungleichmässigkeit an sich ist ja auch nicht schlimmes, solange es nicht zu zuvielen Kollisionen kommt ...

Achja, und der Satzanfang 'Die Gleichverteilung' ... 'Welche Gleichverteilung?' 'Wovon?' könnten wohl typische Leserfragen sein ...

Wie sehen das andere?

--Gms 14:15, 15. Jun. 2008 (CEST)

Achja nochwas: Für die Betrachtung von Kollisionen ist es beim Hashing ja auch egal, ob die Eingabe-Menge von Schlüsseln sortiert ist, oder unsortiert ... Oder übersehe ich da etwas? --Gms 11:26, 19. Jun. 2008 (CEST)

Inhalt

diese artikel sind in erster linie für leute, die (noch) nicht wissen, worum es genau geht! es ist eine allgemeine krankheit, dass die verfasser mathematischer oder informationstechnologischer artikel nicht imstande sind, aus ihrer fachsprache herauszukommen und allgemeinverständlich zu formulieren -- dazu gehört auch, verwendete symbole zu erklären bzw lesarten der formeln verbal anzugeben. die programmierbeispiele sind dafür _nicht_ ausreichend.

Hm, kannst du deine Kritik etwas konkretisieren?

Die in den Programmbeispielen verwendeten Variablen werden im Einleitungstext des Abschnittes klar definiert und ihre Bezeichnung ist konsistent mit der vorherigen Verwendung im Artikel. Das erste Beispiel ist eine direkte Übertragung der im ersten Abschnitt erklärten Hash-Funktion mit einem konkreten eingesetzten A.

Im zweiten Beispiel-Programm wird eine Optimierung demonstriert, wenn m eine 2er Potenz ist. Das steht ja auch dabei.

Achja, signiere doch bitte deine Beiträge auf der Diskussionsseite beim nächsten Mal einfach mit --~~~~ - dann kann man die Beiträge einfacher zuordnen. --Gms 21:05, 24. Jun. 2008 (CEST)

2rd edition

Hat jemand die 2rd edition des Werkes Donald E. Knuth: The Art of Computer Programming / Sorting and Searching. Volume 3. Addison-Wesley, Massachusetts verfügbar? --Diwas 23:49, 2. Okt. 2011 (CEST)

Also 2rd (Secord?) ist unwahrscheinlich, entweder 2nd oder 3rd, vielleicht ist 2nd edition 3rd print gemeint? Aber egal, falls jemand eine Ausgabe kennt, die die Aussage belegt, könnte er bitte so freundlich sein und hier den Beleg ersetzen. Grüße --Diwas (Diskussion) 02:26, 30. Jun. 2013 (CEST)