Ошибки и недостатки (с объяснениями)
1) Отсутствует проверка остановки при полном цикле вставки — возможна бесконечная петля при заполненной таблице.
- В коде: цикл `while self.table[i] is not None:` не прерывается, если место не найдено. Надо проверять число занятых ячеек или вернуться в начальную позицию.
2) При вставке не проверяется совпадение ключа — приводит к дублированию ключей вместо обновления значения.
- Правильно: если встретили запись с тем же ключом, заменить значение.
3) При get не обрабатываются пустые ячейки и tombstone — попытка взять `self.table[i][0]` при `None` вызовет исключение. Также при отсутствии ключа код зациклится (если нет `None`).
- Нужно прерывать поиск, когда встречается пустая ячейка (означает, что ключа в цепочке нет) или после полного обхода.
4) Нет поддержки удаления (tombstone) — простое присваивание `None` при удалении ломает цепочки при открытой адресации и может сделать недоступными другие ключи, которые были перемещены вперёд.
- Требуется специальный маркер удалённой ячейки (tombstone), отличимый от `None`.
5) Нет расширения/сжатия таблицы — при росте загрузки производительность падает из‑за длинных проб и кластеризации.
- Нужно реорганизовывать (rehash) при достижении порога загрузки (например, $\alpha =0.7$).
6) Пробирование: простое линейное пробирование подвержено первичной кластеризации — для высоких нагрузок хуже, чем квадратичное или двойное хеширование.
- Рассмотреть квадратичное пробирование или двойное хеширование (второй хеш не должен быть кратен размеру).
7) Нет учёта сложности и пределов: средняя сложность поиска/вставки — $O(1)$ при разумной загрузке, но в худшем случае $O(n)$. Нужно поддерживать размер и пороги.
8) Небезопасные допущения о `hash`: в Python `hash()` может быть отрицательным, но выражение `hash(key) % size` корректно даёт неотрицательный остаток; можно явно использовать `hash(key) & (size-1)` только при размере — степень двойки.
Рекомендации по улучшению (кратко)
- Обновлять значение при совпадении ключа вместо вставки нового кортежа.
- При вставке использовать повторную запись в первую найденную tombstone, но продолжать поиск, чтобы не быть уверенным, что ключа нет.
- В методе поиска `get` прерывать при встрече `None` или после полного круга; бросать `KeyError` или возвращать `None` по контракту.
- Добавить метод `delete` который помечает ячейку tombstone (специальный объект).
- Поддерживать счётчик занятых ячеек `count` и порог загрузки $\alpha$ (например, $\alpha =0.7$); при `count / size > \alpha` — увеличить `size` (обычно в 2 раза) и выполнить rehash всех живых пар.
- Рассмотреть другие стратегии пробирования: квадратичное или двойное (второй хеш должен быть относительно размера). Для двойного хеширования шаг рассчитывают как $step=1+(hash2(key)\mathrm{mod}(size-1))$.
- Выбирать размер таблицы как простое число или степень двойки в зависимости от выбранного хеширования.
Пример исправленного, достаточно простого варианта (линейное пробирование, tombstone, resize)
```python
class HashTable:
_TOMBSTONE = object()
def __init__(self, size=8, load_factor=0.7):
self.size = size
self.table = [None] * size
self.count = 0 # количество реальных элементов
self.load_factor = load_factor
def _index(self, key):
return hash(key) % self.size # можно оставить: Python % даёт неотрицательный остаток
def _resize(self, new_size):
old = [item for item in self.table if item is not None and item is not self._TOMBSTONE]
self.size = new_size
self.table = [None] * new_size
self.count = 0
for k, v in old:
self.insert(k, v)
def insert(self, key, value):
if (self.count + 1) / self.size > self.load_factor:
self._resize(self.size * 2)
i = self._index(key)
first_tombstone = None
while True:
slot = self.table[i]
if slot is None:
# вставляем в первую tombstone если была, иначе сюда
target = first_tombstone if first_tombstone is not None else i
self.table[target] = (key, value)
self.count += 1
return
if slot is self._TOMBSTONE:
if first_tombstone is None:
first_tombstone = i
else:
k, _ = slot
if k == key:
# обновление существующего ключа
self.table[i] = (key, value)
return
i = (i + 1) % self.size
def get(self, key):
i = self._index(key)
steps = 0
while steps < self.size:
slot = self.table[i]
if slot is None:
raise KeyError(key)
if slot is not self._TOMBSTONE:
k, v = slot
if k == key:
return v
i = (i + 1) % self.size
steps += 1
raise KeyError(key)
def delete(self, key):
i = self._index(key)
steps = 0
while steps < self.size:
slot = self.table[i]
if slot is None:
raise KeyError(key)
if slot is not self._TOMBSTONE:
k, _ = slot
if k == key:
self.table[i] = self._TOMBSTONE
self.count -= 1
return
i = (i + 1) % self.size
steps += 1
raise KeyError(key)
```
Ключевые замечания к этому варианту:
- Используется tombstone, чтобы корректно сохранять цепочки при удалении.
- При вставке обновляется существующий ключ; tombstone запоминается и при отсутствии ключа вставка может использовать её.
- Выполняется расширение при достижении порога загрузки.
- Поиск прерывается при встрече `None` или после полного числа шагов (не даёт бесконечности).
Дополнительные улучшения
- Заменить линейное пробирование на квадратичное или двойное хеширование для уменьшения кластеризации.
- Хранить мощность таблицы как степень двойки и использовать операцию побитового "и" для ускорения индексации, если выбран соответствующий шаг хеширования.
- Для многопоточной среды — добавить синхронизацию.
Кратко о сложностях: при разумной загрузке операции вставки/поиска — в среднем $O(1)$, в худшем случае $O(n)$.