Ինչպե՞ս է որոշվում HashSet-ի իրականացման մեջ տարրերի որոնման արագությունը։

Java-յի HashSet-ի իրականացման ժամանակ, տարրերի որոնման արագությունը որոշվում է 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-ով