HashSet sa Java

Ipinapatupad ng klase HashSetang interface Set, ay batay sa isang hash table, at sinusuportahan din ng isang instance HashMap. Dahil HashSetang mga elemento ay hindi nakaayos, walang garantiya na ang mga elemento ay nasa parehong pagkakasunud-sunod pagkatapos ng ilang panahon. Ang mga operasyon ng pagdaragdag, pagtanggal at paghahanap ay isasagawa sa patuloy na oras, sa kondisyon na ang hash function ay wastong namamahagi ng mga elemento sa "mga bucket", na tatalakayin sa ibang pagkakataon. Ilang mahahalagang punto tungkol sa HashSet:

• kasi ipinapatupad ng klase ang interface Set, maaari lamang itong mag-imbak ng mga natatanging halaga;
• Maaaring mag-imbak ng mga NULL na halaga;
• Ang pagkakasunud-sunod kung saan ang mga elemento ay idinagdag ay kinakalkula gamit ang isang hash code;
• HashSetnagpapatupad din ng Serializableat Cloneable.

Upang mapanatili ang isang pare-parehong oras ng pagpapatupad ng mga operasyon, ang oras na ginugol sa mga aksyon na may HashSet, ay dapat na direktang proporsyonal sa bilang ng mga elemento sa HashSet+ ang "kapasidad" ng built-in na instance HashMap(ang bilang ng mga "basket"). Samakatuwid, upang mapanatili ang pagganap, mahalagang huwag itakda ang paunang kapasidad na masyadong mataas (o masyadong mababa ang load factor). Paunang kapasidad - ang paunang bilang ng mga cell ("bins") sa hash table. Kung ang lahat ng mga cell ay napuno, ang kanilang bilang ay awtomatikong tataas. Ang load factor ay isang sukatan kung gaano ito kapuno HashSetbago awtomatikong tumaas ang kapasidad nito. Kapag ang bilang ng mga elemento sa HashSetay naging mas malaki kaysa sa produkto ng paunang kapasidad at ang load factor, ang hash table ay muling hina-hash (ang mga hash code ng mga elemento ay muling kinakalkula at ang talahanayan ay itinayong muli ayon sa mga nakuhang halaga) at ang numero ang mga cell sa loob nito ay doble. Load factor = Bilang ng mga elemento na nakaimbak sa table / hash table size Halimbawa, kung ang paunang bilang ng mga cell sa table ay 16, at ang load factor ay 0.75, pagkatapos ay sumusunod na kapag ang bilang ng mga filled na cell ay umabot sa 12, ang ang bilang ng mga cell ay awtomatikong tataas. Ang load factor at initial capacity ay ang dalawang pangunahing salik na nakakaapekto sa performance ng HashSet. Ang load factor na 0.75 ay nagbibigay ng magandang performance sa karaniwan. Kung ang parameter na ito ay tumaas, ang memory load ay bababa (dahil babawasan nito ang bilang ng mga re-hashing at muling pagtatayo ng mga operasyon), ngunit ito ay makakaapekto sa mga pagpapatakbo ng append at lookup. Upang mabawasan ang oras na ginugol sa muling pag-hash, kailangan mong piliin ang tamang parameter ng paunang kapasidad. Kung ang paunang kapasidad ay mas malaki kaysa sa maximum na bilang ng mga elemento na hinati sa load factor, walang mangyayaring muling pag-hash. Mahalaga: HashSetay hindi isang istraktura ng data na may built-in na pag-synchronize, kaya kung maraming mga thread ang gumagana sa parehong oras, at hindi bababa sa isa sa mga ito ay sinusubukang gumawa ng mga pagbabago, ito ay kinakailangan upang magbigay ng naka-synchronize na pag-access mula sa labas. Madalas itong ginagawa sa kapinsalaan ng isa pang naka-synchronize na bagay na nakapaloob sa HashSet. Kung walang ganoong bagay, kung gayon ang Collections.synchronizedSet(). Ito ang kasalukuyang pinakamainam na paraan upang maiwasan ang mga out-of-sync na operasyon sa HashSet.

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

Mga tagabuo ng HashSet:

1. HashSet h = new HashSet(); - default na tagabuo. Ang default na paunang kapasidad ay 16, ang load factor ay 0.75.
2. HashSet h = new HashSet(int initialCapacity)– isang constructor na may ibinigay na paunang kapasidad. Salik ng pag-load - 0.75.
3. HashSet h = new HashSet(int initialCapacity, float loadFactor);— isang constructor na may ibinigay na paunang kapasidad at load factor.
4. HashSet h = new HashSet(Collection C)– isang constructor na nagdaragdag ng mga elemento mula sa isa pang koleksyon.

Ang code sa ibaba ay nagpapakita ng ilang mga pamamaraan 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());
    }
}

Konklusyon:

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

Ang lahat ng mga klase na nagpapatupad ng isang interface Setay panloob na sinusuportahan ng mga pagpapatupad Map. HashSetnag-iimbak ng mga elemento gamit ang HashMap. Bagama't HashMapdapat na katawanin ang isang elemento bilang key-value pair para magdagdag ng elemento, HashSetang value lang ang idinaragdag. Sa katunayan, ang value na ipapasa natin HashSetay ang susi sa object HashMap, at isang constant ang ginagamit bilang value HashMap. Sa ganitong paraan, sa bawat key-value pair, lahat ng key ay magkakaroon ng parehong halaga. Pagpapatupad HashSetsa 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();

Kung titingnan mo ang pamamaraan add()y HashSet:

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

Mapapansin mo na tinatawag ng method add()na y ang method sa internal object , na ipinapasa dito ang elementong idaragdag bilang key, at ang PRESENT constant bilang value. Ang pamamaraan ay gumagana sa isang katulad na paraan . Tinatawag nito ang internal object method : HashSetput()HashMapremove()remove()HashMap

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

HashSetay batay sa isang hash table, at magdagdag, magtanggal, o maghanap ng mga operasyon, sa karaniwan, makukumpleto sa pare-pareho (O(1)) na oras . Paraan HashSet:

1. boolean add(E e): nagdadagdag ng isang elemento sa HashSet, kung wala, ngunit kung ang naturang elemento ay naroroon na, ang pamamaraan ay nagbabalik ng false .
2. void clear():inaalis ang lahat ng elemento mula sa isang set.
3. boolean contains(Object o): Nagbabalik ng true kung ang ibinigay na elemento ay nasa set.
4. boolean remove(Object o): Tinatanggal ang ibinigay na elemento mula sa set, kung mayroon.
5. Iterator iterator(): Nagbabalik ng iterator para sa mga elemento ng set.
6. boolean isEmpty(): Nagbabalik ng true kung walang elemento sa set.
7. Object clone(): Nagsasagawa ng surface cloning HashSet.

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