HashSet ใน Java

คลาสHashSetใช้อินเทอร์เฟซSetขึ้นอยู่กับตารางแฮช และยังได้รับการสนับสนุนโดยอินสแตนซ์อีกด้วย HashMapเนื่องจากHashSetองค์ประกอบไม่ได้รับการเรียงลำดับ จึงไม่รับประกันว่าองค์ประกอบจะอยู่ในลำดับเดียวกันหลังจากผ่านไประยะหนึ่ง การดำเนินการเพิ่ม ลบ และค้นหาจะดำเนินการในเวลาคงที่ โดยมีเงื่อนไขว่าฟังก์ชันแฮชจะกระจายองค์ประกอบออกเป็น "ที่เก็บข้อมูล" อย่างถูกต้อง ซึ่งจะกล่าวถึงในภายหลัง ประเด็นสำคัญบางประการเกี่ยวกับHashSet:

• เพราะ คลาสใช้อินเทอร์เฟซSetมันสามารถเก็บเฉพาะค่าที่ไม่ซ้ำเท่านั้น
• สามารถเก็บค่า NULL ได้
• ลำดับการเพิ่มองค์ประกอบจะถูกคำนวณโดยใช้รหัสแฮช
• HashSetยังใช้SerializableและCloneable.

เพื่อรักษาเวลาดำเนินการของการดำเนินการให้คงที่ เวลาที่ใช้ในการดำเนินการกับHashSetจะต้องเป็นสัดส่วนโดยตรงกับจำนวนองค์ประกอบในHashSet+ “ความจุ” ของอินสแตนซ์ในตัวHashMap(จำนวน “ตะกร้า”) ดังนั้น เพื่อรักษาประสิทธิภาพไว้ จึงเป็นสิ่งสำคัญที่จะไม่ตั้งค่าความจุเริ่มต้นสูงเกินไป (หรือปัจจัยโหลดต่ำเกินไป) ความจุเริ่มต้น – จำนวนเซลล์เริ่มต้น (“ถังขยะ”) ในตารางแฮช หากเต็มเซลล์ทั้งหมด จำนวนเซลล์จะเพิ่มขึ้นโดยอัตโนมัติ ตัวประกอบภาระคือการวัดว่าความจุจะเต็มได้แค่ไหนHashSetก่อนที่ความจุจะเพิ่มขึ้นโดยอัตโนมัติ เมื่อจำนวนองค์ประกอบในHashSetมากกว่าผลคูณของความจุเริ่มต้นและปัจจัยโหลด ตารางแฮชจะถูกแฮชอีกครั้ง (รหัสแฮชขององค์ประกอบจะถูกคำนวณใหม่ และสร้างตารางใหม่ตามค่าที่ได้รับ) และจำนวน ของเซลล์ในนั้นเพิ่มขึ้นเป็นสองเท่า Load factor = จำนวนองค์ประกอบที่จัดเก็บไว้ในตาราง / ขนาดตารางแฮช เช่น หากจำนวนเซลล์เริ่มต้นในตารางคือ 16 และ Load Factor เท่ากับ 0.75 ก็จะตามมาว่าเมื่อจำนวนเซลล์ที่เติมถึง 12 เซลล์จะ จำนวนเซลล์จะเพิ่มขึ้นโดยอัตโนมัติ ตัวประกอบภาระและกำลังการผลิตเริ่มต้นเป็นสองปัจจัยหลักที่ส่งผลต่อประสิทธิภาพHashSetของ โหลดแฟคเตอร์ที่ 0.75 ให้ประสิทธิภาพที่ดีโดยเฉลี่ย หากพารามิเตอร์นี้เพิ่มขึ้น โหลดหน่วยความจำจะลดลง (เนื่องจากจะลดจำนวนแฮชใหม่และการสร้างใหม่) แต่จะส่งผลต่อการดำเนินการผนวกและค้นหา เพื่อลดเวลาที่ใช้ในการแฮชซ้ำ คุณต้องเลือกพารามิเตอร์ความจุเริ่มต้นที่เหมาะสม หากความจุเริ่มต้นมากกว่าจำนวนองค์ประกอบสูงสุดหารด้วยปัจจัยโหลด จะไม่มีการดำเนินการแฮชซ้ำเลย สำคัญ: HashSetไม่ใช่โครงสร้างข้อมูลที่มีการซิงโครไนซ์ในตัว ดังนั้นหากหลายเธรดกำลังทำงานอยู่ในเวลาเดียวกัน และอย่างน้อยหนึ่งเธรดกำลังพยายามทำการเปลี่ยนแปลง จำเป็นต้องจัดเตรียมการเข้าถึงแบบซิงโครไนซ์จากภายนอก สิ่งนี้มักจะทำโดยเสียค่าใช้จ่ายของวัตถุซิงโครไนซ์อื่นที่ห่อหุ้มไฟล์HashSet. หากไม่มีวัตถุดังกล่าว ดังนั้นCollections.synchronizedSet(). ขณะนี้นี่เป็นวิธีที่ดีที่สุดในการป้องกันไม่ให้การดำเนินการไม่ซิงค์กันHashSetด้วย

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

ตัวสร้าง HashSet:

1. HashSet h = new HashSet(); - ตัวสร้างเริ่มต้น ความจุเริ่มต้นเริ่มต้นคือ 16 ตัวประกอบการโหลดคือ 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รับการสนับสนุนภายในโดยการใช้งาน เก็บองค์ประกอบโดยใช้. แม้ว่าองค์ประกอบจะต้องแสดงเป็นคู่คีย์-ค่าเพื่อเพิ่มองค์ประกอบ แต่จะเพิ่มเฉพาะค่าเท่านั้น อันที่จริง ค่าที่เราส่งไปคือกุญแจสำคัญไปยังอ็อบเจ็กต์และใช้ค่าคงที่เป็นค่า ด้วยวิธีนี้ ในทุกคู่คีย์-ค่า คีย์ทั้งหมดจะมีค่าเท่ากัน การนำไปปฏิบัติใน:MapHashSetHashMapHashMap HashSetHashSetHashMapHashMapHashSetjava 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()บนวัตถุภายในHashMapโดยส่งผ่านองค์ประกอบที่จะเพิ่มเป็นคีย์ และค่าคงที่ PRESENT เป็นค่า วิธีการทำงานในลักษณะremove()เดียวกัน มันเรียก วิธี remove()การวัตถุภายใน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