ich irgendwo über andere Datenstrukturen lesen ähnlich wie Hash-Tabellen, Wörterbücher, sondern ints zu verwenden, sie wurden mit Schwimmern/Doppel usw.Hashtables/Wörterbücher, die Schwimmer verwenden/verdoppelt
Wer weiß, was sie sind?
Wenn Sie floats/doubles als Schlüssel in Ihrem Hash verwenden, ist das einfach. In .NET zum Beispiel wird nur verwendet.
Wenn Sie den Hash reden ....
Technisch eine doppelte anstelle eines int Basis aus werden etwa mit können Sie jedes Element als interne Hash haben. Normalerweise geschieht dies mit einem int oder long, da diese schnell sind und der Hash-Algorithmus einfach zu berechnen ist.
Allerdings ist der Hash wirklich nur ein BitArray im Herzen, also würde alles funktionieren. Es ist wirklich nicht viel Vorteil, dies zu etwas anderem als einem int oder long zu machen, außer potenziell einen größeren Satz von Hash-Werten zu erlauben (zB: wenn Sie zu einem 8 Byte oder größeren Typ für Ihren Hash gehen).
Gute Antwort. Tatsächlich sind Keys in Hashtabellen nichts anderes als Bit-Arrays, und ein "int" -Typ ist einfach die bequemste Art, dies darzustellen. – Noldorin
Ja: Das Verwenden eines Long als Hash ist technisch dasselbe wie das Verwenden eines Double (64-Bit-Arrays). Wenn Sie länger wollten, könnten Sie zu einem 128-Bit-Typ gehen, wie zum Beispiel einer GUID (was in .NET der Dezimalzahl entspricht). Bei Integertypen ist Math jedoch oft schneller als bei Gleitkommatypen. –
Danke Reed. Ja, ich habe mich gefragt, ob das Hashwerte größer sein könnte. Also würde die Verwendung von double in einem .net-Wörterbuch immer noch Ints verwenden, richtig? –
Ihr Fragenverlauf zeigt, dass Sie .Net verwenden, daher werde ich in diesem Zusammenhang antworten.
Wenn Sie ein Wörterbuch möchten, die bewusst ist, geben, so dass Sie es sollte Schwimmern oder Doppel für die Schlüssel oder Werte verwenden angeben können, verwenden System.Collections.Generic.Dictionary<T, U>http://msdn.microsoft.com/en-us/library/xfhwa508.aspx
Wenn Sie ein Wörterbuch möchten, die blind, ist der Typ, so dass Sie können Schwimmer und Doppel für Tasten und Werte verwenden, verwenden Sie System.Collections.HashTablehttp://msdn.microsoft.com/en-us/library/system.collections.hashtable.aspx
Sie meinen als Schlüssel? Das erscheint mir schwierig.
Wenn Sie sie als beliebige Schlüssel verwenden, sind sie nicht besser als Ganzzahlen.
Wenn Sie erwarten, einen Fließkommawert zu berechnen und ihn in einer Hashtabelle nach etwas zu durchsuchen, leben Sie sehr gefährlich. Fließkommazahlen haben keine unendliche Genauigkeit, und die Berechnung derselben Sache auf zwei leicht unterschiedliche Arten kann zu sehr kleinen Unterschieden im Ergebnis führen. Hash-Schlüssel sind darauf angewiesen, jedes Mal das gleiche zu erhalten, also musst du vorsichtig sein, um zu runden und immer genau die gleiche Runde zu haben. Das ist übrigens kniffliger als es sich anhört.
Also, was würden Sie mit Fließkomma-Hashes tun?
Danke, nur über die Frage m für einen größeren Hash-Wert gesetzt. Obwohl ich mich erinnere, Datenstrukturen zu sehen, die sie tatsächlich benutzen, wenn ich nicht falsch liege. –
Ein Hash-Algorithmus ist im Allgemeinen nur eine Funktion, die eine kleinere Ausgabe von einem größeren Eingang erzeugt. Gute Hash-Funktionen haben interessante Eigenschaften wie eine große Änderung in der Ausgabe für eine kleine Änderung in der Eingabe und eine Gewissheit, dass sie jeden möglichen Ausgabewert für einige Eingaben erzeugen.
Es ist nicht schwer, eine einfache Polynom-Typ-Hash-Funktion zu schreiben, die einen Fließkommawert ausgibt, anstatt einen ganzzahligen Wert, aber es ist schwierig sicherzustellen, dass die resultierende Hash-Funktion die gewünschten Eigenschaften hat, ohne in die Details der bestimmte Gleitkommadarstellung verwendet.
Zumindest ein Grund dafür, dass Hash-Funktionen fast immer in Integer-Arithmetik implementiert sind, liegt darin, dass der Nachweis verschiedener Eigenschaften einer Ganzzahlberechnung einfacher ist als das Gleiche für eine Gleitkommaberechnung.
Es ist ziemlich einfach zu beweisen, dass einige (Summe der Primfaktoren) modulo (ein anderer Prim) notwendigerweise jeden möglichen Ausgang für irgendeine Eingabe erzeugen muss.Das Gleiche für eine Berechnung mit einer Reihe von Fließkomma-Brüchen wäre ein Nachteil.
Hinzu kommt die relative Schwierigkeit der Speicherung und Übertragung von Gleitkommawerten ohne Korruption, und es ist einfach nicht wert.
In .Net ist diese Frage nicht gültig. Wenn Sie Ihre Sprache/DevTools angeben, gibt es möglicherweise eine Antwort für Sie. –
@ David B: Ich denke, das ist eine theoretische Algorithmus Frage: "Kann etwas anderes als eine ganze Zahl als Hash-Struktur verwendet werden?" –
Ja, das ist eine allgemeine Programmierfrage. –