Геш-таблиці

Структури даних і алгоритми в Python

Miriam Antona

Software engineer

Визначення

Пари ключ–значення

  lasagna: 14.75
  moussaka: 21.15
  sushi: 16.05

Майже в кожній мові програмування є вбудована геш-таблиця:
- hashes, hash maps, dictionaries, associative arrays
- Python: словники

Схематичне зображення порожньої геш-таблиці.

Схематичне зображення порожньої геш-таблиці. Ціна лазаньї вставлена на п'яту позицію.

Схематичне зображення геш-таблиці зі словами «Hash function» посередині стрілки, що відображає слово «Lasagna» зі значенням на п'ятій позиції.

Щоразу, коли застосовується геш-функція,
- має повертати те саме значення для того самого вводу

Схематичне зображення геш-таблиці з деякими значеннями.

Схематичне зображення геш-таблиці з деякими значеннями. Значення на п'ятій позиції позначено зеленим.

Геш-функції можуть повертати однаковий результат для різних ввідних даних
hash("moussaka") -> 1

Схематичне зображення геш-таблиці з деякими значеннями. Значення на першій позиції позначено жовтим.

my_empty_dictionary = {}

my_menu = {
    'lasagna': 14.75,
    'moussaka': 21.15,
    'sushi': 16.05
}

print(my_menu['sushi'])

16.05

print(my_menu['paella'])

Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: 'paella'

print(my_menu.get('paella'))

None

print(my_menu.items())

dict_items([('lasanga', 14.75), 
            ('moussaka', 21.15),
            ('sushi', 16.05)])

print(my_menu.keys())

dict_keys(['lasanga', 'moussaka', 'sushi'])

print(my_menu.values())

dict_values([14.75, 21.15, 16.05])

my_menu['samosas'] = 13

print(my_menu.items())

dict_items([('lasanga', 14.75), ('moussaka', 21.15), ('sushi', 16.05), ('samosas', 13)])

print(my_menu.get('sushi'))

16.05

my_menu['sushi'] = 20

print(my_menu.get('sushi'))

del my_menu

del my_menu["sushi"]

my_menu.clear()

for key, value in my_menu.items():
  print(f"\nkey: {key}")
  print(f"value: {value}")

key: lasagna
value: 14.75

key: moussaka
value: 21.15

key: sushi
value: 16.05

for dish in my_menu:
  print(dish)

lasagna
moussaka
sushi

for prices in my_menu.values():
  print(prices)

14.75
21.15
16.05

my_menu = {
  'sushi' : {
    'price' : 19.25,
    'best_served' : 'cold'
  },
  'paella' : {
    'price' : 15,
    'best_served' : 'hot'
  }
}

Структури даних і алгоритми в Python