Чӣ тавр суръати ҷустуҷӯи унсурҳо дар иҷрои HashSet муайян карда мешавад?

Дар реализацияи HashSet дар Java суръати ҷустуҷӯи элементҳо аз истифодаи дохилии HashMap муайян карда мешавад. HashSet элементҳоро ҳамчун калидҳо дар HashMap нигоҳ медорад, ва арзишҳо фиктив мебошанд.

Суръати ҷустуҷӯ вобаста аст ба:

• Функсияи hash-и объект: он объектро ба коди hash табдил медиҳад, ки ҷойгиршавиро дар массиви bucket-ҳо муайян мекунад.
• Коллизияҳо: агар чанд элемент ҳамон hash-ро дошта бошанд, онҳо ба як bucket меафтанд, ва ҷустуҷӯ ба таври хаттӣ дар асоси шумораи элементҳо дар он bucket мешавад.

Дар миёна, бо функсияи hash хуб ва сатҳи пасти коллизияҳо, ҷустуҷӯ дар HashSet як амалиёт O(1) (вақти доимӣ) аст. Агар коллизияҳо зиёд бошанд, вақт метавонад то O(n) бадтар шавад.

Масалан:

HashSet<String> set = new HashSet<>();
set.add("apple");
boolean exists = set.contains("apple"); // Ҷустуҷӯи зуд бо hash