Словари и хэш-таблицы
Основы работы со словарями
Словарь (ассоциативный массив, отображение) — это структура данных, которая хранит пары «ключ-значение». В Python словари реализованы с помощью хэш-таблиц, что обеспечивает быстрый доступ к элементам.
Пример структуры словаря: пары «ключ-значение»
Основные операции со словарями
Создание и доступ
# Создание словаря
student = {
"name": "Alice",
"age": 25,
"city": "Moscow"
}
# Доступ к элементам
print(student["name"]) # Alice
print(student.get("age")) # 25
# Добавление/изменение элемента
student["grade"] = "A" # Добавляем новую пару
student["age"] = 26 # Изменяем существующее значение
# Проверка наличия ключа
if "city" in student:
print("Город указан")
# Удаление элемента
del student["city"]Методы словарей
student = {"name": "Alice", "age": 25, "city": "Moscow"}
# Получение всех ключей
keys = student.keys()
print(keys) # dict_keys(['name', 'age', 'city'])
# Получение всех значений
values = student.values()
print(values) # dict_values(['Alice', 25, 'Moscow'])
# Получение всех пар ключ-значение
items = student.items()
print(items) # dict_items([('name', 'Alice'), ('age', 25), ('city', 'Moscow')])
# Удаление и возврат элемента
age = student.pop("age")
print(age) # 25
# Очистка словаря
student.clear()
print(student) # {}Хэш-таблицы: принцип работы
Хэш-таблица — это структура данных, которая реализует ассоциативный массив. Она использует хэш-функцию для преобразования ключа в индекс массива, где хранится значение.
Принцип работы хэш-таблицы: ключ → хэш-функция → индекс → значение
# Простая реализация хэш-таблицы
class HashTable:
def __init__(self, size):
self.size = size
self.table = [[] for _ in range(size)]
def _hash(self, key):
# Простая хэш-функция: сумма кодов символов по модулю размера таблицы
return sum(ord(char) for char in str(key)) % self.size
def put(self, key, value):
index = self._hash(key)
# Проверяем, не существует ли уже такой ключ
for i, (k, v) in enumerate(self.table[index]):
if k == key:
self.table[index][i] = (key, value)
return
# Если ключ не найден, добавляем новую пару
self.table[index].append((key, value))
def get(self, key):
index = self._hash(key)
for k, v in self.table[index]:
if k == key:
return v
return None
# Пример использования
ht = HashTable(10)
ht.put("name", "Alice")
ht.put("age", 25)
print(ht.get("name")) # Alice
print(ht.get("age")) # 25Построение алфавитно-частотного словаря
Алфавитно-частотный словарь показывает, сколько раз каждый символ встречается в тексте. Это полезно для анализа текста, сжатия данных и криптографии.
def build_frequency_dict(text):
freq_dict = {}
for char in text:
# Приводим символ к нижнему регистру для игнорирования регистра
char_lower = char.lower()
if char_lower.isalpha(): # учитываем только буквы
if char_lower in freq_dict:
freq_dict[char_lower] += 1
else:
freq_dict[char_lower] = 1
return freq_dict
# Пример использования
text = "Hello World! Hello Python!"
frequency = build_frequency_dict(text)
# Вывод результатов в отсортированном виде
for char in sorted(frequency.keys()):
print(f"'{char}': {frequency[char]}")
# Вывод:
# 'd': 1
# 'e': 2
# 'h': 3
# 'l': 5
# 'n': 2
# 'o': 4
# 'p': 1
# 'r': 1
# 't': 2
# 'w': 1
# 'y': 1Визуализация частотного словаря для текста «Hello World»
# Улучшенная версия с использованием defaultdict
from collections import defaultdict
def build_frequency_dict_improved(text):
freq_dict = defaultdict(int)
for char in text:
char_lower = char.lower()
if char_lower.isalpha():
freq_dict[char_lower] += 1
return freq_dict
# Еще более краткая версия с использованием Counter
from collections import Counter
def build_frequency_dict_counter(text):
# Фильтруем только буквы и приводим к нижнему регистру
filtered_chars = [char.lower() for char in text if char.isalpha()]
return Counter(filtered_chars)
# Пример использования
text = "Hello World! Hello Python!"
frequency = build_frequency_dict_counter(text)
print(frequency) # Counter({'l': 5, 'o': 4, 'h': 3, 'e': 2, 'n': 2, 't': 2, 'd': 1, 'w': 1, 'r': 1, 'p': 1, 'y': 1})Сравнение структур данных
| Структура | Вставка | Поиск | Удаление | Применение |
|---|---|---|---|---|
| Список | O(1) (в конец) | O(n) | O(n) | Последовательности элементов |
| Множество | O(1) | O(1) | O(1) | Уникальные элементы, проверка принадлежности |
| Словарь | O(1) | O(1) | O(1) | Ассоциативные массивы, ключ-значение |
Заключение
Словари и хэш-таблицы — мощные структуры данных, которые обеспечивают эффективное хранение и доступ к данным по ключу. Понимание их работы важно для решения многих задач в программировании и для успешной сдачи ЕГЭ по информатике.
Алфавитно-частотный словарь — практическое применение словарей для анализа текста. Этот навык полезен не только для экзамена, но и для реальных задач обработки текстовой информации.