Хеширование и словари

Hash-функция

Обязательные свойства:

• Однозначность (функция!)
• Много → мало (⇒ взаимонеоднозначность)

Дополнительные свойства зависят от свойств хешируемого множества!

• Различие для «почти похожих» параметров

  • Например, n//1024 — плохая функция, а n%1014 — получше

• равномерное (или другое заданное) распределение на множестве значений
• (более сильно) непредсказуемое расстояние между значениями на почти похожих операндах

  • например, x%65536 vs int(f"{sin(x+1):14.13f}"[-5:])

    • Одно равномерное, другое (несколько) непредсказуемое ( а равномерное ли?)

• Невосстановимость исходного значения/значения с коллизией из хеша (иначе как перебором области определения)

• Редкость или отсутствие hash collision на определённом множестве

Замечания:

• ⇒ всегда можно подобрать множество, на котором нужное свойство не выполняется
• зная свойства множества, можно подобрать «почти идеальную» hash-функцию

Хеш-таблицы

Задача: есть множество {E} объектов: |{E}|=N , в хранилище лежат k объектов этого множества

• Задача поиска значения в хранилище — O(k) в общем случае

• Если N невелико и для всего множества ∃ возможность перенумеровать все элементы {E}, скорость поиска — константа: массив/list из N True/False (принадлежит ли k-й элемент хранилищу)

• Если N велико, но ∃ однозначная хеш-функция — та же структура, только из хешей

• Когда хеш-функция неоднозначна (всегда), возможны коллизии

  • ⇒ хранить сам элемент для проверки, равны или элементы, если равны хеши.
  • Обрабатывать коллизии и хранить несколько элементов с одинаковыми хешами (поиск по которым будет уже линеен по количеству коллизий)
    1. Либо хранить »ведро» (bucket) таких элементов

    2. Перехешировать: например, взять следующий слот, но лучше — куда-нибудь далеко (hash(x^hash(x)) или что-нибудь такое), особенно, если свойство «разброса» в исходной функции не соблюдается (

Множества и hash()

Множества в Python реализованы именно так.

• Функция hash(), её отличие от id()

• Только неизменяемые объекты (почему)

  • например, frozenset()

Элементы множества неупорядочены

Словари

Задача: хранить произвольные объекты, каждый из которых взаимно однозначно соответствует хорошо хешируемому ключу.

• просто list() (ключ — 0, 1, …)

• dict — как массив с константными элементами вместо индекса

• Задание и обращение к элементу
• Циклический констуктор

• Элементы словаря упорядочены по времени добавления

• Работа со словарём

• keys(), values(), items()

  • итератор из словаря

• До Python3.6 словари были неупорядочены — как множества; сейчас способ более хитрый (см. https://docs.python.org/3/whatsnew/3.6.html#whatsnew36-compactdict и далее по ссылкам)

Словари внутри Python:

• globals()/locals()

     1 >>> QQ
     2 Traceback (most recent call last):
     3   File "<stdin>", line 1, in <module>
     4 NameError: name 'QQ' is not defined
     5 >>> globals()
     6 {'__name__': '__main__', '__doc__': None, '__package__': None, '__loader__': <_frozen_importlib_external.SourceFileLoader object at 0x7f434c1b4190>, '__spec__': None, '__annotations__': {}, '__builtins__': <module 'builtins' (built-in)>, '__cached__': None, 'rlcompleter': <module 'rlcompleter' from '/usr/lib64/python3.7/rlcompleter.py'>}
     7 >>> globals()["QQ"]=100500
     8 >>> QQ
     9 100500
    10 >>> globals()
    11 {'__name__': '__main__', '__doc__': None, '__package__': None, '__loader__': <_frozen_importlib_external.SourceFileLoader object at 0x7f434c1b4190>, '__spec__': None, '__annotations__': {}, '__builtins__': <module 'builtins' (built-in)>, '__cached__': None, 'rlcompleter': <module 'rlcompleter' from '/usr/lib64/python3.7/rlcompleter.py'>, 'QQ': 100500}
  

• Именные параметры функции

     1 >>> def fun(*argp, **argn):
     2 ...     print(argp, argn)
     3 ...
     4 >>> fun(1,2,3,a=4,b=5)
     5 (1, 2, 3) {'a': 4, 'b': 5}
     6 
     7 >>> def fun(a=1, b=2):
     8 ...   print(a,b)
     9 ...
    10 >>> d = dict(a="QQ", b="PP")
    11 >>> fun(**d)
    12 QQ PP
    13 >>> d = {"a":"QQ", "b":"QKRQ"}
    14 >>> fun(**d)
    15 QQ QKRQ
  

• Ещё вкусности

(если успеем)

• collections.htmla и collections.html

• Мелкий изврат: def tree(): return defaultdict(tree) (тут)

Д/З

0. Прочитать про словари в учебнике и в документации

1. EJudge: DungeonMap 'Карта подземелья'

   Вводится карта проходимых в обе стороны тоннелей подземлья в виде строк, содержащих разделённые пробелом названия двух пещер, которые соединяет соответствующий тоннель. Две последние строки не содержат пробелов — это название входа в подземелье и название выхода. Вывести "YES", если из входа можно попасть в выход, и "NO" в противном случае. Пары могут повторяться или содержать одинаковые слова.

   Input:

   markers jumping
   jumping guinea
   skiing pre
   markers gauge
   skiing mpeg
   solar jackson
   skiing solar
   guinea gauge
   mpeg honor
   pre honor
   guinea gauge
   pre mpeg
   markers guinea
   markers gauge
   honor mpeg
   markers jumping
   skiing
   jumping

   Output:

   NO

   • генератор тестовых даных (вам понадобится google-10000-english.txt)

2. EJudge: FarGalaxy 'В далёкой галактике'

   Ввести построчно четвёрки вида «число число число слово», где первые три числа — это координаты галактики по имени «слово» (некоторые галактики могут называться одинаково, но координаты у всех разные). Последняя строка ввода не содержит пробелов и не учитывается. Вывести в алфавитном порядке имена любых двух наиболее удалённых друг от друга галактик.

   Input:

   35.764 -797.636 -770.320 almost
   88.213 -61.688 778.457 gene
   -322.270 -248.555 -812.730 trend
   721.262 630.355 968.287 dow
   -895.519 -970.173 97.282 non
   -561.036 -350.840 -723.149 disco
   -151.546 -900.962 -658.862 bidder
   -716.197 478.576 -695.843 hawaii
   -744.664 -173.034 -11.211 sad
   -999.968 990.467 650.551 erik
   .

   Output:

   almost erik

   • генератор тестовых даных (вам понадобится google-10000-english.txt)

3. EJudge: CheckHash 'Хороший ли хеш'

   Написать функцию checkhash(seq, f, mod), которой на вход подаётся последовательность неравных друг другу (это гарантируется) хешируемых объектов, хеш-функция и число mod. Функция формирует новую редуцированную хеш-функцию r()=f()%mod, и собирает статистику коллизий по каждому значению r() на исходной последовательности. checkhash(seq, f, mod) возвращает кортеж из двух элементов — наибольшее и наименьшее количество произошедших коллизий.

   Input:

   from math import *
   print(checkhash(range(-1000000,1000000,77),hash,128))
   print(checkhash(range(-1000000,1000000,77),lambda x: int(f"{sin(x+1):14.13f}"[-5:]),128))

   Output:

   (204, 202)
   (260, 112)

   • В примере используется питоновская функция hash(), котороая, как мы выяснили, при каджом новом запуске может возвращать иные значения. В тестах её нет.

   • В примере используется формула из лекции. Что-то с ней явно не так!