Dove posso trovare la fonte o l'algoritmo della funzione hash() di Python?

Question

>>> hash("\x01") 
128000384 
>>> hash("\x02") 
256000771 
>>> hash("\x03") 
384001154 
>>> hash("\x04") 
512001541 

parte interessante è 128000384 x 2 non è 256000771, e anche gli altri

Mi chiedo solo come funziona l'algoritmo e vogliono imparare qualcosa su di esso.

Answer 1

Se si scarica il codice sorgente di Python, lo troverete di sicuro! Ma tenete a mente che la funzione di hash è implementata in modo diverso per ogni tipo di oggetto.

Ad esempio, nella funzione unicode_hash si trova la funzione di hash unicode in Objects/unicodeobject.c. Potrebbe essere necessario cercare un po 'di più per trovare la funzione hash della stringa. Trova la struttura che definisce l'oggetto a cui sei interessato e nel campo tp_hash troverai la funzione che calcola il codice hash di quell'oggetto.

Per l'oggetto stringa di: il codice esatto si trova nella Objects/stringobject.c nella funzione string_hash:

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

Answer 2

vi consiglio di leggere la voce di Wikipedia per le funzioni di hash (http://en.wikipedia.org/wiki/Hash_function) per comprendere meglio le funzioni di hash . Riceverai molte risposte per l'implementazione!

di riassumere alcuni punti chiave (non solo per questa specifica funzione, ma in generale per tutte le funzioni hash):

• su un dato di entrata (a seconda delle esigenze sarà un numero, una stringa, e l'oggetto , ecc.) può produrre un output più piccolo e di lunghezza fissa. Di solito (per non dire sempre), è un numero intero.
• Diversi ingressi producono uscite differenti. Poiché l'uscita è più piccola dell'input, ci saranno SEMPRE input diversi che producono lo stesso output. Chiamata "hash collition" e dovrebbe essere raro se la funzione hash è ben progettata
• Il processo dovrebbe essere efficiente, quindi è veloce ottenere l'hash di un dato di input
• Per alcuni tipi di funzioni hash è importante che gli ingressi simili producono delle uscite non simili. per altri, non è un requisito, ma di solito è raggiunto. Ecco perché hash("\x02") non è 2*hash("\x01")

Fondamentalmente, funzioni hash sono utilizzati per utilizzare un numero intero posto dell'oggetto completo , che è possibile gestire in modo più semplice ed efficiente