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

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

• Чаще всего — в число
• Поскольку хешей меньше, чем всего объектов, существую объекты с одинаковыми шешами
  • …желательно, чтобы вручную такие объекты было трудно подобрать
• Желательно, чтобы хеши почти похожих объектов были разные
• Желательно, чтобы при переборе объектов получались как можно более разные хеши

  • …хотя чисто теоретически можно подобрать много обектов с одинаковым хешом

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 некоторый объект придётся проходить веси список от начала

• Если объект в списке есть — это в среднем N/2 сравнений
• Если объекта в списке нет — это ровно N сравнений

Идея:

• если объектов у нас предполагается, допустим, 8 штук, заведём список T побольше, скажем, на 2*8==16. И назовём его «множеством».

• Зададим хеш-функцию hsh() в диапазоне 0…15:

  •    1 >>> def hsh(Obj):
       2 ...   return hash(Obj)%16
    

• От каждого объекта O будем вычислять хеш h (в диапазоне от 0 до 15)

• Простой вариант (возможны ложные срабатывания):

  • T — это просто массив нулей

    •    1 >>> T=[0]*16
         2 >>> T
         3 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
         4 
      

  • Добавление элемента O с хешом h в множество: T[h]=1

    •    1 >>> T[hsh("QWERTY")]=1
         2 >>> T[hsh("QWERTZ")]=1
         3 >>> T[hsh("QWERTX")]=1
         4 >>> T[hsh("QWERTW")]=1
         5 >>> T
         6 [0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0]
         7 
      

  • Проверка, принадлежит ли элемент O с хешом h множеству T: if T[h]…

    •    1 >>> T[hsh("QWERTZ")]
         2 1
         3 >>> T[hsh("QWERTW")]
         4 1
         5 >>> T[hsh("QWERTB")]
         6 0
         7 
      

  • Возможны ложные срабатывания, если у двух объектов хеш совпадает (а это очень частая ситуация при маленьком диапазоне)
    • {{{!#highlight pycon

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

• }}}

• Вариант посложнее: хранить в T не 0/1, а списки объектов (т. н. «вёдра»)

  •    1 >>> T=[[] for i in range(16)]
       2 >>> T
       3 [[], [], [], [], [], [], [], [], [], [], [], [], [], [], [], []]
       4 
    

  • Добавление объекта O с хешом h — это добавление его в ведро №h

    •    1 >>> A="QWERTY"
         2 >>> T[hsh(A)].append(A)
         3 >>> T
         4 [[], ['QWERTY'], [], [], [], [], [], [], [], [], [], [], [], [], [], []]
         5 >>> A="QWERTX"
         6 >>> T[hsh(A)].append(A)
         7 >>> A="QWERTZ"
         8 >>> T[hsh(A)].append(A)
         9 >>> A="QWERTW"
        10 >>> T[hsh(A)].append(A)
        11 >>> T
        12 [[], ['QWERTY'], ['QWERTX'], [], [], [], [], [], [], ['QWERTZ'], [], ['QWERTW'], [], [], [], []]
        13 
      

    • В этом случае объекты с одинаковым хешом попадают в одно ведро:

      •    1 >>> A="QWERTT"
           2 >>> T[hsh(A)].append(A)
           3 >>> T
           4 [[], ['QWERTY'], ['QWERTX'], [], [], [], [], [], [], ['QWERTZ', 'QWERTT'], [], ['QWERTW'], [], [], [], []]
           5 
        

  • Проверка, принадлежит ли элемент O с хешом h множеству T — это поиск объекта в ведре №h

    •    1 >>> A
         2 'QWERTT'
         3 >>> A in T[hsh(A)]
         4 True
         5 >>> A="QWERTU"
         6 >>> A in T[hsh(A)]
         7 False
         8 >>> A="QWERTX"
         9 >>> A in T[hsh(A)]
        10 True
        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 уже реализована! Это множество:

• Конструирование и обычное использование
  • Имеется циклический конструктор
• Хранит только константные элементы
• Можно изготовить из любой последовательности
• Является последовательностью
  • Порядок хранения элементов не определён

• Поддерживает операции .add() и .pop()

• Поддерживает теоретико-множественные операции

Д/З

TODO

• Прочитать про множества в учебнике и тьюториале