HashSet дар Java

Синф HashSetинтерфейсро амалӣ мекунад Set, ба ҷадвали ҳаш асос ёфтааст ва инчунин бо мисол дастгирӣ карда мешавад HashMap. Азбаски HashSetунсурҳо фармоиш дода нашудаанд, ҳеҷ кафолате нест, ки унсурҳо пас аз чанд вақт дар ҳамон тартиб хоҳанд буд. Амалиётҳои илова кардан, нест кардан ва ҷустуҷӯ кардан дар вақти доимӣ иҷро карда мешаванд, ба шарте ки функсияи hash унсурҳоро ба "сатилҳо" дуруст тақсим кунад, ки баъдтар баррасӣ хоҳад шуд. Якчанд нуктаҳои муҳим дар бораи HashSet:

• Зеро синф интерфейсро амалӣ мекунад Set, он танҳо арзишҳои беназирро нигоҳ дошта метавонад;
• Қиматҳои NULL-ро нигоҳ дошта метавонад;
• Тартиби илова кардани элементҳо бо истифода аз рамзи hash ҳисоб карда мешавад;
• HashSetSerializableва ро низ ба амал мебарорад Cloneable.

Барои нигоҳ доштани доимии вақти иҷрои амалиёт, вақти сарфшуда барои амалҳо бо HashSet, бояд мустақиман ба шумораи элементҳо дар HashSet+ "иқтидори" инстансияи дарунсохт HashMap(шумораи "сабадҳо") мутаносиб бошад. Аз ин рӯ, барои нигоҳ доштани кор, муҳим аст, ки иқтидори ибтидоиро аз ҳад зиёд (ё омor сарборӣ хеле паст) муқаррар накунед. Иқтидори ибтидоӣ - шумораи ибтидоии ячейкаҳо ("бинҳо") дар ҷадвали хэш. Агар ҳама ҳуҷайраҳо пур карда шаванд, шумораи онҳо ба таври худкор зиёд мешавад. Омor сарборӣ ченаки он аст, ки HashSetто он даме, ки иқтидори он ба таври худкор афзоиш ёбад, то чӣ андоза пур шуданаш мумкин аст. Вақте ки шумораи элементҳо HashSetаз ҳосor иқтидори ибтидоӣ ва омor сарборӣ зиёд мешавад, ҷадвали хэш аз нав хэш карда мешавад (рамзҳои хэши элементҳо аз нав ҳисоб карда мешаванд ва ҷадвал мувофиқи арзишҳои гирифташуда аз нав сохта мешаванд) ва адад ҳуҷайраҳои дар он дучанд мешавад. Омor сарборӣ = Шумораи элементҳои дар ҷадвал нигоҳ дошташуда / андозаи ҷадвали хэш Масалан, агар шумораи ибтидоии чашмакҳо дар ҷадвал 16 бошад ва омor сарборӣ 0,75 бошад, пас аз он бармеояд, ки вақте шумораи ҳуҷайраҳои пуршуда ба 12 мерасад, шумораи ҳуҷайраҳо ба таври худкор зиёд мешавад. Омor сарборӣ ва иқтидори ибтидоӣ ду омor асосие мебошанд, ки ба иҷрои HashSet. Омor сарбории 0,75 ба ҳисоби миёна иҷрои хубро таъмин мекунад. Агар ин параметр зиёд карда шавад, пас сарбории хотира кам мешавад (чунонки он шумораи дубора ва барқароркуниро кам мекунад), аммо он ба амалиёти замима ва ҷустуҷӯ таъсир мерасонад. Барои кам кардани вақти сарфшуда барои re-hashing, шумо бояд параметри иқтидори ибтидоиро дуруст интихоб кунед. Агар иқтидори ибтидоӣ аз шумораи ниҳоии элементҳо, ки ба омor сарборӣ тақсим карда мешавад, зиёд бошад, он гоҳ амалиёти дубораи ҳашинг умуман сурат намегирад. Муҳим: HashSetсохтори додаҳо бо синхронизатсияи дарунсохт нест, бинобар ин, агар риштаҳои сершумор дар як вақт дар он кор кунанд ва ҳадди аққал яке аз онҳо кӯшиши тағир доданро дошта бошад, дастрасии ҳамоҳангшударо аз берун таъмин кардан лозим аст. Ин аксар вақт аз ҳисоби an objectи дигари ҳамоҳангшуда, ки HashSet. Агар чунин an object набошад, пас Collections.synchronizedSet(). Ин дар айни замон беҳтарин роҳи пешгирии амалиёти берун аз ҳамоҳангӣ бо HashSet.

Set s = Collections.synchronizedSet(new HashSet(...));

Созандагони HashSet:

