Алгоритмы. Хеш-таблица

Пример 1

# Пример реализации телефонной книги
phonebook = {}

# Добавление контактов
phonebook["Мама"] = "+7-900-111-22-33"
phonebook["Друг Саша"] = "+7-900-444-55-66"
phonebook["Работа"] = "+7-495-777-88-99"

# Быстрый поиск по имени
print(f"Телефон мамы: {phonebook['Мама']}")
# Вывод: Телефон мамы: +7-900-111-22-33

# Проверка наличия контакта
if "Брат" in phonebook:
    print(phonebook["Брат"])
else:
    print("Контакт не найден")
# Вывод: Контакт не найден

# Обновление номера
phonebook["Мама"] = "+7-900-999-00-00"
print(f"Новый телефон мамы: {phonebook['Мама']}")

Пример 2

# Кэширование результатов вычислений с использованием хеш-таблицы
cache = {}

def expensive_calculation(n):
    """Функция с имитацией сложных вычислений"""
    # Проверяем, есть ли результат в кэше
    if n in cache:
        print(f"Беру из кэша для {n}")
        return cache[n]
    
    # Вычисляем (предполагаем, что операция дорогая)
    print(f"Вычисляю для {n}")
    result = n * n * n  # Куб числа
    
    # Сохраняем в кэш
    cache[n] = result
    return result

# Первый вызов — вычисление
print(expensive_calculation(5))  # Вывод: Вычисляю для 5 \n 125

# Второй вызов — результат берётся из кэша
print(expensive_calculation(5))  # Вывод: Беру из кэша для 5 \n 125

Пример 3

# Упрощенная реализация хеш-таблицы с методом цепочек
class SimpleHashTable:
    def __init__(self, size=10):
        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 insert(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
    
    def display(self):
        for i, bucket in enumerate(self.table):
            if bucket:
                print(f"[{i}]: {bucket}")

# Использование
ht = SimpleHashTable(size=5)
ht.insert("apple", 50)
ht.insert("grape", 60)  # Может попасть в ту же ячейку!
ht.insert("banana", 30)

print("Структура таблицы:")
ht.display()
# Возможный вывод:
# [1]: [('banana', 30)]
# [3]: [('apple', 50), ('grape', 60)]

print(f"\nЦена apple: {ht.get('apple')}")
print(f"Цена grape: {ht.get('grape')}")

Пример 4

# Пример: Поиск первого неповторяющегося символа
def first_unique_char(text):
    char_count = {}
    for char in text:
        char_count[char] = char_count.get(char, 0) + 1
    for char in text:
        if char_count[char] == 1:
            return char
    return None

text = "aabbccddeef"
result = first_unique_char(text)
print(f"Первый уникальный символ в '{text}': {result}")
# Вывод: Первый уникальный символ в 'aabbccddeef': f
# Пример: Группировка анаграмм
def group_anagrams(words):
    anagram_groups = {}
    for word in words:
        sorted_word = ''.join(sorted(word))
        if sorted_word not in anagram_groups:
            anagram_groups[sorted_word] = []
        anagram_groups[sorted_word].append(word)
    return list(anagram_groups.values())

words = ["eat", "tea", "tan", "ate", "nat", "bat"]
groups = group_anagrams(words)
print("Группы анаграмм:")
for group in groups:
    print(group)
# Вывод:
# ['eat', 'tea', 'ate']
# ['tan', 'nat']
# ['bat']
# Пример: Проверка, является ли строка перестановкой другой
def are_permutations(str1, str2):
    if len(str1) != len(str2):
        return False
    char_count = {}
    for char in str1:
        char_count[char] = char_count.get(char, 0) + 1
    for char in str2:
        if char not in char_count:
            return False
        char_count[char] -= 1
        if char_count[char] < 0:
            return False
    return True

print(are_permutations("listen", "silent"))  # True
print(are_permutations("hello", "world"))    # False

Пример 5

# Расширенная реализация хеш-таблицы с методом цепочек
class HashTableWithChaining:
    def __init__(self, size=10):
        self.size = size
        self.table = [[] for _ in range(size)]
    
    def _hash(self, key):
        return hash(key) % self.size
    
    def insert(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)
                print(f"Обновлено: {key} → {value} в ячейке [{index}]")
                return
        self.table[index].append((key, value))
        print(f"Добавлено: {key} → {value} в ячейку [{index}]")
    
    def get(self, key):
        index = self._hash(key)
        for k, v in self.table[index]:
            if k == key:
                return v
        return None
    
    def delete(self, key):
        index = self._hash(key)
        for i, (k, v) in enumerate(self.table[index]):
            if k == key:
                del self.table[index][i]
                print(f"Удалено: {key} из ячейки [{index}]")
                return True
        return False
    
    def display(self):
        print("\n=== Структура хеш-таблицы ===")
        for i, bucket in enumerate(self.table):
            if bucket:
                print(f"[{i}]: {bucket}")
            else:
                print(f"[{i}]: пусто")

# Демонстрация работы
ht = HashTableWithChaining(size=5)
print("--- Вставка элементов ---")
ht.insert("apple", 50)
ht.insert("banana", 30)
ht.insert("grape", 60)
ht.insert("orange", 40)
ht.insert("melon", 35)
ht.display()