Как достигается сложность операций в Hashtable близкой к O(1)

Hashtable достигает O(1) сложности за счет хеширования и правильного размера массива. Ключевые моменты:

1. Хеш-функция равномерно распределяет элементы по бакетам, минимизируя коллизии
2. Размер массива выбирается простым числом для лучшего распределения
3. Рехеширование при достижении load factor (по умолчанию 0.75)

Пример:

Hashtable<String, Integer> table = new Hashtable<>();
table.put("key", 42); // O(1) в лучшем случае

В худшем случае (все ключи в одном бакете) сложность деградирует до O(n). Для предотвращения Java 8+ использует сбалансированные деревья вместо списков при большом количестве коллизий.