Hallo,
Ich habe ein paar Fragen zu hash() und zlib.crc32():
Gibt es einen Unterschied zwischen der built-in-Funktion hash() und der Funktion zlib.crc32()?
Warum, bzw. wann liefern beide Funktionen auch negative Werte?
Sind diese Funktionen zu gebrauchen um Indizies von Pfaden innerhalb einer Bibliothek zu erstellen? Wie hoch ist die Kollisionsgefahr?
Schon mal Dankeschön im Voraus!
Unterschied hash() und zlib.crc32()
Diese Funktionen haben überhaupt nichts miteinander zu tun.HarryH hat geschrieben:Gibt es einen Unterschied zwischen der built-in-Funktion hash() und der Funktion zlib.crc32()?
hash() dient dazu, möglichst eindeutige IDs für Objekte zu errechnen, um set() und dict() performant implementieren zu können. hash() stützt sich dabei auf die Attribute eines Objekts.
zlib.crc32() dagegen ist ein Standardalgorithmus, um Prüfsummen für Binärdaten zu erstellen, um so die Integrität der Daten zu garantieren.
Die Implementierung von Hash kenne ich nicht, crc32 ist eine Polynomdivision, deren mathematische Beschreibung auf Wikipedia zu finden ist. Dann kannst du dir selbst ausrechnen, wann da negative Werte rauskommen.Warum, bzw. wann liefern beide Funktionen auch negative Werte?
Lies doch einfach mal den Docstring von hash() und den Wikipedia-Artikel zu crc32, um die Kollisionsgefahr zu beurteilen.Sind diese Funktionen zu gebrauchen um Indizies von Pfaden innerhalb einer Bibliothek zu erstellen? Wie hoch ist die Kollisionsgefahr?
Die Kollisionsgefahr bei `hash()` lässt sich nicht so ohne weiteres feststellen, weil die Funktion selber nichts tut, sondern die `__hash__()`-Methode auf dem übergebenen Objekt aufruft. Und da kann man sowohl Objekte konstruieren, die bei `__hash__()` nie kollidieren, als auch welche die das 100%ig immer tun.
Schon mal vielen Dank für eure Antworten.
Da ich kein Mathematiker bin, kann ich allerdings nicht sehr viel mit den mathematischen Konstrukten in wikipedia zu crc anfangen. Der Rest ist aber sehr interessant.
Weiß jemand auf was für einen Algorithmus sich die hash()-Funktion gründet?
Ist sie für kurze Strings, wie eben Pfadangaben, besser geeignet als der crc-Algorithmus?
Da ich kein Mathematiker bin, kann ich allerdings nicht sehr viel mit den mathematischen Konstrukten in wikipedia zu crc anfangen. Der Rest ist aber sehr interessant.
Wie steht es bezüglich hash() bei Standard-String-Objekten. Wie steht es dabei mit der Kollisionsgefahr?BlackJack hat geschrieben:Die Kollisionsgefahr bei `hash()` lässt sich nicht so ohne weiteres feststellen, weil die Funktion selber nichts tut, sondern die `__hash__()`-Methode auf dem übergebenen Objekt aufruft. Und da kann man sowohl Objekte konstruieren, die bei `__hash__()` nie kollidieren, als auch welche die das 100%ig immer tun.
Weiß jemand auf was für einen Algorithmus sich die hash()-Funktion gründet?
Ist sie für kurze Strings, wie eben Pfadangaben, besser geeignet als der crc-Algorithmus?
Gruß, Harry
Use the source! Python ist doch quelloffen. In `Objects/stringobject.c` findet man folgende Funktion:
Code: Alles auswählen
static long
string_hash(PyStringObject *a)
{
register Py_ssize_t len;
register unsigned char *p;
register long x;
if (a->ob_shash != -1)
return a->ob_shash;
len = Py_SIZE(a);
p = (unsigned char *) a->ob_sval;
x = *p << 7;
while (--len >= 0)
x = (1000003*x) ^ *p++;
x ^= Py_SIZE(a);
if (x == -1)
x = -2;
a->ob_shash = x;
return x;
}