HashSet في جافا

يطبق الفصل HashSetالواجهة Set، ويستند إلى جدول التجزئة، ويدعمه أيضًا مثيل HashMap. وبما أن HashSetالعناصر ليست مرتبة، فليس هناك ما يضمن أن العناصر ستكون بنفس الترتيب بعد مرور بعض الوقت. سيتم إجراء عمليات الإضافة والحذف والبحث في وقت ثابت، على أن تقوم وظيفة التجزئة بتوزيع العناصر بشكل صحيح إلى “دلاء”، وهو ما سيتم الحديث عنه لاحقًا. بعض النقاط المهمة حول HashSet:

• لأن ينفذ الفصل الواجهة Set، ويمكنه تخزين قيم فريدة فقط؛
• يمكن تخزين القيم الخالية.
• يتم حساب الترتيب الذي تتم به إضافة العناصر باستخدام رمز التجزئة؛
• HashSetينفذ أيضًا Serializableو Cloneable.

للحفاظ على وقت تنفيذ ثابت للعمليات، HashSetيجب أن يكون الوقت المستغرق في الإجراءات مع ، متناسبًا بشكل مباشر مع عدد العناصر في HashSet+ "سعة" المثيل المدمج HashMap(عدد "السلال"). لذلك، للحفاظ على الأداء، من المهم عدم تعيين السعة الأولية عالية جدًا (أو عامل الحمولة منخفضًا جدًا). السعة الأولية – العدد الأولي للخلايا ("الصناديق") في جدول التجزئة. إذا تم ملء جميع الخلايا، فسيزيد عددها تلقائيًا. عامل الحمولة هو مقياس لمدى امتلاءها 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يستدعي التابع put()على الكائن الداخلي HashMap، ويمرره العنصر المراد إضافته كمفتاح، والثابت PRESENT كقيمة. الطريقة تعمل بطريقة مماثلة remove(). يستدعي طريقة 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.

جافادوك: https://docs.Oracle.com/javase/7/docs/api/java/util/HashSet.html