1. HashSet h = new HashSet(); - созандаи пешфарз. Иқтидори ибтидоии пешфарз 16, омor сарборӣ 0,75 аст.
2. HashSet h = new HashSet(int initialCapacity)– конструктори дорои иқтидори ибтидоии додашуда. Коэффисиенти сарборӣ - 0,75.
3. HashSet h = new HashSet(int initialCapacity, float loadFactor);— конструкторе, ки иктидори ибтидой ва коэффисиенти сарборй дода шудааст.
4. HashSet h = new HashSet(Collection C)– конструкторе, ки элементҳоро аз коллексияи дигар илова мекунад.

Рамзи дар поён овардашуда баъзе усулҳоро нишон медиҳад HashSet:

import java.util.*;

class Test
{
    public static void main(String[]args)
    {
        HashSet<String> h = new HashSet<String>();

        // Add elements to the HashSet using the add() method
        h.add("India");
        h.add("Australia");
        h.add("South Africa");
        h.add("India");// try to add another same element

        // Print the elements of the HashSet to the console
        System.out.println(h);
        System.out.println("List contains India or not:" +
                           h.contains("India"));

        // Remove elements from the set using the remove() method
        h.remove("Australia");
        System.out.println("List after removing Australia:"+h);

        // Loop through the elements of the HashSet using an iterator:
        System.out.println("Iterating over list:");
        Iterator<String> i = h.iterator();
        while (i.hasNext())
            System.out.println(i.next());
    }
}

Хулоса:

[South Africa, Australia, India]
List contains India or not:true
List after removing Australia:[South Africa, India]
Iterating over list:
South Africa
India

Ҳама синфҳое, ки интерфейсро амалӣ мекунанд, Setдар дохor барномаҳо дастгирӣ мешаванд Map. HashSetбо истифода аз элементҳо захира мекунад HashMap. Гарчанде ки HashMapунсур бояд ҳамчун ҷуфти калид-арзиш барои илова кардани элемент муаррифӣ карда шавад, HashSetтанҳо арзиш ба он илова карда мешавад. Дар асл, арзише, ки мо ба он мегузарем , HashSetкалиди an object аст HashMapва доимӣ ҳамчун арзиш истифода мешавад HashMap. Ҳамин тавр, дар ҳар як ҷуфти калидҳо, ҳамаи калидҳо арзиши якхела доранд. Амалиёт HashSetдар java doc:

private transient HashMap map;

// Constructor - 1
// All constructors implicitly create a HashMap object.
public HashSet()
{
    // Create an implicit HashMap object
    map = new HashMap();
}

// Constructor- 2
public HashSet(int initialCapacity)
{
    // Create an implicit HashMap object
    map = new HashMap(initialCapacity);
}

// An object of the Object class, each time acting as a value in the HashMap
private static final Object PRESENT = new Object();

Агар шумо ба усули add()y нигаред HashSet:

public boolean add(E e)
{
   return map.put(e, PRESENT) == null;
}

Шумо метавонед аҳамият диҳед, ки усули add()y HashSetметодро put()дар an objectи дохилӣ даъват мекунад HashMapва ба он элементеро, ки бояд ҳамчун калид илова карда шавад, ва доимии PRESENT ҳамчун арзиш медиҳад. Усул ба ҳамин монанд кор мекунад remove(). Он усули remove()an objectи дохorро даъват мекунад HashMap:

public boolean remove(Object o)
{
  return map.remove(o) == PRESENT;
}

HashSetба ҷадвали ҳаш асос ёфтааст ва илова кардан, нест кардан ё ҷустуҷӯ кардан ба ҳисоби миёна дар вақти доимӣ (O(1)) анҷом хоҳанд ёфт . Усулҳо HashSet:

1. boolean add(E e): элементро ба , илова мекунад HashSet, агар мавҷуд набошад, аммо агар чунин элемент аллакай мавҷуд бошад, усул false -ро бармегардонад .
2. void clear():ҳама элементҳоро аз маҷмӯа хориҷ мекунад.
3. boolean contains(Object o): Ҳақиқатро бармегардонад , агар унсури додашуда дар маҷмӯи мавҷуд бошад.
4. boolean remove(Object o): Агар мавҷуд бошад, элементи додашударо аз маҷмӯи хориҷ мекунад.
5. Iterator iterator(): Итераторро барои унсурҳои маҷмӯа бармегардонад.
6. boolean isEmpty(): Ҳақиқатро бармегардонад , агар дар маҷмӯи унсурҳо мавҷуд набошад.
7. Object clone(): Клонкунии рӯи заминро иҷро мекунад HashSet.

Javadoc: https://docs.oracle.com/javase/7/docs/api/java/util/HashSet.html