Как се извършва търсенето на елемент в структурата HashSet и каква е нейната времева сложност?

HashSet се базира на хеш таблица. При търсене на елемент първо се изчислява неговият хеш код, след което се определя индексът на кофата (bucket) в масива. След това се търси елементът вътре в тази кофа, обикновено чрез сравнение с equals. Времевата сложност на търсенето в HashSet в средния случай е O(1), тоест константно време, при условие на равномерно разпределение на хешовете и малко колизии.