کالکشن ها در جاوا: استفاده از HashSet, LinkedHashSet و TreeSet

معرفی Set

Set یک پیاده‌سازی در ساختمان داده است که داخلش نمیتونیم عنصر تکراری داشته باشیم.

هر عنصر در جاوا دارای یک هش کد (hashCode) است، زمانی که دو عنصر باهم برابر باشن هش کد های یکسانی دارن.

تمام کلاس ها در جاوا یک تابع به نام hashCode دارن که این تابع یک کد اختصاصی برای کلاس تولید میکنه Set یک ساختار داده است که در آن عنصر تکراری وجود نداره، مقایسه ی دو کلاس در Set با هش‌ کد صورت می گیره.

در جاوا سه کلاس HashSet, LinkedHashSet و TreeSet اینترفیس Set رو پیاده‌سازی میکنن و Set یک ساب اینترفیس از Collection است.

زمانی که بخوایم به Set یک عنصر تکراری اضافه کنیم، عنصر جدید بهش اضافه نمیشه استفاده از Set در مواقعی که نیاز داریم عناصر تکراری نباشن بهینه تر از سایر کالکشن هاست.

متد (تابع) های پرکاربرد Set در Collection تعریف شده اند برای آشنایی با این متد ها میتونید به معرفی اینترفیس کالکشن مراجعه کنید.

استفاده از HashSet

کلاس HashSet یک پیاده سازی از اینترفیس Set است، عناصر داخل HashSet بر اساس hashCode هاشون نگهداری میشن و ترتیب مشخصی در نگهداری عناصر داخل HashSet وجود نداره.

در زیر سلسله مراتب ارث‌بری کلاس HashSet شرح داده شده است.

در نمودار uml زیر کانستراکتور (سازنده) های کلاس HashSet با پارامتر هاشون توضیح داده شده است.

مقدار loadFactor باید یک عدد بین 0 تا 1 باشه و loadFactor در Set زمان افزایش ظرفیت رو مشخص میکنه فرض کنید ظرفیت اولیه یک HashSet برابر با 16 است یعنی 16 تا عنصر داخلش جا میگیره، اگه مقدار loadFactor برابر با 0.5 باشه، زمانی که تعداد عناصر داخل HashSet به 8 برسه، ظرفیت HashSet به صورت خودکار افزایش پیدا میکنه؛ مقدار loadFactor به صورت پیشفرض برابر با 0.75 است.

در مثال زیر میخوایم اسم زبان های برنامه‌نویسی رو به Set اضافه کنیم و سپس با foreach صداشون بزنیم.

Set<String> set = new HashSet<>();
set.add("Java");
set.add("Python");
set.add("Kotlin");
set.add("JavaScript");

set.forEach(System.out::println);

System.out.println();

set.add("JavaScript");

set.forEach(System.out::println);
        

استفاده از LinkedHashSet

در پیاده‌سازی LinkedHashSet از LinkedList استفاده شده و عناصر مانند LinkedList به ترتیبی که اضافه میشن داخلش قرار میگیرن، زمانی که ترتیب قرار گرفتن عناصر مهم باشه یا بخوایم عنصری رو به ابتدا یا انتهای Set اضافه کنیم از LinkedHashSet استفاده میکنیم.

در زیر سلسله مراتب ارث‌بری LinkedHashSet شرح داده شده است.

کانستراکتور (سازنده) های LinkedHashSet مانند HashSet هستن، در زیر uml کانستراکتور (سازنده) های کلاس LinkedHashSet با توضیحاتشون اورده شده است.

در مثال زیر میخوایم زبان های برنامه نویسی رو به LinkedHashSet اضافه کنیم و سپس با foreach صداشون بزنیم و چاپ کنیم.

LinkedHashSet<String> linkedHashSet = new LinkedHashSet<>();
linkedHashSet.add("Java");
linkedHashSet.add("Python");
linkedHashSet.add("Kotlin");
linkedHashSet.addLast("JavaScript");
linkedHashSet.addFirst("PHP");

linkedHashSet.forEach(System.out::println);
        

در مثال زیر میخوایم یک صف (Queue) با LinkedHashSet پیاده کنیم.

public class QueueSet<E> {
    private final LinkedHashSet<E> set = new LinkedHashSet<>();

    public QueueSet(E[] elements){
        Collections.addAll(set, elements);
    }

    public E poll(){
        return set.removeFirst();
    }

    public void add(E e){
        set.addFirst(e);
    }


    public int size(){
        return set.size();
    }

    public boolean isEmpty(){
        return set.isEmpty();
    }
}
        

استفاده از TreeSet

عناصر در TreeSet به ترتیب مقایسه ای که توسط Comparable باهمدیگه میشن قرار میگیرن؛ در TreeSet زمانی دو عنصر تکراری هستن که مقدار 0 توسط Comparable برگردونده بشه.

علاوه بر مقایسه ی عناصر به صورت پیشفرض توسط Comparable میتونیم عناصر رو با Comparator در TreeSet باهم مقایسه کنیم.

در زیر سلسله مراتب ارث‌بری کلاس TreeSet شرح داده شده است.

در نمودار UML زیر کانستراکتور (سازنده) های TreeSet شرح داده شده است.

SortedSet<String> sortedSet = new TreeSet<>(Comparator.comparingInt(String::length));

sortedSet.add("Arak");
sortedSet.add("Qom");
sortedSet.add("Hamadan");
sortedSet.add("Mashhad");
sortedSet.add("Ahwaz");
sortedSet.add("Sari");
sortedSet.add("Qazvin");
sortedSet.add("Golestan");
sortedSet.add("Shiraz");
sortedSet.add("Tabriz");

System.out.println(sortedSet);
System.out.println(sortedSet.getFirst());
System.out.println(sortedSet.getLast());
System.out.println("headSet(\"Qazvin\"): " + sortedSet.headSet("Qazvin"));
System.out.println("tailSet(\"Qazvin\"): " + sortedSet.tailSet("Qazvin"));
        

NavigableSet<String> navigableSet = new TreeSet<>();
navigableSet.add("Arak");
navigableSet.add("Qom");
navigableSet.add("Hamadan");
navigableSet.add("Mashhad");
navigableSet.add("Ahwaz");
navigableSet.add("Sari");
navigableSet.add("Qazvin");
navigableSet.add("Golestan");
navigableSet.add("Shiraz");
navigableSet.add("Tabriz");

System.out.println(navigableSet);
System.out.println("lower(\"Q\"): " + navigableSet.lower("Q"));
System.out.println("higher(\"Q\"): " + navigableSet.higher("Q"));
System.out.println("floor(\"Q\"): " + navigableSet.floor("Q"));
System.out.println("ceiling(\"Q\"): " + navigableSet.ceiling("Q"));
System.out.println(navigableSet.descendingSet());
          

پیچیدگی زمان (Time Complexity)

در جدول زیر پیچیدگی زمان کلاس های HashSet, LinkedHashSet و TreeSet برای افزودن و جستجوی عناصر شرح داده شده است.

خلاصه

• از Set برای نگهداری عناصر غیر تکراری استفاده می کنیم.
• عناصر در HashSet به ترتیب hashCode هاشون نگهداری میشن.
• هنگامی که بخوایم عناصر رو به ترتیبی که اضافه میکنیم در Set نگهداری کنیم از LinkedHashSet استفاده می کنیم.
• در TreeSet عناصر به ترتیب مقایسه ای که با Comparable یا Comparator میشن، نگهداری میشن.