Хеш-таблицы

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

Miriam Antona

Software engineer

Определение

  • Хранит коллекцию элементов

  • Пары ключ-значение

      lasagna: 14.75
  moussaka: 21.15
  sushi: 16.05

  • Почти в каждом языке программирования есть встроенная хеш-таблица:

    • хеши, хеш-карты, словари, ассоциативные массивы
    • Python: словари
Структуры данных и алгоритмы на Python

Структура

  • Каждая позиция: слот/корзина

Схематическое изображение пустой хеш-таблицы.

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

Хеш-функции

Схематическое изображение пустой хеш-таблицы. Цена лазаньи вставлена на пятую позицию.

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

Хеш-функции

Схематическое изображение хеш-таблицы с надписью «Хеш-функция» в середине стрелки, отображающей слово «Lasagna» на пятую позицию.

  • При каждом применении хеш-функции
    • должно возвращаться одно и то же значение для одного и того же входа
Структуры данных и алгоритмы на Python

Поиск

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

  • Найти «lasagna»
    • hash("lasagna") -> 5
Структуры данных и алгоритмы на Python

Поиск

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

  • Найти «lasagna»
    • hash("lasagna") -> 5
    • вернуть 14,75
  • $O(1)$
Структуры данных и алгоритмы на Python

Коллизии

  • Хеш-функции могут возвращать одинаковый результат для разных входных данных
  • hash("moussaka") -> 1

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

  • вставить: moussaka -> 21,15
  • Коллизия!
    • необходимо разрешить
    • существует несколько техник
Структуры данных и алгоритмы на Python

Словарь Python

  • Пустой словарь
my_empty_dictionary = {}
  • Словарь с элементами
my_menu = {
    'lasagna': 14.75,
    'moussaka': 21.15,
    'sushi': 16.05
}
Структуры данных и алгоритмы на Python

Словарь Python — метод get

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
Структуры данных и алгоритмы на Python

Словарь Python — items, keys и values

  • Получить элементы
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])
Структуры данных и алгоритмы на Python

Словарь Python — добавление элементов

my_menu['samosas'] = 13

print(my_menu.items())

dict_items([('lasanga', 14.75), ('moussaka', 21.15), ('sushi', 16.05), ('samosas', 13)])
Структуры данных и алгоритмы на Python

Словарь Python — изменение элементов

print(my_menu.get('sushi'))

16.05

my_menu['sushi'] = 20

print(my_menu.get('sushi'))

20
Структуры данных и алгоритмы на Python

Словарь Python — удаление элементов

  • Полностью удаляет словарь
del my_menu
  • Удаляет пару ключ-значение
del my_menu["sushi"]
  • Очищает словарь
my_menu.clear()
Структуры данных и алгоритмы на Python

Словарь Python — перебор элементов

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
Структуры данных и алгоритмы на Python

Словарь Python — перебор элементов

for dish in my_menu:
  print(dish)

lasagna
moussaka
sushi

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

14.75
21.15
16.05
Структуры данных и алгоритмы на Python

Словарь Python — вложенные словари

  • Вложенный словарь
my_menu = {
  'sushi' : {
    'price' : 19.25,
    'best_served' : 'cold'
  },
  'paella' : {
    'price' : 15,
    'best_served' : 'hot'
  }
}
Структуры данных и алгоритмы на Python

Давайте потренируемся!

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

Preparing Video For Download...