محمدرضا علاقه‌ی زیادی به بهینه بودن برنامه‌ها دارد. او که در زمینه‌ی الگوریتم بسیار خفن است، می‌داند که استفاده از hash برای نگه‌داری داده‌ها در برخی مواقع نه تنها کمکی به افزایش پرفورمنس نمی‌کند، بلکه پرفورمنس برنامه را کاهش می‌دهد. نیما که حرف محمدرضا را قبول ندارد، از او درخواست کدی کرده است تا میزان hash collision ها را ببیند. محمدرضا نیز این کار را به شما محول کرده است.

در این سؤال، یک HashSet یا HashMap به شما داده می‌شود. شما باید تعداد یکتای hash code های مقادیر موجود در HashSet یا کلیدهای موجود در HashMap را محاسبه کرده و برگردانید.

جزئیات پروژه

پروژه‌ی اولیه را از این لینک دانلود کنید. ساختار فایل‌های پروژه به‌صورت زیر است:

hash-collision-checker
├── HashCollisionChecker.java
└── HashCollisionCheckerSampleTest.java

کلاس HashCollisionChecker

این کلاس شامل دو متد زیر است که باید آن‌ها را پیاده‌سازی کنید:

محاسبه‌ی تعداد یکتای hash code های موجود در یک HashSet

public static <T> int countOfUniqueHashCodes(HashSet<T> set)

این متد را طوری پیاده‌سازی کنید که با دریافت یک HashSet، تعداد یکتای hash code های مقادیر موجود در آن را برگرداند.

محاسبه‌ی تعداد یکتای hash code های موجود در یک HashSet

public static <K, V> int countOfUniqueHashCodes(HashMap<K, V> map)

این متد را طوری پیاده‌سازی کنید که با دریافت یک HashMap، تعداد یکتای hash code های کلیدهای موجود در آن را برگرداند.

مثال

با اجرای متد main موجود در کلاس HashCollisionChecker:

public static void main(String[] args) {
    HashSet<String> set = new HashSet<>();
    set.add("c#c#c#c#c#c#bBc#c#c#c#bBc#");
    set.add("abcd");
    set.add("c#c#c#c#c#c#bBc#c#c#c#c#aa");
    set.add("1234");
    set.add("c#c#c#c#c#c#bBc#c#c#c#c#bB");
    System.out.println(countOfUniqueHashCodes(set)); // 3

    HashMap<String, Integer> map = new HashMap<>();
    map.put("c#c#c#c#c#c#c#aaaaaaaabBbB", 14);
    map.put("c#c#c#c#c#c#c#aaaaaaaac#c#", 12);
    map.put("c#c#c#c#c#c#c#aaaaaaaac#cc", 16);
    System.out.println(countOfUniqueHashCodes(map)); // 2
}

خروجی باید به‌صورت زیر باشد:

3
2

نکات

• برای دریافت hash code آبجکت‌ها، می‌توانید از متد hashCode استفاده کنید.
• تست‌های نمونه‌ی سؤال در کلاس HashCollisionCheckerSampleTest موجود هستند. با افزودن JUnit به classpath پروژه، می‌توانید آن‌ها را اجرا کنید.

آن‌چه باید آپلود کنید

پس از پیاده‌سازی متدها، فایل HashCollisionChecker.java را آپلود کنید.