Java-da HashSet

Sinf HashSetinterfeysni amalga oshiradi Set, xesh-jadvalga asoslanadi va shuningdek, misol bilan quvvatlanadi HashMap. Elementlar tartiblanmaganligi sababli HashSet, bir muncha vaqt o'tgach, elementlar bir xil tartibda bo'lishiga kafolat yo'q. Qo'shish, o'chirish va qidirish operatsiyalari, agar xesh funktsiyasi elementlarni keyinroq muhokama qilinadigan "chelaklarga" to'g'ri taqsimlash sharti bilan doimiy ravishda amalga oshiriladi. Haqida bir nechta muhim fikrlar HashSet:

• Chunki sinf interfeysni amalga oshiradi Set, u faqat noyob qiymatlarni saqlashi mumkin;
• NULL qiymatlarni saqlashi mumkin;
• Elementlarni qo'shish tartibi xesh-kod yordamida hisoblanadi;
• HashSetSerializableva ni ham amalga oshiradi Cloneable.

Operatsiyalarning doimiy bajarilishi vaqtini saqlab turish uchun bilan harakatlarga sarflangan vaqt + o'rnatilgan instansiyaning "sig'imi" HashSetdagi elementlar soniga ("savatlar" soni) to'g'ridan-to'g'ri proportsional bo'lishi kerak. Shuning uchun, ishlashni saqlab qolish uchun, dastlabki quvvatni juda yuqori (yoki yuk koeffitsienti juda past) o'rnatmaslik kerak. Boshlang'ich sig'im - xesh jadvalidagi hujayralarning dastlabki soni ("qutilar"). Agar barcha hujayralar to'ldirilgan bo'lsa, ularning soni avtomatik ravishda ortadi. Yuk koeffitsienti uning sig'imi avtomatik ravishda oshishidan oldin qanchalik to'la bo'lishi mumkinligini ko'rsatadigan o'lchovdir . Elementlar soni boshlang'ich sig'im va yuk koeffitsientining mahsulotidan kattaroq bo'lganda, xesh jadvali qayta xeshlanadi (elementlarning xesh kodlari qayta hisoblab chiqiladi va olingan qiymatlarga muvofiq jadval qayta tiklanadi) va raqam undagi hujayralar soni ikki barobar ortadi. Yuklash koeffitsienti = Jadvalda saqlangan elementlar soni / jadval o'lchami xesh Masalan, agar jadvaldagi hujayralarning dastlabki soni 16 bo'lsa va yuklanish koeffitsienti 0,75 bo'lsa, to'ldirilgan katakchalar soni 12 ga yetganda, hujayralar soni avtomatik ravishda ortadi. Yuk koeffitsienti va boshlang'ich quvvati ishlashiga ta'sir qiluvchi ikkita asosiy omildir . 0,75 yuk koeffitsienti o'rtacha yaxshi ishlashni ta'minlaydi. Agar bu parametr oshirilsa, xotira yuki kamayadi (chunki u qayta xeshlar va qayta qurishlar sonini kamaytiradi), lekin qo'shish va qidirish operatsiyalariga ta'sir qiladi. Qayta xeshlash uchun sarflangan vaqtni kamaytirish uchun siz to'g'ri boshlang'ich sig'im parametrini tanlashingiz kerak. Agar boshlang'ich sig'im yuk koeffitsientiga bo'lingan elementlarning maksimal sonidan kattaroq bo'lsa, unda hech qanday qayta xeshlash jarayoni sodir bo'lmaydi. HashSetHashMapHashSetHashSetHashSetMuhim: HashSeto'rnatilgan sinxronizatsiyaga ega ma'lumotlar strukturasi emas, shuning uchun bir vaqtning o'zida bir nechta iplar ishlayotgan bo'lsa va ulardan kamida bittasi o'zgartirish kiritishga harakat qilsa, tashqaridan sinxronlashtirilgan kirishni ta'minlash kerak. Bu ko'pincha o'z ichiga olgan boshqa sinxronlashtirilgan ob'ekt hisobiga amalga oshiriladi HashSet. Agar bunday ob'ekt bo'lmasa, u holda Collections.synchronizedSet(). Bu hozirda bilan sinxronlashdan tashqari operatsiyalarni oldini olishning eng yaxshi usuli hisoblanadi HashSet.

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

HashSet konstruktorlari:

1. HashSet h = new HashSet(); - standart konstruktor. Standart boshlang'ich sig'imi 16, yuk koeffitsienti 0,75.
2. HashSet h = new HashSet(int initialCapacity)– berilgan boshlang‘ich sig‘imga ega bo‘lgan konstruktor. Yuk koeffitsienti - 0,75.
3. HashSet h = new HashSet(int initialCapacity, float loadFactor);— dastlabki quvvati va yuk koeffitsienti berilgan konstruktor.
4. HashSet h = new HashSet(Collection C)- boshqa to'plamdan elementlarni qo'shadigan konstruktor.

Quyidagi kod ba'zi usullarni ko'rsatadi 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());
    }
}

Xulosa:

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

Interfeysni amalga oshiradigan barcha sinflar Setichki ilovalar tomonidan qo'llab-quvvatlanadi Map. HashSetyordamida elementlarni saqlaydi HashMap. HashMapElement qo'shish uchun element kalit-qiymat juftligi sifatida ko'rsatilishi kerak bo'lsa-da , HashSetfaqat qiymat qo'shiladi. Aslida, biz o'tadigan qiymat HashSetob'ektning kalitidir HashMapva qiymat sifatida doimiy ishlatiladi HashMap. Shunday qilib, har bir kalit-qiymat juftligida barcha kalitlar bir xil qiymatga ega bo'ladi. Amalga oshirish :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()Agar siz y usuliga qarasangiz HashSet:

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

E'tibor berishingiz mumkinki, add()y usuli ichki ob'ektdagi HashSetusulni chaqiradi , unga kalit sifatida qo'shiladigan elementni va qiymat sifatida PRESENT doimiysini uzatadi. Usul shunga o'xshash tarzda ishlaydi . U ichki ob'ekt usulini chaqiradi : put()HashMapremove()remove()HashMap

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

HashSetxesh jadvaliga asoslanadi va qo'shish, o'chirish yoki qidirish operatsiyalari o'rtacha (O(1)) vaqt ichida yakunlanadi . Usullari HashSet:

1. boolean add(E e): ga element qo'shadi HashSet, agar mavjud bo'lmasa, lekin agar bunday element allaqachon mavjud bo'lsa, usul false ni qaytaradi .
2. void clear():to'plamdan barcha elementlarni olib tashlaydi.
3. boolean contains(Object o): Agar berilgan element toʻplamda mavjud boʻlsa, true qiymatini qaytaradi.
4. boolean remove(Object o): Agar mavjud bo'lsa, berilgan elementni to'plamdan olib tashlaydi.
5. Iterator iterator(): To'plam elementlari uchun iteratorni qaytaradi.
6. boolean isEmpty(): Agar to'plamda hech qanday element bo'lmasa, true qiymatini qaytaradi.
7. Object clone(): Sirt klonlashni amalga oshiradi HashSet.

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