Как __hash__ реализован в Python 3.2? - PullRequest
Новая
       27

Как __hash__ реализован в Python 3.2?

4 голосов
/ 15 мая 2011

Я хочу, чтобы пользовательский объект мог работать с хэшем (с помощью травления). Я мог бы найти __hash__ алгоритм для Python 2.x (см. Код ниже), но он, очевидно, отличается от хеша для Python 3.2 (интересно, почему?). Кто-нибудь знает, как __hash__ реализовано в Python 3.2? 

#Version: Python 3.2

def c_mul(a, b):
    #C type multiplication
    return eval(hex((int(a) * b) & 0xFFFFFFFF)[:-1])

class hs:
    #Python 2.x algorithm for hash from http://effbot.org/zone/python-hash.htm
    def __hash__(self):
        if not self:
            return 0 # empty
        value = ord(self[0]) << 7
        for char in self:
            value = c_mul(1000003, value) ^ ord(char)
        value = value ^ len(self)
        if value == -1:
            value = -2
        return value


def main():
    s = ["PROBLEM", "PROBLEN", "PROBLEO", "PROBLEP"]#, "PROBLEQ", "PROBLER", "PROBLES"]
    print("Python 3.2 hash() bild-in")
    for c in s[:]: print("hash('", c, "')=", hex(hash(c)),  end="\n")
    print("\n")
    print("Python 2.x type hash: __hash__()")
    for c in s[:]: print("hs.__hash__('", c, "')=", hex(hs.__hash__(c)),  end="\n")


if __name__ == "__main__":
    main()

OUTPUT:
Python 3.2 hash() bild-in
hash(' PROBLEM ')= 0x7a8e675a
hash(' PROBLEN ')= 0x7a8e6759
hash(' PROBLEO ')= 0x7a8e6758
hash(' PROBLEP ')= 0x7a8e6747


Python 2.x type hash: __hash__()
hs.__hash__(' PROBLEM ')= 0xa638a41
hs.__hash__(' PROBLEN ')= 0xa638a42
hs.__hash__(' PROBLEO ')= 0xa638a43
hs.__hash__(' PROBLEP ')= 0xa638a5c

Редактировать: Разъяснение различий, для Python 3.2 "Хеш-значения теперь являются значениями нового типа, Py_hash_t и т. Д."

Edit2 @Pih Спасибо [ссылка] http://svn.python.org/view/python/trunk/Objects/stringobject.c?view=markup

static long
1263    string_hash(PyStringObject *a)
1264    {
1265        register Py_ssize_t len;
1266        register unsigned char *p;
1267        register long x;
1268    
1269        if (a->ob_shash != -1)
1270            return a->ob_shash;
1271        len = Py_SIZE(a);
1272        p = (unsigned char *) a->ob_sval;
1273        x = *p << 7;
1274        while (--len >= 0)
1275            x = (1000003*x) ^ *p++;
1276        x ^= Py_SIZE(a);
1277        if (x == -1)
1278            x = -2;
1279        a->ob_shash = x;
1280        return x;
1281    }

Ответы [ 2 ]

5 голосов
/ 15 мая 2011

Ответ о том, почему они различаются, записан там:

Значения хеш-функции теперь являются значениями нового типа Py_hash_t, размер которого определен так же, как указатель.Ранее они имели тип long, который в некоторых 64-разрядных операционных системах по-прежнему имеет длину всего 32 бита.

Хэширование также учитывает вычисление новых значений, посмотрите на 

 sys.hash_info

Для строк вы можете взглянуть на http://svn.python.org/view/python/trunk/Objects/stringobject.c?view=markup line 1263 string_hash (PyStringObject * a)

2 голосов
/ 15 мая 2011

Я посмотрел новую функцию в исходном коде (в unicodeobject.c) и перестроил ее в Python.Вот оно: 

def my_hash(string):
    x = ord(string[0]) << 7
    for c in string:
        x = (1000003 * x) ^ ord(c)
    x ^= len(string)
    needCorrection =  x & (1 << 65)
    x %= 2 ** 64
    if needCorrection:
        x = -~(-x ^ 0xFFFFFFFFFFFFFFFF)
    if x == -1:
        x = -2
    return x

Это только 64-битная версия.Теперь с поправкой на странное поведение Python, когда числа становятся отрицательными.(Тебе лучше не думать об этом слишком много.)

...