როგორ არის მოწყობილი და ორგანიზებული მონაცემთა…

Java-ში HashMap დაფუძნებულია ჰეშირების პრინციპებზე. ის ინახავს "საკლავი-მნიშვნელობის" წყვილებს.

შიდა მოწყობა:

ბაკეტების მასივი. თითოეული ბაკეტი არის დაკავშირებული სია (ან ხე, Java 8-დან და შემდეგ, როდესაც კოლიზიები დიდია).
ელემენტის დამატებისას (put):
1. საკლავის ჰეშკოდი გამოითვლება (key.hashCode()).
2. ჰეშკოდი მოდიფიცირდება უკეთესი განაწილებისთვის (hash).
3. გამოყენებით მოდიფიცირებული ჰეშისა და ბაკეტების მასივის ზომის, გამოითვლება ბაკეტის ინდექსი (хеш & (размер_массива - 1)).
4. ელემენტი (საკლავი-ღირებულების წყვილი Node ობიექტის სახით) მოთავსდება ამ ბაკეტში. თუ ბაკეტი უკვე შეიცავს ელემენტებს, ახალი ელემენტი დამატება ხდება დაკავშირებული სიის ან ხის დასაწყისში.
5. დამატებისას შემოწმდება საკლავის არსებობა: გამოიყენება equals() მეთოდი საკლავების შედარებისთვის. თუ საკლავი იპოვეს, მნიშვნელობა განახლდება.
ელემენტის მიღებისას (get):
1. ასევე გამოითვლება ბაკეტის ინდექსი საკლავზე.
2. ბაკეტში ხდება ელემენტის ძიება საკლავის მიხედვით, hashCode() და equals() მეთოდების გამოყენებით.
3. დაბრუნდება დაკავშირებული მნიშვნელობა.

ორგანიზაცია:

კოლიზიები: თუ რამდენიმე საკლავი აქვს ერთსა და იმავე ჰეშკოდს და ერთ ბაკეტში ხვდება, ელემენტები ინახება დაკავშირებული სიის სახით. Java 8-დან და შემდეგ, როდესაც ბაკეტის ელემენტების რაოდენობა გადის ზღვარს (ზოგჯერ 8), დაკავშირებული სია გარდაიქმნება ხეებად უფრო სწრაფი ძიებისთვის (O(log n) ნაცვლად O(n)).
რეზაიზინგი: როდესაც ელემენტების რაოდენობა გადის "ატვირთვის ზღვარს" (load factor * capacity), HashMap-ის შიდა მასივი განახლდება (ზოგჯერ ორმაგდება) და ყველა ელემენტი გადახაზავდება. ეს ძვირი ოპერაციაა (O(n)).
პარამეტრები:
- capacity: საწყისი ბაკეტების მასივის ზომა (ნაგულისხმევი 16).
- load factor: ატვირთვის ზღვარი (ნაგულისხმევი 0.75). განსაზღვრავს, როდის მოხდება რეზაიზინგი.

რატომ არის მნიშვნელოვანი hashCode() და equals():

სწორად მუშაობს HashMap-ის დამოკიდებულია ამ მეთოდების სწორ რეალიზაციაზე.
თუ equals() აბრუნებს true ორ ობიექტზე, მაშინ hashCode() უნდა აბრუნებდეს ერთსა და იმავე მნიშვნელობას.
არასწორი რეალიზაცია შეიძლება გამოიწვიოს ის, რომ ელემენტები ვერ იპოვიან (get დააბრუნებს null), მიუხედავად იმისა, რომ დამატებულია.

Node-ის სტრუქტურის მაგალითი:

// მხოლოდ შიდა გამოყენებისთვის
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }

    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

HashMap უზრუნველყოფს სწრაფი (საშუალოდ O(1)) დამატებას, მიღებას და წაშლას ელემენტებზე თანაბარი განაწილების შემთხვევაში. უარეს შემთხვევაში (ძალიან კოლიზიები) ოპერაცია შეიძლება გახდეს O(n) ან O(log n) ხეებით.

როგორ არის მოწყობილი და ორგანიზებული მონაცემთა სტრუქტურა HashMap-ში Java-ში?