Какова логика порядка функций хэш-функции Python?

Question

Как известно, некоторые структуры данных Python используют таблицы хеша для хранения таких предметов, как set или dictionary. Таким образом, в этих объектах нет порядка. Но, похоже, для некоторых последовательностей чисел это неверно.

Для примера рассмотрим следующие примеры:

>>> set([7,2,5,3,6]) 
set([2, 3, 5, 6, 7]) 

>>> set([4,5,3,0,1,2]) 
set([0, 1, 2, 3, 4, 5]) 

Но не отсортированные если мы делаем небольшое изменение:

>>> set([8,2,5,3,6]) 
set([8, 2, 3, 5, 6]) 

Таким образом, вопрос: Как хэш-функция работы Python на целые последовательности?

Answer 1

Хотя в SO есть много вопросов о hash и его порядке, но ни один из них не объясняет алгоритм хэш-функции.

Итак, все, что вам нужно, это знать, как python вычисляет индексы в хэш-таблице.

Если вы идете через hashtable.c файл в CPython исходном коде, вы увидите следующие строки в _Py_hashtable_set функции, которая показывает путь питона расчета индекса ключей хэш-таблицы:

key_hash = ht->hash_func(key); 
index = key_hash & (ht->num_buckets - 1); 

Так как значение хэш из целых чисел - это целое число * (кроме -1), индекс основан на числе и длине вашей структуры данных (ht->num_buckets - 1) и вычисляется с помощью Поразрядный и между (ht->num_buckets - 1) и номером.

Теперь рассмотрим следующий пример с set, которые используют хэш-таблицу:

>>> set([0,1919,2000,3,45,33,333,5]) 
set([0, 33, 3, 5, 45, 333, 2000, 1919]) 

Для числа 33 мы имеем:

33 & (ht->num_buckets - 1) = 1 

Это на самом деле это:

'0b100001' & '0b111'= '0b1' # 1 the index of 33 

Примечание в данном случае (ht->num_buckets - 1) является 8-1=7 или 0b111.

И 1919:

'0b11101111111' & '0b111' = '0b111' # 7 the index of 1919 

И 333:

'0b101001101' & '0b111' = '0b101' # 5 the index of 333 

И так же, как и для предыдущих примеров в вопросе:

>>> set([8,2,5,3,6]) 
set([8, 2, 3, 5, 6]) 

'0b1000' & '0b100'='0b0' # for 8 
'0b110' & '0b100'='0b100' # for 8 

---

* хэш-функция для класса int:

class int: 
    def __hash__(self): 
     value = self 
     if value == -1: 
      value = -2 
     return value