HashSet در جاوا

کلاس HashSetاینترفیس را پیاده سازی می کند Set، بر اساس جدول هش است و همچنین توسط یک نمونه پشتیبانی می شود HashMap. از آنجایی که HashSetالمان ها مرتب نیستند، هیچ تضمینی وجود ندارد که عناصر بعد از مدتی به همان ترتیب باشند. عملیات افزودن، حذف و جستجو در زمان ثابت انجام می شود، مشروط بر اینکه تابع هش به درستی عناصر را در "سطل ها" توزیع کند، که بعداً مورد بحث قرار خواهد گرفت. چند نکته مهم در مورد HashSet:

• زیرا کلاس رابط را پیاده سازی می کند Set، فقط می تواند مقادیر منحصر به فرد را ذخیره کند.
• می تواند مقادیر NULL را ذخیره کند.
• ترتیب اضافه شدن عناصر با استفاده از کد هش محاسبه می شود.
• HashSetSerializableو را نیز اجرا می کند Cloneable.

برای حفظ زمان اجرای ثابت عملیات، زمان صرف شده برای اقدامات با HashSet، باید مستقیماً با تعداد عناصر HashSetموجود در + "ظرفیت" نمونه داخلی HashMap(تعداد "سبدها") متناسب باشد. بنابراین، برای حفظ عملکرد، مهم است که ظرفیت اولیه را خیلی زیاد (یا ضریب بار خیلی کم) تنظیم نکنید. ظرفیت اولیه - تعداد اولیه سلول ها ("bin") در جدول هش. اگر تمام سلول ها پر شوند، تعداد آنها به طور خودکار افزایش می یابد. ضریب بار معیاری است که نشان می دهد HashSetقبل از اینکه ظرفیت آن به طور خودکار افزایش یابد چقدر می تواند پر باشد. هنگامی که تعداد عناصر موجود در HashSetبیش از حاصلضرب ظرفیت اولیه و ضریب بار شد، جدول هش مجدداً هش می شود (کدهای هش عناصر دوباره محاسبه می شوند و جدول با توجه به مقادیر بدست آمده بازسازی می شود) و تعداد سلول های موجود در آن دو برابر شده است. ضریب بار = تعداد عناصر ذخیره شده در جدول / اندازه جدول هش به عنوان مثال، اگر تعداد سلول های اولیه در جدول 16 و ضریب بار 0.75 باشد، پس از اینکه تعداد سلول های پر شده به 12 رسید، تعداد سلول ها به طور خودکار افزایش می یابد. ضریب بار و ظرفیت اولیه دو عامل اصلی هستند که بر عملکرد HashSet. ضریب بار 0.75 به طور متوسط ​​عملکرد خوبی را ارائه می دهد. اگر این پارامتر افزایش یابد، بار حافظه کاهش می‌یابد (زیرا تعداد هش‌ها و بازسازی‌های مجدد را کاهش می‌دهد)، اما بر عملیات پیوست و جستجو تأثیر می‌گذارد. برای به حداقل رساندن زمان صرف شده برای هش کردن مجدد، باید پارامتر ظرفیت اولیه مناسب را انتخاب کنید. اگر ظرفیت اولیه بیشتر از حداکثر تعداد عناصر تقسیم بر ضریب بار باشد، هیچ عملیات هش کردن مجدد به هیچ وجه رخ نخواهد داد. مهم: 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)– سازنده ای که عناصری را از مجموعه دیگری اضافه می کند.

کد زیر چند روش را نشان می دهد 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فقط مقدار به آن اضافه می شود. در واقع، مقداری که به آن پاس می دهیم HashSet، کلید شی است HashMapو یک ثابت به عنوان مقدار استفاده می شود HashMap. به این ترتیب، در هر جفت کلید-مقدار، همه کلیدها دارای یک مقدار خواهند بود. پیاده سازی 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 نگاه کنید 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اگر عنصری وجود نداشته باشد، یک عنصر را به آن اضافه می کند، اما اگر چنین عنصری از قبل وجود داشته باشد، متد false را برمی گرداند .
2. void clear():تمام عناصر را از یک مجموعه حذف می کند.
3. boolean contains(Object o): اگر عنصر داده شده در مجموعه وجود داشته باشد مقدار true را برمی گرداند.
4. boolean remove(Object o): عنصر داده شده را در صورت وجود از مجموعه حذف می کند.
5. Iterator iterator(): یک تکرار کننده برای عناصر مجموعه برمی گرداند.
6. boolean isEmpty(): اگر هیچ عنصری در مجموعه وجود نداشته باشد، true را برمی‌گرداند.
7. Object clone(): شبیه سازی سطحی را انجام می دهد HashSet.

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