class HashNode:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.next = None

class HashMap:
    """
    Ассоциативный массив на основе хеш-таблицы.
    
    Разрешение коллизий: метод цепочек.
    Операции:
        - put: добавить/обновить элемент
        - get: получить элемент
        - remove: удалить элемент (опционально)
    
    Хеш-функция: используется встроенная hash() с модулем.
    """
    def __init__(self, capacity=10):
        self.capacity = capacity
        self.table = [None] * capacity
        self._size = 0
        self.load_factor = 0.75
    
    def _hash(self, key):
        """Хеш-функция."""
        return hash(key) % self.capacity
    
    def _resize(self):
        """Увеличить размер таблицы при переполнении."""
        if self._size / self.capacity > self.load_factor:
            old_table = self.table
            self.capacity *= 2
            self.table = [None] * self.capacity
            self._size = 0
            
            for head in old_table:
                curr = head
                while curr:
                    self.put(curr.key, curr.value)
                    curr = curr.next
    
    def put(self, key, value):
        """
        Добавить или обновить элемент.
        
        Время: O(1) в среднем, O(n) в худшем.
        """
        index = self._hash(key)
        curr = self.table[index]
        
        # Проверяем, есть ли уже такой ключ
        while curr:
            if curr.key == key:
                curr.value = value  # Обновляем значение
                return
            curr = curr.next
        
        # Добавляем новый узел в начало цепочки
        new_node = HashNode(key, value)
        new_node.next = self.table[index]
        self.table[index] = new_node
        self._size += 1
        
        self._resize()
    
    def get(self, key, default=None):
        """
        Получить значение по ключу.
        
        Время: O(1) в среднем.
        """
        index = self._hash(key)
        curr = self.table[index]
        while curr:
            if curr.key == key:
                return curr.value
            curr = curr.next
        return default
    
    def remove(self, key):
        """
        Удалить элемент по ключу.
        
        Время: O(1) в среднем.
        Возвращает: True если удалено, False если не найдено.
        """
        index = self._hash(key)
        curr = self.table[index]
        prev = None
        
        while curr:
            if curr.key == key:
                if prev:
                    prev.next = curr.next
                else:
                    self.table[index] = curr.next
                self._size -= 1
                return True
            prev = curr
            curr = curr.next
        return False
    
    def keys(self):
        """Вернуть все ключи."""
        keys = []
        for head in self.table:
            curr = head
            while curr:
                keys.append(curr.key)
                curr = curr.next
        return keys
    
    def size(self):
        return self._size
    
    def __str__(self):
        items = []
        for head in self.table:
            curr = head
            while curr:
                items.append(f"{curr.key}: {curr.value}")
                curr = curr.next
        return "{" + ", ".join(items) + "}"

# Тесты
hash_map = HashMap()
hash_map.put('apple', 1)
hash_map.put('banana', 2)
hash_map.put('cherry', 3)
hash_map.put('date', 4)
hash_map.put('apple', 10)  # Обновление
print(hash_map)  # {apple: 10, date: 4, banana: 2, cherry: 3}
print(hash_map.get('banana'))  # 2
print(hash_map.get('grape', 0))  # 0
print(hash_map.remove('date'))  # True
print(hash_map)  # {apple: 10, banana: 2, cherry: 3}
print(hash_map.size())  # 3

# Проверка хеш-коллизий и расширения
for i in range(20):
    hash_map.put(f'key{i}', i)
print(hash_map.size())  # 23 (3 + 20)
print(f"Capacity: {hash_map.capacity}")  # Должно увеличиться