Java-da HashSet

Sinif HashSetinterfeysi həyata keçirir Set, hash cədvəlinə əsaslanır və həmçinin bir nümunə ilə dəstəklənir HashMap. Elementlər sıralanmadığından HashSetbir müddət sonra elementlərin eyni qaydada olacağına zəmanət yoxdur. Əlavə etmə, silmə və axtarış əməliyyatları sabit vaxtda yerinə yetiriləcək, bir şərtlə ki, hash funksiyası elementləri "kovalara" düzgün şəkildə paylayır, bu barədə daha sonra müzakirə ediləcəkdir. Haqqında bir neçə vacib məqam HashSet:

• Çünki sinif interfeysi həyata keçirir Set, yalnız unikal dəyərləri saxlaya bilər;
• NULL dəyərləri saxlaya bilir;
• Elementlərin əlavə olunma sırası hash kodundan istifadə etməklə hesablanır;
• HashSetSerializablevə də həyata keçirir Cloneable.

Əməliyyatların daimi icra müddətini saxlamaq üçün ilə hərəkətlərə sərf olunan vaxt + quraşdırılmış instansiyanın "tutumu" HashSetndakı elementlərin sayına ("səbətlərin" sayı) düz mütənasib olmalıdır. Buna görə də, performansı qorumaq üçün ilkin tutumu çox yüksək (və ya yükləmə faktorunu çox aşağı) təyin etməmək vacibdir. İlkin tutum – hash cədvəlindəki ilkin xanaların (“zibil qutuları”) sayı. Bütün hüceyrələr doldurulursa, onların sayı avtomatik olaraq artacaq. Yük əmsalı , tutumu avtomatik olaraq artmadan əvvəl onun nə qədər dolu ola biləcəyinin ölçüsüdür . Elementlərin sayı ilkin tutumun və yükləmə əmsalının hasilindən çox olduqda, hash cədvəli yenidən hash edilir (elementlərin hash kodları yenidən hesablanır və cədvəl alınan dəyərlərə uyğun olaraq yenidən qurulur) və nömrə onun tərkibindəki hüceyrələrin sayı ikiqat artır. Yük əmsalı = Cədvəldə saxlanılan elementlərin sayı/hesh cədvəl ölçüsü Məsələn, cədvəldəki xanaların ilkin sayı 16, yükləmə əmsalı isə 0,75-dirsə, bundan belə nəticə çıxır ki, doldurulmuş xanaların sayı 12-yə çatdıqda, hüceyrələrin sayı avtomatik olaraq artacaq. Yük əmsalı və ilkin tutum performansına təsir edən iki əsas amildir . 0,75 yük faktoru orta hesabla yaxşı performans təmin edir. Bu parametr artırılarsa, o zaman yaddaş yükü azalacaq (çünki bu, yenidən hash və yenidən qurmaların sayını azaldacaq), lakin əlavə və axtarış əməliyyatlarına təsir edəcək. Yenidən hashing üçün sərf olunan vaxtı minimuma endirmək üçün düzgün ilkin tutum parametrini seçməlisiniz. İlkin tutum yük faktoruna bölünən elementlərin maksimum sayından çox olarsa, heç bir yenidən hashing əməliyyatı baş verməyəcək. HashSetHashMapHashSetHashSetHashSetƏhəmiyyətli: HashSetdaxili sinxronizasiyaya malik olan məlumat strukturu deyil, ona görə də əgər onun üzərində eyni vaxtda birdən çox mövzu işləyirsə və onlardan ən azı biri dəyişiklik etməyə çalışırsa, kənardan sinxron girişi təmin etmək lazımdır. Bu, çox vaxt HashSet. Əgər belə bir obyekt yoxdursa, o zaman Collections.synchronizedSet(). Bu, hazırda ilə sinxronizasiyadan kənar əməliyyatların qarşısını almağın ən yaxşı yoludur HashSet.

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

HashSet konstruktorları:

1. HashSet h = new HashSet(); - standart konstruktor. Varsayılan ilkin tutum 16, yükləmə əmsalı 0,75-dir.
2. HashSet h = new HashSet(int initialCapacity)– verilmiş ilkin tutumu olan konstruktor. Yük əmsalı - 0,75.
3. HashSet h = new HashSet(int initialCapacity, float loadFactor);— verilmiş ilkin gücü və yük əmsalı olan konstruktor.
4. HashSet h = new HashSet(Collection C)– başqa kolleksiyadan elementlər əlavə edən konstruktor.

Aşağıdakı kod bəzi üsulları nümayiş etdirir 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());
    }
}

Nəticə:

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

İnterfeys həyata keçirən bütün siniflər Setdaxili olaraq tətbiqlər tərəfindən dəstəklənir Map. HashSetistifadə edərək elementləri saxlayır HashMap. HashMapElement əlavə etmək üçün element açar-dəyər cütü kimi təqdim edilməli olsa da , HashSetyalnız dəyər əlavə edilir. Əslində, keçdiyimiz dəyər HashSetobyektin açarıdır HashMapvə dəyər kimi sabit istifadə olunur HashMap. Beləliklə, hər açar-dəyər cütlüyündə bütün düymələr eyni dəyərə malik olacaq. Tətbiq : HashSet_java 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 metoduna baxsanız HashSet:

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

add()Siz qeyd edə bilərsiniz ki, y metodu daxili obyektdə HashSetmetodu çağırır , ona əlavə olunacaq elementi açar kimi, PRESENT sabitini isə dəyər kimi ötürür. Metod oxşar şəkildə işləyir . Daxili obyekt metodunu çağırır : put()HashMapremove()remove()HashMap

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

HashSethash cədvəlinə əsaslanır və əlavə etmək, silmək və ya axtarış əməliyyatları orta hesabla sabit (O(1)) müddətdə tamamlanacaq . Metodlar HashSet:

1. boolean add(E e): elementə element əlavə edir HashSet, əgər yoxdursa, lakin belə element artıq mövcuddursa, metod false qaytarır .
2. void clear():çoxluqdan bütün elementləri silir.
3. boolean contains(Object o): Verilmiş element çoxluqda olarsa, doğru qaytarır.
4. boolean remove(Object o): Əgər varsa, verilmiş elementi dəstdən çıxarır.
5. Iterator iterator(): Çoxluğun elementləri üçün iterator qaytarır.
6. boolean isEmpty(): Dəstə heç bir element yoxdursa, doğru qaytarır.
7. Object clone(): Səthin klonlaşdırılmasını həyata keçirir HashSet.

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