HashMap Java 8-ში

ეს პოსტი ერთ-ერთ ბლოგზე ვნახე და ვიფიქრე კარგი იქნებოდა თუ გადავთარგმნიდი და გავუზიარებდი ჩემი ბლოგი მკითხველებს.

როგორც ვიცით Java 8-მ წინა ვერსიებთან შედარებით პროგრესი განიცადა და ბევრი რამ გააუმჯობესა. საკმაოდ ბევრი კლასი განახლდა, ამ მხრივ არც HashMap ყოფილა გამონაკლისი. ამ პოსტში განხილულია ერთ-ერთი მნიშვნელოვანი ფუნქცია რომელიც Java 8-ში გამოჩნდა hash კოდების კოლიზიისას.

რა არის ყველაზე ამრტივი გზა რომ მოვახდინოთ კოლიზია HashMap-ში ? რა თქმა უნდა, უნდა შევქმნათ კლასი რომელსაც ექნება თავისი hashCode() ფუნქცია, რომელიც დააბრუნებს მუდმივ მნიშვნელობას. გასაუბრებებზე კანდიდატები ხშრად უშვებენ შეცდომას, რომ map შეიცავს მხოლოდ და მხოლოდ ერთ ელემენტს, რადგან ძველი ჩანაწერს ყოველთვის გადაეწერება ახალი ერთნაირი hash კოდის შემთხვევაში. რა თქმა უნდა, ეს არ არის სიმართლე. Hash კოლიზია არ იწვევს ჩანაწერების ერთმანეთზე გადაწერას, ეს ხდება მაშინ და მხოლოდ მაშინ როცა ორი ელემენტი ტოლია equals() ფუნქციით. ჩანაწერები არა ტოლი გასაღებებით და ერთი და იგივე hash კოდით იქნება ერთი და იგივე hash კალათაში. სურათზე მოცემულია მაგალითი Java 7-ში.

aa

დავწეროთ პატარა აპლიკაცია, რომელიც მოახდენს კოლიზიის სიმულაციას. მაგალითი ცოტა გაზვიადებულია, რადგან მიზანია, რომ დააგენერიროს რაც შეიძლება მეტი კოლიზია, თუნდაც იმაზე მეტი რაც რეალურ აპლიკაციებშია, თუმცა ეს საჭიროა შედეგის დასამტკიცებლად.

მაგალითში, ვიყენებთ Person ობიექტს როგორც map-ის გასაღებს, ხოლო მნიშვნელობები არის String-ები. ვნახოთ იმპლემენტაცია Person ობიექტის.


public class Person {

private String firstName;

private String lastName;

private UUID id;

public Person(String firstName, String lastName, UUID id) {

this.firstName = firstName;

this.lastName = lastName;

this.id = id;

}

@Override

public int hashCode() {

return 5;

}

@Override

public boolean equals(Object obj) {

// ... pertty good equals here taking into account the id field...

}

}

ახლა კი დავაგენერიროთ კოლიზიები


private static final int LIMIT = 500_000;

private void fillAndSearch() {

Person person = null;

Map<Person, String> map = new HashMap<>();

for (int i=0;i<LIMIT;i++) {

UUID randomUUID = UUID.randomUUID();

person = new Person("fn", "ln", randomUUID);

map.put(person, "comment" + i);

}

long start = System.currentTimeMillis();

map.get(person);

long stop = System.currentTimeMillis();

System.out.println(stop-start+" millis");

}

როგორც ამ პოსტის დედანის ავტორი გვეუბნება, მან ეს კოდი გაუშვა საკმაოდ კარგ მანქანაზე და map-ის შევსებას მოუნდა 2.5 საათი, ხოლო ბოლო ძებნას დასჭირდა ~40 მილიწამი.  ახლა ყოველგვარი ახსნა-განმარტების გარეშე Person კლასში შევიტანოთ პატარა ცვლილება: მოვახდინოთ Comparable<Person>-ის იმპლემენტაცია და დავამატოთ შემდეგი მეთოდი


@Override

public int compareTo(Person person) {

return this.id.compareTo(person.id);

}

ახლა გავუშვათ map-ის შემვსები მეთოდი კიდევ ერთხელ. ისევე ამ პოსტის დედანის ავტორის ინფორმაციით, map-ის შევსებას დასჭირდა 1 წუთამდე, ხოლო ბოლო ძებნას მოუნდა თითქმის 0 მილიწამი. ასე რომ ამან დაახლოებით 150-ჯერ ააჩქარა აპლიკაცია.

 

როგორც დასაწყისში აღვნიშნეთ, Java 8-ში ბევრი რამ გაუმჯობესდა. Java 7-ში ისეთი ჩანაწერები, რომლების კოლიზიაც მოხდებოდა ინახებოდა LinkedList-ად bucket-ში. Java 8-დან , თუ კოლიზიების რიცხვი მეტია კონკრეტულ ზღურბლზე (threshold) (8) და map-ის მოცულობა მეტია სხვა ზღურბლზე (threshold) (64), HashMap-ის იმპლემენტაცია გადაიყვანს LinkedList-დან ორობით ხეში.

ისმის კითხვა თუ რატომ მივიღეთ ასეთი შედეგები რაც მივიღეთ. იმიტომ რომ non-comparable გასაღებების შემთხვევაში რეზულტატი ხე იყო არაბალანსირებული, ხოლო comparable ის იყო უკეთ ბალანსირებული  ? არა. ხის იმპლემენტაცია HashMap-ში არის წითელ-შავი ხეები, რაც გულისხმობს იმას, რომ ის ყოველთვის ბალანსირებულია. მაშინ ისმის კითხვა ? აბა საიდან მივიღეთ ასეთი დიდი განსხვავება ? როცა HashMap ცდილობს იპოვოს ახალი ჩანაწერისთვის ადგილი ხეში, პირველ რიგში ადარებს მიმდინარე და ახალი მნიშვნელობები არის თუ არა ადვილად შესადარებელი (Comparable interface) . უკანასკნელ შემთხვევაში, ის უბრუნდება შესადარებელ მეთოდ tieBreakOrder(Object a, Object b)ს. ეს მეთოდი ცდილობს პირველად შეადაროს კლასის სახელით, და შემდეგ იყენებს System.identityHashCodeს. როცა გასაღები იმპლემენტირებას უკეთებს Comparable-ს, პროცესი არის გაცილებით მარტივი. გასაღები თვითონ განსაზღვარს როგორ უნდა შეედაროს სხვა გასაღებს, რაც მთლიან ჩასმა/ამოღების ოპერაციებს აჩქარებს. უნდა აღინიშნოს, რომ იგივე tieBreakOrder  გამოიყენება, როცა ორი Comparable გასაღები არის ტოლი compareTo მეთოდზე დაყრდნობით (ანუ ეს compareTo  მეთოდი აბრუნებს 0-ს).

 

Leave a Reply / უპასუხე

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / შეცვლა )

Twitter picture

You are commenting using your Twitter account. Log Out / შეცვლა )

Facebook photo

You are commenting using your Facebook account. Log Out / შეცვლა )

Google+ photo

You are commenting using your Google+ account. Log Out / შეცვლა )

Connecting to %s