fork download
copy 
  1. class HashNode:
  2.     def __init__(self, key, value):
  3.         self.key = key
  4.         self.value = value
  5.         self.next = None
  6.  
  7. class HashMap:
  8.     """
  9.     Ассоциативный массив на основе хеш-таблицы.
  10.  
  11.     Разрешение коллизий: метод цепочек.
  12.     Операции:
  13.         - put: добавить/обновить элемент
  14.         - get: получить элемент
  15.         - remove: удалить элемент (опционально)
  16.  
  17.     Хеш-функция: используется встроенная hash() с модулем.
  18.     """
  19.     def __init__(self, capacity=10):
  20.         self.capacity = capacity
  21.         self.table = [None] * capacity
  22.         self._size = 0
  23.         self.load_factor = 0.75
  24.  
  25.     def _hash(self, key):
  26.         """Хеш-функция."""
  27.         return hash(key) % self.capacity
  28.  
  29.     def _resize(self):
  30.         """Увеличить размер таблицы при переполнении."""
  31.         if self._size / self.capacity > self.load_factor:
  32.             old_table = self.table
  33.             self.capacity *= 2
  34.             self.table = [None] * self.capacity
  35.             self._size = 0
  36.  
  37.             for head in old_table:
  38.                 curr = head
  39.                 while curr:
  40.                     self.put(curr.key, curr.value)
  41.                     curr = curr.next
  42.  
  43.     def put(self, key, value):
  44.         """
  45.         Добавить или обновить элемент.
  46.  
  47.         Время: O(1) в среднем, O(n) в худшем.
  48.         """
  49.         index = self._hash(key)
  50.         curr = self.table[index]
  51.  
  52.         # Проверяем, есть ли уже такой ключ
  53.         while curr:
  54.             if curr.key == key:
  55.                 curr.value = value  # Обновляем значение
  56.                 return
  57.             curr = curr.next
  58.  
  59.         # Добавляем новый узел в начало цепочки
  60.         new_node = HashNode(key, value)
  61.         new_node.next = self.table[index]
  62.         self.table[index] = new_node
  63.         self._size += 1
  64.  
  65.         self._resize()
  66.  
  67.     def get(self, key, default=None):
  68.         """
  69.         Получить значение по ключу.
  70.  
  71.         Время: O(1) в среднем.
  72.         """
  73.         index = self._hash(key)
  74.         curr = self.table[index]
  75.         while curr:
  76.             if curr.key == key:
  77.                 return curr.value
  78.             curr = curr.next
  79.         return default
  80.  
  81.     def remove(self, key):
  82.         """
  83.         Удалить элемент по ключу.
  84.  
  85.         Время: O(1) в среднем.
  86.         Возвращает: True если удалено, False если не найдено.
  87.         """
  88.         index = self._hash(key)
  89.         curr = self.table[index]
  90.         prev = None
  91.  
  92.         while curr:
  93.             if curr.key == key:
  94.                 if prev:
  95.                     prev.next = curr.next
  96.                 else:
  97.                     self.table[index] = curr.next
  98.                 self._size -= 1
  99.                 return True
  100.             prev = curr
  101.             curr = curr.next
  102.         return False
  103.  
  104.     def keys(self):
  105.         """Вернуть все ключи."""
  106.         keys = []
  107.         for head in self.table:
  108.             curr = head
  109.             while curr:
  110.                 keys.append(curr.key)
  111.                 curr = curr.next
  112.         return keys
  113.  
  114.     def size(self):
  115.         return self._size
  116.  
  117.     def __str__(self):
  118.         items = []
  119.         for head in self.table:
  120.             curr = head
  121.             while curr:
  122.                 items.append(f"{curr.key}: {curr.value}")
  123.                 curr = curr.next
  124.         return "{" + ", ".join(items) + "}"
  125.  
  126. # Тесты
  127. hash_map = HashMap()
  128. hash_map.put('apple', 1)
  129. hash_map.put('banana', 2)
  130. hash_map.put('cherry', 3)
  131. hash_map.put('date', 4)
  132. hash_map.put('apple', 10)  # Обновление
  133. print(hash_map)  # {apple: 10, date: 4, banana: 2, cherry: 3}
  134. print(hash_map.get('banana'))  # 2
  135. print(hash_map.get('grape', 0))  # 0
  136. print(hash_map.remove('date'))  # True
  137. print(hash_map)  # {apple: 10, banana: 2, cherry: 3}
  138. print(hash_map.size())  # 3
  139.  
  140. # Проверка хеш-коллизий и расширения
  141. for i in range(20):
  142.     hash_map.put(f'key{i}', i)
  143. print(hash_map.size())  # 23 (3 + 20)
  144. print(f"Capacity: {hash_map.capacity}")  # Должно увеличиться
Success #stdin #stdout 0.07s 14012KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
{date: 4, apple: 10, banana: 2, cherry: 3}
2
0
True
{apple: 10, banana: 2, cherry: 3}
3
23
Capacity: 40
https://ideone.com/7uAksU
language:
Python 3 (python  3.12)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!