Javaдагы HashSet

Класс HashSetинтерфейсти ишке ашырат Set, хэш tableга негизделген жана ошондой эле инстанция менен колдоого алынат HashMap. Элементтер ирээтке келтирилбегендиктен HashSet, бир нече убакыт өткөндөн кийин элементтер бирдей тартипте болот деген кепилдик жок. Кошуу, жок кылуу жана издөө операциялары хэш-функция элементтерди “чакаларга” туура бөлүштүрсө, анда туруктуу убакытта аткарылат, алар кийинчерээк талкууланат. жөнүндө бир нече маанилүү пункттар HashSet:

• Анткени класс интерфейсти ишке ашырат Set, ал уникалдуу баалуулуктарды гана сактай алат;
• NULL маанилерин сактай алат;
• Элементтерди кошуу тартиби хэш-codeдун жардамы менен эсептелет;
• HashSetSerializableжана да ишке ашырат Cloneable.

Операциялардын туруктуу аткарылышын камсыз кылуу үчүн, менен иш-аракеттерге жумшалган убакыт + орнотулган инстанциянын "кубаттуулугундагы" HashSetэлементтердин санына түз пропорционалдуу болушу керек ("себеттердин" саны). Ошондуктан, өндүрүмдүүлүктү сактоо үчүн баштапкы кубаттуулукту өтө жогору (же жүктөө коэффициентин өтө төмөн) орнотпоо маанилүү. Баштапкы сыйымдуулук - хэш tableсындагы уячалардын баштапкы саны ("контенкалар"). Бардык уячалар толтурулган болсо, алардын саны автоматтык түрдө көбөйөт. Жүктөө коэффициенти анын кубаттуулугу автоматтык түрдө жогорулаганга чейин анын канчалык толушу мүмкүн экендигинин өлчөмү . Элементтердин саны баштапкы кубаттуулуктун жана жүктөө коэффициентинин көбөйтүлгөнүнөн көп болгондо, хэш tableсы кайрадан хэштирилет (элементтердин хэш-codeдору кайра эсептелет жана алынган маанилерге ылайык table кайра түзүлөт) жана саны андагы клеткалардын саны эки эсеге көбөйөт. Жүктөө коэффициенти = Таблицада сакталган элементтердин саны / tableнын хэш өлчөмү Мисалы, tableдагы уячалардын баштапкы саны 16 болсо, жүктөө коэффициенти 0,75 болсо, анда толтурулган уячалардын саны 12ге жеткенде, клеткалардын саны автоматтык түрдө көбөйөт. Жүктөө фактору жана баштапкы кубаттуулук - бул иштин натыйжалуулугуна таасир этүүчү эки негизги фактор . 0,75 жүк коэффициенти орточо жакшы аткарууну камсыз кылат. Эгерде бул параметр көбөйтүлсө, анда эс жүктөө азаят (анткени ал кайра хэштердин жана кайра куруулардын санын азайтат), бирок бул тиркеме жана издөө операцияларына таасирин тийгизет. Кайра хэширүүгө кеткен убакытты азайтуу үчүн, сиз туура баштапкы кубаттуулук параметрин тандап алышыңыз керек. Эгерде баштапкы кубаттуулук жүк коэффициентине бөлүнгөн элементтердин максималдуу санынан көп болсо, анда эч кандай кайра хэширлөө операциясы таптакыр болбойт. HashSetHashMapHashSetHashSetHashSetМаанилүү: HashSetкамтылган синхрондоштуруусу бар маалымат структурасы эмес, андыктан бир эле учурда анын үстүндө бир нече жиптер иштеп жатса жана алардын жок дегенде бири өзгөртүү киргизүүгө аракет кылып жатса, сырттан синхрондоштуруу мүмкүнчүлүгүн камсыз кылуу зарыл. Бул көбүнчө башка синхрондоштурулган an objectтин эсебинен жасалат HashSet. Эгерде андай an object жок болсо, анда Collections.synchronizedSet(). Бул учурда синхрондоштуруудан тышкары операцияларды алдын алуунун эң мыкты жолу HashSet.

Set s = Collections.synchronizedSet(new HashSet(...));

HashSet конструкторлору:

