Да. Чтобы выполнить поиск по хэш-карте с добавлением 100 миллионов элементов, выполните следующие действия:
1) Рассчитать хеш объекта, который вы ищете.
2) Найдите это ведро
3) Найдите в этом ведре предмет.
(1) не зависит от размера хэш-карты или количества элементов в ней.
(2) - это O (1), при условии, что стандартная хеш-карта реализована в виде массива связанных списков.
(3) занимает количество времени, связанное с количеством элементов в сегменте, которое должно быть приблизительно (количество элементов, добавленных в хэш) / (количество элементов). Эта часть начнется с O (1), но будет очень медленно увеличиваться, так как количество предметов начинает значительно превышать количество ведер.
Практически для любых целей Hash Maps можно считать O (1) как для вставки, так и для извлечения, даже с очень большими наборами данных, если вы начинаете с достаточно большого количества сегментов.