Java тіліндегі HashSet

Класс HashSetинтерфейсті жүзеге асырады Set, хэш кестесіне негізделген және сонымен қатар данасы арқылы қолдау көрсетіледі HashMap. Элементтер реттелмегендіктен HashSet, элементтер біраз уақыттан кейін бірдей тәртіпте болатынына кепілдік жоқ. Хэш функциясы элементтерді кейінірек талқыланатын «шелектерге» дұрыс таратқан жағдайда қосу, жою және іздеу операциялары тұрақты уақытта орындалады. Бірнеше маңызды тармақтар туралы HashSet:

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

Операциялардың тұрақты орындалу уақытын сақтау үшін, көмегімен әрекеттерге жұмсалған уақыт + кірістірілген дананың «сыйымдылығындағы» HashSetэлементтер санына («себеттер» саны) тура пропорционалды болуы керек. Сондықтан өнімділікті сақтау үшін бастапқы сыйымдылықты тым жоғары (немесе жүктеме коэффициентін тым төмен) орнатпау маңызды. Бастапқы сыйымдылық – хэш кестесіндегі ұяшықтардың бастапқы саны («қалқымалар»). Барлық ұяшықтар толтырылған болса, олардың саны автоматты түрде артады. Жүктеме коэффициенті оның сыйымдылығы автоматты түрде ұлғаюына дейін оның қаншалықты толы болуы мүмкін екенін көрсететін өлшем . Элементтердің саны бастапқы сыйымдылық пен жүктеме коэффициентінің көбейтіндісінен үлкен болған кезде хэш кестесі қайта хэштеледі (элементтердің хэш-codeтары қайта есептеледі және алынған мәндерге сәйкес кесте қайта құрылады) және саны ондағы жасушалардың саны екі есе артады. Жүктеу коэффициенті = Кестеде сақталған элементтер саны / кестенің хэш өлшемі Мысалы, кестедегі ұяшықтардың бастапқы саны 16 болса, ал жүктеу коэффициенті 0,75 болса, толтырылған ұяшықтар саны 12-ге жеткенде, ұяшықтардың саны автоматты түрде артады. Жүктеме коэффициенті және бастапқы сыйымдылық өнімділікке әсер ететін екі негізгі фактор болып табылады . 0,75 жүктеме коэффициенті орташа жақсы өнімділікті қамтамасыз етеді. Егер бұл параметр ұлғайтылса, жад жүктемесі азаяды (өйткені ол қайта хэштер мен қайта құрулар санын азайтады), бірақ ол қосу және іздеу әрекеттеріне әсер етеді. Қайта хэшингке кететін уақытты азайту үшін дұрыс бастапқы сыйымдылық параметрін таңдау керек. Егер бастапқы сыйымдылық жүктеме коэффициентіне бөлінген элементтердің максималды санынан көп болса, онда қайта хэштеу операциясы мүлдем болмайды. HashSetHashMapHashSetHashSetHashSetМаңызды: HashSetкірістірілген синхрондауы бар деректер құрылымы емес, сондықтан егер онда бірнеше ағындар бір уақытта жұмыс істеп тұрса және олардың кем дегенде біреуі өзгертулер енгізуге әрекеттенсе, сырттан синхрондалған қатынасты қамтамасыз ету қажет. Бұл көбінесе инкапсуляциялайтын басқа синхрондалған нысан есебінен жасалады HashSet. Егер мұндай нысан жоқ болса, онда 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әдісті шақырып , оған кілт ретінде қосылатын элементті және мән ретінде PRESENT тұрақтысын жіберетінін байқай аласыз . Әдіс ұқсас түрде жұмыс істейді . Ол ішкі нысан әдісін шақырады : put()HashMapremove()remove()HashMap

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

HashSetхэш кестесіне негізделген және қосу, жою немесе іздеу операциялары орташа алғанда тұрақты (O(1)) уақытта аяқталады . Әдістері HashSet:

1. boolean add(E e): элементті параметріне қосады HashSet, егер жоқ болса, бірақ мұндай элемент бұрыннан бар болса, әдіс жалған мәнін қайтарады .
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