Нет разницы между асимптотиками Hashtable и HashMap, и они являются предсказуемым ожидаемым амортизированным O(1) для put и ожидаемым O(1) для get, при условии, что у вас есть хороший хеш-функция.
Самым большим отличием является то, что Hashtable включает в себя бесполезные накладные расходы на синхронизацию из параллельных потоков, что а) вам обычно не нужно, и б) выполняется более эффективно ConcurrentHashMap. Вы в принципе никогда не должны использовать Hashtable в новом коде.