1. HashSet h = new HashSet(); - демейки конструктор. Демейки баштапкы кубаттуулугу 16, жүктөө коэффициенти 0,75.
2. HashSet h = new HashSet(int initialCapacity)– берилген баштапкы кубаттуулугу бар конструктор. Жүктөө коэффициенти – 0,75.
3. HashSet h = new HashSet(int initialCapacity, float loadFactor);— берилген баштапкы кубаттуулугу жана жүктөө коэффициенти менен конструктор.
4. HashSet h = new HashSet(Collection C)– башка коллекциянын элементтерин кошкон конструктор.

Төмөндөгү code кээ бир ыкмаларды көрсөтөт HashSet:

import java.util.*;

class Test
{
    public static void main(String[]args)
    {
        HashSet<String> h = new HashSet<String>();

        // Add elements to the HashSet using the add() method
        h.add("India");
        h.add("Australia");
        h.add("South Africa");
        h.add("India");// try to add another same element

        // Print the elements of the HashSet to the console
        System.out.println(h);
        System.out.println("List contains India or not:" +
                           h.contains("India"));

        // Remove elements from the set using the remove() method
        h.remove("Australia");
        System.out.println("List after removing Australia:"+h);

        // Loop through the elements of the HashSet using an iterator:
        System.out.println("Iterating over list:");
        Iterator<String> i = h.iterator();
        while (i.hasNext())
            System.out.println(i.next());
    }
}

Жыйынтык:

[South Africa, Australia, India]
List contains India or not:true
List after removing Australia:[South Africa, India]
Iterating over list:
South Africa
India

Интерфейсти ишке ашырган бардык класстар Setишке ашыруулар тарабынан ички колдоого алынат Map. HashSetколдонуп элементтерди сактайт HashMap. HashMapЭлемент кошуу үчүн элемент ачкыч-маани жуп катары көрсөтүлүшү керек болсо да , HashSetага маани гана кошулат. Чындыгында, биз өткөн маани HashSetan objectтин ачкычы болуп саналат HashMapжана маани катары константа колдонулат HashMap. Ошентип, ар бир ачкыч-маани жуптарында бардык ачкычтар бирдей мааниге ээ болот. Ишке ашыруу :HashSetjava doc

private transient HashMap map;

// Constructor - 1
// All constructors implicitly create a HashMap object.
public HashSet()
{
    // Create an implicit HashMap object
    map = new HashMap();
}

// Constructor- 2
public HashSet(int initialCapacity)
{
    // Create an implicit HashMap object
    map = new HashMap(initialCapacity);
}

// An object of the Object class, each time acting as a value in the HashMap
private static final Object PRESENT = new Object();

add()Эгерде сиз y ыкмасын карасаңыз HashSet:

public boolean add(E e)
{
   return map.put(e, PRESENT) == null;
}

add()Сиз y ыкмасы HashSetметодду put()ички an objectке чакырып HashMap, ага ачкыч катары кошула турган элементти жана маани катары PRESENT константасын өткөрүп жатканын байкасаңыз болот. Метод ушундай эле жол менен иштейт remove(). remove()Ал ички an object ыкмасын чакырат HashMap:

public boolean remove(Object o)
{
  return map.remove(o) == PRESENT;
}

HashSetхэш tableга негизделген жана кошуу, жок кылуу же издөө операциялары орточо эсеп менен туруктуу (O(1)) убакытта бүтөт . Методдор HashSet:

1. boolean add(E e): элементти кошот HashSet, эгер жок болсо, бирок андай элемент мурунтан эле бар болсо, метод false кайтарат .
2. void clear():топтомдон бардык элементтерди жок кылат.
3. boolean contains(Object o): Берилген элемент топтомдо бар болсо, чындыкты кайтарат .
4. boolean remove(Object o): Берилген элементти, эгерде бар болсо, топтомдон алып салат.
5. Iterator iterator(): Топтун элементтери үчүн итераторду кайтарат.
6. boolean isEmpty(): Эгерде топтомдо элементтер жок болсо, чындыкты кайтарат .
7. Object clone(): Беттик клондоштурууну жүргүзөт HashSet.

Javadoc: https://docs.oracle.com/javase/7/docs/api/java/util/HashSet.html