Seite 1 von 1
Unterschied hash() und zlib.crc32()
Verfasst: Donnerstag 2. Oktober 2008, 12:13
von HarryH
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!
Re: Unterschied hash() und zlib.crc32()
Verfasst: Donnerstag 2. Oktober 2008, 12:49
von lunar
HarryH hat geschrieben:Gibt es einen Unterschied zwischen der built-in-Funktion hash() und der Funktion zlib.crc32()?
Diese Funktionen haben überhaupt nichts miteinander zu tun.
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.
Warum, bzw. wann liefern beide Funktionen auch negative Werte?
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.
Sind diese Funktionen zu gebrauchen um Indizies von Pfaden innerhalb einer Bibliothek zu erstellen? Wie hoch ist die Kollisionsgefahr?
Lies doch einfach mal den Docstring von hash() und den Wikipedia-Artikel zu crc32, um die Kollisionsgefahr zu beurteilen.
Verfasst: Donnerstag 2. Oktober 2008, 12:56
von BlackJack
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.
Verfasst: Donnerstag 2. Oktober 2008, 13:51
von HarryH
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.
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.
Wie steht es bezüglich hash() bei Standard-String-Objekten. Wie steht es dabei mit der Kollisionsgefahr?
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?
Verfasst: Donnerstag 2. Oktober 2008, 14:44
von BlackJack
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;
}