Sets, Queues

ชนิดข้อมูลและการจัดการข้อยกเว้นใน Java

Jim White

Java Developer

Set interface

Set เป็น Collection ประเภทหนึ่ง
- ไม่อนุญาตให้มีออบเจ็กต์ซ้ำกัน
  - รับประกันว่าแต่ละ element มีค่าไม่ซ้ำกัน
- ออบเจ็กต์ใน Set โดยทั่วไปไม่มีลำดับ (จึงไม่มี index)
List เปรียบเหมือนกล่องยา แต่ละออบเจ็กต์อยู่ในช่องที่กำหนด
Set เปรียบเหมือนถุงใส่ของ ออบเจ็กต์อยู่แบบสุ่มโดยไม่มีลำดับ

List เปรียบเหมือนกล่องยา ซึ่งออบเจ็กต์ถูกเก็บตาม index ในตำแหน่งที่กำหนด

Set เปรียบเหมือนถุงที่บรรจุออบเจ็กต์แบบสุ่มและไม่มีลำดับ

¹ ภาพจาก Wikimedia Commons

List vs Set

เมื่อใดควรใช้ Set
- รับประกันความไม่ซ้ำของ element
- ค้นหาได้เร็วกว่า
  - ตรวจสอบว่าออบเจ็กต์อยู่ใน Set หรือไม่
- ใช้หน่วยความจำน้อยลงเมื่อ collection มีขนาดใหญ่ขึ้น
- เหมาะสำหรับการตรวจสอบสมาชิกใน cache
  - ตัวอย่าง: ค้นหาคำที่ไม่ซ้ำกันในเอกสาร

List vs Set

เมื่อใดควรใช้ List
- คงลำดับของ element และรองรับค่าซ้ำได้
- เข้าถึง element ตามตำแหน่งได้เร็วกว่า
- เพิ่ม/ลบ element ตาม index ได้เร็วกว่า
- เหมาะเมื่อลำดับของ element มีความสำคัญ
  - เช่น: จัดการขั้นตอนลำดับงาน หรือเพลงใน playlist

Set implementation

Set มีหลาย implementation
- HashSet เป็น implementation ที่นิยมใช้
HashSet
- ถุงออบเจ็กต์ที่ไม่มีลำดับ
- เร็วกว่า Set implementation อื่นในการ insert, delete และค้นหา
- โดยทั่วไปใช้หน่วยความจำมากกว่า Set implementation อื่น
- รองรับการเก็บ null ได้หนึ่งค่า

HashSet คือถุงออบเจ็กต์ที่ไม่มีลำดับและรับ null ได้หนึ่งค่า

HashSet construction

ใช้ generic parameterized constructor เพื่อสร้าง HashSet
```
HashSet<String> set = new HashSet<String>();
```
HashSet อยู่ใน package java.util
- ต้องทำการ import
- import java.util.HashSet

HashSet methods

ใช้ .add() และ .remove() เพื่อเพิ่มและลบออบเจ็กต์
ใช้ .remove() แล้วตามด้วย .add() เพื่อแทนที่ออบเจ็กต์
ใช้ .contains() เพื่อตรวจสอบว่ามีออบเจ็กต์อยู่แล้วหรือไม่
ค่าซ้ำจะถูกละเว้น
รองรับ null
ไม่รับประกันลำดับ

set.add("France");
set.add("Japan");
set.add("Brazil");
set.add("Egypt");
set.add(null); // null is allowed
set.remove("Brazil");

boolean z =
  set.contains("France"); // z is true
set.add("Japan"); // Ignored
System.out.println(set);

[null, Japan, Egypt, France]

Queue interface

โครงสร้างข้อมูล Queue ประมวลผลออบเจ็กต์แบบ first in, first out (FIFO)
- ออบเจ็กต์ที่เพิ่มเข้าก่อนจะถูกนำออกก่อน
- เปรียบเหมือนคิวที่ช่องขายตั๋ว
- มีออบเจ็กต์ head และ tail

ภาพ queue แสดง head (ต้น) และ tail (ปลาย)

Queue มีหลาย implementation
- พฤติกรรมและการดำเนินการใกล้เคียงกัน

ArrayBlockingQueue

Queue implementation ที่นิยมใช้
- ใช้ array เป็นโครงสร้างภายใน
ข้อควรระวัง: ArrayBlockingQueue อยู่ใน package java.util.concurrent
- ไม่ใช่ package java.util

ArrayBlockingQueue construction

ใช้ generic parameterized constructor เพื่อสร้าง ArrayBlockingQueue
- ต้องระบุขีดความสามารถ (จำนวนออบเจ็กต์สูงสุด) ตอนสร้าง

import java.util.concurrent;  // At the top of the class

// Create new queue that can store 4 Strings
ArrayBlockingQueue<String> queue = new ArrayBlockingQueue<String>(4);

ArrayBlockingQueue methods

ใช้ .add(object) หรือ .offer(object) เพื่อเพิ่มไปที่ tail
- .add(object) โยน exception เมื่อ Queue เต็ม
- .offer(object) ละเว้นออบเจ็กต์ใหม่เมื่อ Queue เต็ม

ArrayBlockingQueue<String> queue 
    = new ArrayBlockingQueue<String>(4);
queue.offer("France");
queue.offer("Japan");
queue.offer("Brazil");
queue.offer("Egypt");
queue.offer("China"); // Ignores China

// Causes IllegalStateException
// queue.add("China");

System.out.println(queue);

[France, Japan, Brazil, Egypt]

ArrayBlockingQueue methods

ใช้ .remove() หรือ .poll() เพื่อลบออบเจ็กต์จาก head
- .remove() โยน exception เมื่อ Queue ว่างเปล่า
- .poll() คืนค่า null เมื่อ Queue ว่างเปล่า
ไม่รองรับ null

ArrayBlockingQueue<String> queue 
    = new ArrayBlockingQueue<String>(4);
String x = queue.poll(); // x is null
// Causes NoSuchElementException
// String y = queue.remove();

queue.offer("France");
String next = queue.poll();
System.out.println(next);

France

มาฝึกกันเถอะ!

ชนิดข้อมูลและการจัดการข้อยกเว้นใน Java