Hashtable — реализация интерфейса Map, основанная на хеш-таблицах. Не гарантирует какое — то определенное время выполнения, но в среднем работает за O(1). Тут следует сказать, что хеш-таблицы имеют два важных параметра: capacity (максимальное количество элементов) и loadFactor (загруженность таблицы). При достижении количества реально существующих элементов в размере 0,75 от максимального происходит автоматическое увеличение максимального количество элементов, т.е самой таблицы. 0,75 это показатель по умолчанию, конечно вы можете изменить загруженность таблицы:

Кроме этого, существует класс HashMap, который имеет схожую функциональность, но при работе с потоками его лучше не использовать.

TreeMap — реализация интерфейса Map, основанная на деревьях. Как и в любом дереве операции взятия элемента по ключу, вставка или удаления происходят за O(logN). Пример использования TreeMap: