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

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

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

{{{#!highlight pycon
>>> hash
<built-in function hash>
>>> hash(123)
123
>>> hash(12334256)
12334256
>>> hash(12334256356735674567)
805041310667204812
>>> hash("QWERTY")
-2463846115164988031
>>> hash("QWERTZ")
-959534987291318183
>>> hash("QWERTX")
9070152385316643634
>>> hash((2,34,5))
3789663398087360548
>>> hash([2,34,5])
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'
>>>
}}}

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

== Поиск по хешу ==
Если хранить объекты в списке (массиве), то для ответа на вопрос, есть ли в списке длиной N некоторый объект придётся проходить веси список от начала
  * Если объект в списке есть — это в среднем N/2 сравнений
  * Если объекта в списке нет — это ровно N сравнений

Идея:
 * если объектов у нас предполагается, допустим, 8 штук, заведём список '''T''' ''побольше'', скажем, на 2*8==16. И назовём его «множеством».
 * Зададим хеш-функцию `hsh()` в диапазоне 0…15:
  {{{#!highlight pycon
>>> def hsh(Obj):
...   return hash(Obj)%16
}}}
 * От каждого объекта '''O''' будем вычислять хеш '''h''' (в диапазоне от 0 до 15)
 * Простой вариант (возможны ложные срабатывания):
  * '''T''' — это просто массив нулей
   {{{#!highlight pycon
>>> T=[0]*16
>>> T
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
  }}}
  * Добавление элемента '''O''' с хешом '''h''' в множество: `T[h]=1`
   {{{#!highlight pycon
>>> T[hsh("QWERTY")]=1
>>> T[hsh("QWERTZ")]=1
>>> T[hsh("QWERTX")]=1
>>> T[hsh("QWERTW")]=1
>>> T
[0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0]
  }}}
  * Проверка, принадлежит ли элемент '''O''' с хешом '''h''' множеству '''T''': `if T[h]…`
   {{{#!highlight pycon
>>> T[hsh("QWERTZ")]
1
>>> T[hsh("QWERTW")]
1
>>> T[hsh("QWERTB")]
0
  }}}
  * Возможны ложные срабатывания, если у двух объектов хеш совпадает (а это очень частая ситуация при маленьком диапазоне)
   {{{!#highlight pycon
>>> T[hsh("QWERTA")]
1
>>> hsh("QWERTA")
11
>>> hsh("QWERTW")
11
  }}}
 * Вариант посложнее: хранить в '''T''' не 0/1, а списки объектов (т. н. «вёдра»)
  {{{#!highlight pycon
>>> T=[[] for i in range(16)]
>>> T
[[], [], [], [], [], [], [], [], [], [], [], [], [], [], [], []]
  }}}
  * Добавление объекта '''O''' с хешом '''h''' — это добавление его в ведро №'''h'''
   {{{#!highlight pycon
>>> A="QWERTY"
>>> T[hsh(A)].append(A)
>>> T
[[], ['QWERTY'], [], [], [], [], [], [], [], [], [], [], [], [], [], []]
>>> A="QWERTX"
>>> T[hsh(A)].append(A)
>>> A="QWERTZ"
>>> T[hsh(A)].append(A)
>>> A="QWERTW"
>>> T[hsh(A)].append(A)
>>> T
[[], ['QWERTY'], ['QWERTX'], [], [], [], [], [], [], ['QWERTZ'], [], ['QWERTW'], [], [], [], []]
  }}}
   * В этом случае объекты с одинаковым хешом попадают в одно ведро:
    {{{#!highlight pycon
>>> A="QWERTT"
>>> T[hsh(A)].append(A)
>>> T
[[], ['QWERTY'], ['QWERTX'], [], [], [], [], [], [], ['QWERTZ', 'QWERTT'], [], ['QWERTW'], [], [], [], []]
}}}
  * Проверка, принадлежит ли элемент '''O''' с хешом '''h''' множеству '''T''' — это поиск объекта в ведре №'''h'''
   {{{#!highlight pycon
>>> A
'QWERTT'
>>> A in T[hsh(A)]
True
>>> A="QWERTU"
>>> A in T[hsh(A)]
False
>>> A="QWERTX"
>>> A in T[hsh(A)]
True
  }}}

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

{{{#!highlight pycon
>>> T=[[] for i in range(16)]
>>> for c in "qwertyuiopasdfghjklzxcvbnm":
...   T[hsh(c)].append(c)
...
>>> T
[['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']]
}}}

== Множества ==
'''TODO'''
Такая структура данных в Python3 уже реализована! Это множество:
 * Конструирование и обычное использование
  * Имеется циклический конструктор
 * Хранит только константные элементы
 * Можно изготовить из любой последовательности
 * Является последовательностью
  * Порядок хранения элементов не определён
 * Поддерживает операции `.add()` и `.pop()`
 * Поддерживает теоретико-множественные операции

== Д/З ==
'''TODO'''
 * Прочитать про множества в учебнике и тьюториале
 *