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

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


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

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


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


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

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

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

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


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


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


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

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


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

словник

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

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

new={}

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

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

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

dict.items() - містить перелік пар ключ-значення

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

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

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

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

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

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

Вхідні дані:

s={"яблуко":['malum', 'pomum', 'popula'],"фрукт" : ['baca', 'bacca', 'popum'],"покарання" : ['malum', 'multa']}

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

baca - фрукт

bacca - фрукт

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

multa - покарання

pomum - яблуко

popula - яблуко

popum - фрукт

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

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)

Остання зміна: неділя 29 вересня 2019 7:23