Какая сложность операций в Hashtable

Операции put(), get(), remove() в Hashtable имеют среднюю сложность O(1) (амортизированное время). В худшем случае (при коллизиях) сложность может деградировать до O(n) из-за цепочек в корзинах (реализация через LinkedList или TreeNode в Java 8+).

Пример:

Hashtable<String, Integer> table = new Hashtable<>();
table.put("key", 42);  // O(1) в среднем
int value = table.get("key");  // O(1) в среднем
table.remove("key");  // O(1) в среднем

Нюансы:

• Синхронизированность Hashtable добавляет накладные расходы.
• При плохой хеш-функции (hashCode()) коллизии учащаются, ухудшая производительность.
• В Java 8 при большом количестве коллизий корзины переходят с LinkedList на TreeNode, улучшая худший случай до O(log n).

Для несинхронизированных сценариев лучше использовать HashMap.