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

Hash-функция

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

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

Замечания:

Хеш-таблицы

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

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

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

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

Словари

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

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

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

Д/З

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

  2. 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
  3. 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
  4. 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(), котороая, как мы выяснили, при каджом новом запуске может возвращать иные значения. В тестах её нет.

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

LecturesCMC/PythonIntro2019/07_HashDictionary (last edited 2019-11-05 11:33:17 by FrBrGeorge)