Ինչպես է կառուցված և կազմակերպված Data Structure HashMap-ը Java-ում:

HashMap-ը Java-ում հիմնված է հեշավորման սկզբունքների վրա։ Այն պահում է « բանալի-արժեք » զույգեր։

Ներքին կառուցվածքը:

• Բաքուների (կոնտեյներների) զանգված։ Յուրաքանչյուր բաքը կապված ցանկ է (կամ ծառ, Java 8-ից սկսած, երբ շատ կոլիզիաներ են)։
• Երբ ավելացվում է տարր (put):
  1. Հաշվարկվում է բանալի հեշ կոդը (key.hashCode())։
  2. Հեշ կոդը փոփոխվում է ավելի լավ բաշխման համար (hash)։
  3. Օգտագործելով փոփոխված հեշը և զանգվածի չափը, հաշվարկվում է բաքի ինդեքսը (hash & (array_size - 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) ծառերով։