Persistentes Hashing von Strings in Python

Question

Wie würden Sie eine beliebige Zeichenfolge in eine eindeutige Ganzzahl konvertieren, die in Python-Sitzungen und -Plattformen identisch ist? Beispielsweise würde hash('my string') nicht funktionieren, da für jede Python-Sitzung und -Plattform ein anderer Wert zurückgegeben wird.

Answer 1

Wenn eine Hash-Funktion wirklich nicht funktioniert, können Sie die Zeichenfolge in eine Zahl umwandeln.

my_string = 'my string' 
def string_to_int(s): 
    ord3 = lambda x : '%.3d' % ord(x) 
    return int(''.join(map(ord3, s))) 

In[10]: string_to_int(my_string) 
Out[11]: 109121032115116114105110103L 

Dies ist umkehrbar, indem jedes Triplett durch chr abbildet.

def int_to_string(n) 
    s = str(n) 
    return ''.join([chr(int(s[i:i+3])) for i in range(0, len(s), 3)]) 

In[12]: int_to_string(109121032115116114105110103L) 
Out[13]: 'my string' 

Answer 2

einen Hash-Algorithmus wie MD5 oder SHA1 verwenden, dann wandeln die hexdigest über int():

>>> import hashlib 
>>> int(hashlib.md5('Hello, world!').hexdigest(), 16) 
144653930895353261282233826065192032313L 

Answer 3

First off, haben Sie wahrscheinlich nicht wirklich die ganzen Zahlen tatsächlich einzigartig sein wollen. Wenn Sie das tun, sind Ihre Nummern möglicherweise nicht unbegrenzt groß. Wenn das wirklich das ist, was Sie wollen, dann könnten Sie eine Bibliothek bignum verwenden und die Bits der Zeichenkette als Darstellung einer (möglicherweise sehr großen) Ganzzahl interpretieren. Wenn Ihre Zeichenfolgen das Zeichen \ 0 enthalten können, sollten Sie eine 1 voranstellen, damit Sie z. "\ 0 \ 0" von "\ 0".

Wenn Sie jetzt Zahlen in begrenzter Größe bevorzugen, verwenden Sie eine Art von Hashing. MD5 wird funktionieren, aber es ist Overkill für den angegebenen Zweck. Ich empfehle stattdessen, sdbm zu verwenden, es funktioniert sehr gut. In C sieht es wie folgt aus:

static unsigned long sdbm(unsigned char *str) 
{ 
    unsigned long hash = 0; 
    int c; 

    while (c = *str++) 
     hash = c + (hash << 6) + (hash << 16) - hash; 

    return hash; 
} 

Die Quelle, http://www.cse.yorku.ca/~oz/hash.html stellt auch ein paar andere Hash-Funktionen.

Answer 4

Hier sind meine python27 Implementierung für Algorithmen hier aufgelistet: http://www.cse.yorku.ca/~oz/hash.html. Keine Ahnung, ob sie effizient sind oder nicht.

from ctypes import c_ulong 

def ulong(i): return c_ulong(i).value # numpy would be better if available 

def djb2(L): 
    """ 
    h = 5381 
    for c in L: 
    h = ((h << 5) + h) + ord(c) # h * 33 + c 
    return h 
    """ 
    return reduce(lambda h,c: ord(c) + ((h << 5) + h), L, 5381) 

def djb2_l(L): 
    return reduce(lambda h,c: ulong(ord(c) + ((h << 5) + h)), L, 5381) 

def sdbm(L): 
    """ 
    h = 0 
    for c in L: 
    h = ord(c) + (h << 6) + (h << 16) - h 
    return h 
    """ 
    return reduce(lambda h,c: ord(c) + (h << 6) + (h << 16) - h, L, 0) 

def sdbm_l(L): 
    return reduce(lambda h,c: ulong(ord(c) + (h << 6) + (h << 16) - h), L, 0) 

def loselose(L): 
    """ 
    h = 0 
    for c in L: 
    h += ord(c); 
    return h 
    """ 
    return sum(ord(c) for c in L) 

def loselose_l(L): 
    return reduce(lambda h,c: ulong(ord(c) + h), L, 0) 

Answer 5

Hier ist eine andere Option, ziemlich roh (wahrscheinlich hat viele Kollisionen) und nicht sehr gut lesbar.

Er arbeitete für den Zweck einen int zu generieren (und später, eine zufällige Farbe) für verschiedene Strings:

aString = "don't panic" 
reduce(lambda x,y:x+y, map(lambda x:ord(x[0])*x[1],zip(aString, range(1, len(aString)))))