Хеши и множества

Хеш-функция — преобразование объекта произвольного размера в объект фиксированного размера

Python: hash(константный_объект). От изменяемого объекта (например, списка) хеши считать смысла нет, так-то хеш вычисляется сразу при создании объекта, а так каждый раз пересчитывать придётся.

   1 >>> hash
   2 <built-in function hash>
   3 >>> hash(123)
   4 123
   5 >>> hash(12334256)
   6 12334256
   7 >>> hash(12334256356735674567)
   8 805041310667204812
   9 >>> hash("QWERTY")
  10 -2463846115164988031
  11 >>> hash("QWERTZ")
  12 -959534987291318183
  13 >>> hash("QWERTX")
  14 9070152385316643634
  15 >>> hash((2,34,5))
  16 3789663398087360548
  17 >>> hash([2,34,5])
  18 Traceback (most recent call last):
  19   File "<stdin>", line 1, in <module>
  20 TypeError: unhashable type: 'list'
  21 >>>
  22 

При сравнении объектов можно сначала сравнивать их хеши (это просто целые), а если совпадут — тогда сами объекты, это быстрее, если сравнение объектов — дорогая операция.

Поиск по хешу

Если хранить объекты в списке (массиве), то для ответа на вопрос, есть ли в списке длиной N некоторый объект придётся проходить веси список от начала

Идея:

>>> T[hsh("QWERTA")] 1 >>> hsh("QWERTA") 11 >>> hsh("QWERTW") 11

Такая структура данных в случае идеального хеша сократит скорость поиска в 16 раз! Но и в обычной жизни она эффективна, потому что индексирование выполняется за фиксированное время, а поиск производится по ведру, в котором меньше элементов:

   1 >>> T=[[] for i in range(16)]
   2 >>> for c in "qwertyuiopasdfghjklzxcvbnm":
   3 ...   T[hsh(c)].append(c)
   4 ...
   5 >>> T
   6 [['d'], [], ['k'], [], ['g', 'j', 'x', 'v'], ['p', 'a'], ['i', 'h'], ['u'], ['w', 't', 'l', 'm'], ['e'], ['q', 'z'], ['c', 'n'], [], ['s'], ['r', 'f', 'b'], ['y', 'o']]
   7 

Множества

TODO Такая структура данных в Python3 уже реализована! Это множество:

Д/З

TODO

Python/PsyPython2018/14_HashSets (last edited 2018-12-18 06:19:39 by FrBrGeorge)