Структури даних. Хеш-таблиці та словники

Пригадаємо, що у різних структурах даних є різна ефективність пошуку: наприклад пошук в упорядкованому списку відбувається з ефективністю O (log n), у невпорядкованому – O ( n ).

Це означає, що якщо асортимент магазину зберігається у списку, і покупець запитує вартість того чи іншого товару, то на пошук відповіді потрібно буде затратити відповідну кількість часу (менше, якщо це впорядкований список, більше - якщо невпорядкований). Водночас, додавання нового товару в асортимент теж займатиме різну кількість часу - менше для невпорядкованого списку, і більше - для впорядкованого.

Але чи не можна зробити так, щоб взагалі не потрібно було шукати у списку? Наприклад, якщо у нас є помічниця Меггі, яка знає всі ціни напам'ять, нам достатньо її запитати і отримати миттєву відповідь! Залишається створити таку Меггі у формі алгоритму.

Це називається хеш-функція. Принцип її роботи наступний: на вході маємо певний текст, застосовуємо математичні перетворення і одержуємо число. 

Для коректної роботи функція має виконувати дві умови:

- Послідовність: якщо на вході певне слово, то на виході одне і те ж число щоразу при виклику цієї функції.

- Унікальність: одне і те ж число не може бути результатом перетворення різних вхідних слів.

Що це нам дасть? Ми зможемо зберігати інформацію в пам'яті наступним чином. Створимо порожній масив/список (далі дізнаєтесь, що насправді - словник):

Оскільки слово "апельсин" хеш-функція перетворює на число 3, ми запишемо вартість апельсинів у цю комірку!

Аналогічно заповнимо решту цін асортименту магазину:

Зверніть увагу - у даному випадку не зберігається сам асортимент, він по суті "прихований" хеш-функцією, завдяки якій назва товару перетворюється на унікальне число (яке стає індексом у списку).

Для того, щоб дізнатись вартість певного товару, застосовуємо до його назви хеш-функцію, і виводимо значення з відповідної комірки.

У Python хеш-функцію реалізує структура даних, яка називається словник.

Словник - структура даних, яка містить пари елементів: ключі та їх значення.

Створення словника - задаємо його назву і порожні фігурні дужки.

new={}

Додавання значення у словник відбувається парою ключ-значення.

new[ключ]=значення

Усі ключі словника знаходяться у списку new.keys() ,а значення - у списку new.values().

Задача 1. Дано список 20 випадкових чисел. Знайти частоту кожного з елементів списку.

Розглядаючи список (перебираючи усі його елементи), ми будемо перевіряти наступне. Якщо елемент списку вже є у словнику (як ключ), то до його значення треба додати одиницю, а якщо ще немає, то внести у словник новий ключ зі значенням 1.

import random
spysok=[]
for nomer in range(20):
    k=random.randint(0,10)
    spysok.append(k)
print(spysok)

new={}
for element in spysok:
    if element not in new:
        new[element]=1
    else:
        new[element]=new[element]+1
print(new)

Показати код/Сховати код^

Задача 2. Сортування словника

print(sorted(hogwarts.keys()))
print(sorted(hogwarts.values()))

Показати код/Сховати код^

Задача 3. Виведення відсортованого словника

За ключами
print(sorted(hogwarts.items()))
[('gryffindor', 'lion'), ('hufflepuff', 'badger'), ('ravenclaw', 'eagle'), ('slytherin', 'snake')]

За значеннями
hufflepuff badger
ravenclaw eagle
gryffindor lion
slytherin snake
Для тварини у списку сортованих значень словника
Для дому в Хогвартсі
Якщо значення дому == тварині
Друкувати дім, тварину

Показати код/Сховати код^

Задача 4. Відсортувати список за довжиною слів у ньому ['a', 'dd', 'bbb','cccc']

Програма 
spysok = ['a', 'dd', 'bbb','cccc']
spysok.sort()
print(spysok)
Дає результат
['a', 'bbb', 'cccc', 'dd']
Потрібно відсортувати за довжиною рядка:
['a', 'dd', 'bbb', 'cccc']
Потрібно створити словник:
Значенням зі списку має відповідати кількість букв
Відсортувати за кількістю букв
Вивести значення відповідно до сортування

Показати код/Сховати код^

Задача 5. Дано україно-латинський словник. Перетворити його на латино-український.

Вхідні дані:

Вихідні дані:

baca - фрукт

bacca - фрукт

malum - яблуко, покарання

multa - покарання

pomum - яблуко

popula - яблуко

popum - фрукт

s={"яблуко":['malum', 'pomum', 'popula'],"фрукт" : ['baca', 'bacca', 'popum'],"покарання" : ['malum', 'multa']}
print(s.keys())
print(s.values())
for element in s.values():
    for e in element:
        for kluch in s.keys():
            if e in s[kluch]:
                print(e,kluch)

Показати код/Сховати код^

Де використовуються хеш-таблиці

DNS-сервери:

Системи, де не можна допустити дублікат, наприклад вибори. Якщо громадянин вже проголосував, він заноситься у словник, і більше до голосування не допускається:

Забезпечення роботи кеш-пам'яті: якщо користувач нещодавно відвідував веб-сторінку, то завантажиться її локальна копія, інакше потрібно звернутись до сервера.

hogwarts={}
hogwarts['gryffindor']='lion'
hogwarts['hufflepuff']='badger'
hogwarts['ravenclaw']='eagle'
hogwarts['slytherin']='snake'
for animal in sorted(hogwarts.values()):
    for house in hogwarts:
        if hogwarts[house]==animal:
            print(house, animal)



spysok = ['a', 'dd', 'bbb','cccc']

slovnyk={}
for element in spysok:
    slovnyk[element]=len(element)

print(slovnyk)

new=[]
new=slovnyk.values()
print(sorted(slovnyk.values()))

for chyslo in sorted(slovnyk.values()):
    for element in slovnyk.keys():
        if slovnyk[element]==chyslo:
            print(element)