хеш-таблицы

Ассоциативный массив (словарь, map) — это абстрактный тип данных, хранящий пары «ключ-значение» с уникальными ключами. В Python эта структура реализована в виде словарей (dict).

Основные характеристики:

• Каждый ключ уникален в рамках структуры

• Значение извлекается по соответствующему ключу

• Нет порядка элементов (до Python 3.7) / сохранение порядка добавления (Python 3.7+)

• Нет доступа по индексу (только по ключу)

Хеш-таблица как реализация ассоциативного массива

Хеш-таблица — конкретная структура данных, реализующая ассоциативный массив. В Python словари реализованы с помощью оптимизированных хеш-таблиц.

Принцип работы:

1. Ключ проходит через хеш-функцию, которая преобразует его в числовой хеш

2. По этому хешу определяется позиция в массиве (индекс)

3. При коллизиях (одинаковые хеши для разных ключей) используются различные стратегии разрешения (цепочки, открытая адресация)

Сложность операций:

*Худший случай возможен при большом количестве коллизий. Колизией является, когда ключ является уникальным, но его хеш интерпритация совпадает с другим ключем. 

Пример кода:

class HashTable:
    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):
        """Вставка пары ключ-значение"""
        hash_key = self._hash(key)
        bucket = self.table[hash_key]
        
        # Проверка на существование ключа
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)  # Обновление значения
                return
        bucket.append((key, value))  # Добавление новой пары
    
    def get(self, key):
        """Получение значения по ключу"""
        hash_key = self._hash(key)
        bucket = self.table[hash_key]
        
        for k, v in bucket:
            if k == key:
                return v
        raise KeyError(key)
    
    def delete(self, key):
        """Удаление пары по ключу"""
        hash_key = self._hash(key)
        bucket = self.table[hash_key]
        
        for i, (k, v) in enumerate(bucket):
            if k == key:
                del bucket[i]
                return
        raise KeyError(key)
    
    def __str__(self):
        """Строковое представление"""
        return str(self.table)

# Пример использования
ht = HashTable()
ht.insert("apple", 10)
ht.insert("orange", 20)
ht.insert("banana", 30)

print(ht.get("apple"))   # 10
ht.insert("apple", 15)   # Обновление значения
print(ht.get("apple"))   # 15

ht.delete("orange")
print(ht)  # Выведет содержимое хеш-таблицы