Unterschied hash() und zlib.crc32()

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
HarryH
User
Beiträge: 266
Registriert: Freitag 23. Mai 2003, 09:08
Wohnort: Deutschland

Unterschied hash() und zlib.crc32()

Beitragvon HarryH » Donnerstag 2. Oktober 2008, 12:13

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!
Gruß, Harry
lunar

Re: Unterschied hash() und zlib.crc32()

Beitragvon lunar » Donnerstag 2. Oktober 2008, 12:49

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.
BlackJack

Beitragvon BlackJack » Donnerstag 2. Oktober 2008, 12:56

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.
HarryH
User
Beiträge: 266
Registriert: Freitag 23. Mai 2003, 09:08
Wohnort: Deutschland

Beitragvon HarryH » Donnerstag 2. Oktober 2008, 13:51

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?
Gruß, Harry
BlackJack

Beitragvon BlackJack » Donnerstag 2. Oktober 2008, 14:44

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;
}

Wer ist online?

Mitglieder in diesem Forum: Bing [Bot]