Bab.8 Framework
Koleksi JAVA
|
Tujuan Instruksional
|
|
|
·
Mendeskripsikan hirarki JAVA Collections
Framework (JCF).
·
Menggunakan metode-metode umum yang
didefinisikan di dalam antarmuka Collection
untuk mengeporasikan himpunan (set) dan daftar (list).
·
Menggunakan antarmuka Iterator.
·
Menggunakan loop for-each untuk
menyederhanakan koleksi.
·
Mengeksplorasi bagaimana dan kapan menggunakan
HashSet, LinkedHashSet, atau TreeSet.
·
Membandingkan elemen menggunakan antarmuka Comparable dan antarmuka Comparator.
·
Mengeksplorasi bagaimana dan kapan menggunakan
ArrayList atau LinkedList untuk menyimpan elemen.
·
Menggunakan metode-metode utilitas statik di
dalam kelas Collections untuk
mengurutkan, mencari, mengacak list, dan menemukan elemen terbesar dan
terkecil di dalam koleksi.
|
·
Membandingkan kinerja set dan list.
·
Membedakan antara Vector dan ArrayList
dan untuk menggunakan kelas Stack
untuk menciptakan tumpukan.
·
Mengeksplorasi relasi di antara Collection, Queue, LinkedList, dan
PriorityQueue dan untuk
menciptakan antrian menggunakan kelas PriorityQueue.
·
Mengetahui perbedaan antara Collection dan Map dan menjelaskan kapan dan bagaimana menggunakan HashMap, LinkedHashMap, dan TreeMap
untuk menyimpan nilai-nilai yang berkaitan dengan kunci.
|
8.1
Introduksi
Struktur data merupakan koleksi data yang
diorganisasi dengan gaya tertentu. Struktur tidak hanya menyimpan data tetapi
juga mendukung operasi-operasi untuk mengakses dan memanipulasi data. Anda
telah belajar tentang ArrayList,
yang merupakan suatu struktur data untuk menyimpan elemen-elemen di dalam suatu
list atau daftar atau senarai. JAVA menyediakan beberapa struktur data tambahan
yang dapat digunakan untuk mengorganisasi dan memanipulasi data. secara
efisien. Struktur-struktur data tersebut dikenal dengan framework koleksi JAVA
(JCF, JAVA Collections Framework).
Dalam pemikiran berorientasi-objek, suatu
struktur data, yang juga dikenal dengan kontainer, adalah suatu objek yang bisa
menyimpan objek lain, yang dikenal dengan data atau elemen. Beberapa pihak
menyebut struktur data sebagai objek kontainer. Mendefinisikan struktur data
sama dengan mendefinisikan kelas. Kelas untuk suatu struktur data harus
menggunakan bidang-bidang data untuk menyimpan data dan menyediakan beberapa
metode untuk mendukung operasi-operasi seperti pencarian, penyisipan, dan
penghapusan. Menciptakan suatu struktur data sama dengan menciptakan suatu
instans dari kelas. Anda bisa menerapkan metode-metode terhadap instans
tersebut untuk memanipulasi struktur data, seperti menyisipkan suatu elemen ke
atau menghapus suatu elemen dari struktur data.
JCF mendukung dua jenis kontainer:
·
Satu untuk menyimpan sekoleksi
elemen, yang dikenal dengan koleksi.
·
Lainnya untuk menyimpan pasangan
kunci/nilai, yang disebut dengan peta.
Peta atau map merupakan struktur data yang
efisien untuk melakukan pencarian cepat suatu elemen menggunakan kunci. Anda
akan dikenalkan tentang peta pada bab ini. Sekarang, akan didiskusikan terlebih
dahulu tentang koleksi.
8.2
Koleksi
JCF
mendukung tiga koleksi utama: Set, List, dan Queue. Suatu instans dari Set
menyimpan sekelompok elemen non-duplikat. Suatu instans dari List menyimpan sekumpulan elemen yang
terurut. Suatu instans dari Queue
menyimpan objek-objek yang diproses dengan gaya FIFO (first-in, first-out). Fitur-fitur umum koleksi ini didefinisikan di dalam beberapa
antarmuka, dan implementasinya disediakan di dalam kelas-kelas konkrit, seperti
tertampil pada Gambar 8.2.
Gambar 8.1 Koleksi merupakan suatu kontainer yang memuat
objek-objek
8.3
Antarmuka Collection dan Kelas AbstractCollection
Antarmuka Collection merupakan antarmuka akar untuk memanipulasi sekumpulan
objek. Beberapa metode publik ditampilkan pada Gambar 8.2. Kelas AbstractCollection merupakan suatu
kelas yang menyediakan implementasi parsial untuk antarmuka Collection. Kelas tersebut
mengimplementasikan semua metode di dalam Collection
kecuali metode size dan iterator.
Antarmuka Collection menyediakan operasi-operasi dasar untuk menambah dan
menghapus elemen di dalam suatu koleksi. Metode add menambah suatu elemen pada koleksi. Metode addAll menambah semua elemen di dalam koleksi tertentu pada koleksi
lain. Metode remove menghapus atau
membuang suatu elemen dari koleksi. Metode removeAll
menghapus semua elemen dari koleksi yang ada pada koleksi tertentu. Metode retainAll mendapatkan elemen-elemen
dalam koleksi yang ada pada koleksi tertentu. Semu metode ini mengembalikan boolean. Nilai balik true jika koleksi diubah sebagai akibat
dari eksekusi metode. Metode clear()
menghapus semua elemen dari koleksi.
Gambar 8.2 Antarmuka Collection memuat metode-metode untuk memanipulasi elemen-elemen di
dalam suatu koleksi, dan Anda bisa mendapatkan suatu objek iterator untuk menjelajah
elemen-elemen di dalam koleksi
Antarmuka Collection menyediakan berbagai operasi query. Metode size mengembalikan jumlah elemen di
dalam koleksi. Metode contains
memeriksa apakah koleksi mempunyai elemen tertentu. Metode containsAll memeriksa apakah koleksi mempunyai semua elemen di
dalam koleksi tertentu. Metode isEmpty
mengembalikan true jika koleksi kosong.
Antarmuka Collection menyediakan metode toArray()
yang mengembalikan suatu representasi array untuk koleksi.
Koleksi bisa berupa set atau list. Antarmuka Iterator menyediakan suatu cara seragam
untuk menjelajah elemen-elemen dalam berbagai jenis koleksi. Metode iterator
dalam antarmuka Collection
mengembalikan suatu instans dari antarmuka Iterator,
seperti tertampil pada Gambar 8.2, yang menyediakan akses sekuensial terhadap
elemen-elemen dalam koleksi menggunakan metode next(). Anda juga bisa menggunakan metode hasNext() untuk memeriksa apakah masih terdapat elemen di dalam
iterator, dan metode remove() untuk
menghapus elemen terakhir yang dikembalikan oleh iterator.
8.4
Set
Antarmuka Set mewarisi antarmuka Collection.
Antarmuka ini tidak memiliki metode atau konstanta baru, tetapi menjamin bahwa
suatu instans Set tidak memiliki
elemen-elemen duplikat. Kelas konkrit yang mengimplementasikan Set harus memastikan bahwa tidak
terdapat elemen duplikat yang dapat ditambahkan ke dalam set. Yaitu, tidak
terdapat dua elemen e1 dan e2 yang berada di dalam set yang
membuat e1.equals(e2) bernilai true.
Gambar 8.3 JCF menyediakan tiga kelas set konkrit
Kelas AbstractSet
merupakan kelas yang mewarisi AbstractCollection
dan yang mengimplementasikan Set.
Kelas AbstractSet menyediakan
implementasi konkrit untuk metode equals
dan metode hashCode. Kode hash atas
suatu set adalah penjumlahan atas kode hash dari semua elemen di dalam set.
Karena metode size dan metode iterator tidak diimplementasikan di
dalam kelas AbstractSet, maka AbstractSet merupakan suatu kelas
abstrak.
Tiga kelas konkrit dari Set adalah HashSet, LinkedSet, dan TreeSet, seperti ditampilkan pada Gambar 8.3.
8.4.1
HashSet
Kelas HashSet merupakan suatu kelas konkrit
yang mengimplementasikan Set. Anda
bisa menciptakan suatu hash kosong menggunakan konstruktor tanpa-argumen atau
menciptkan suatu set hash dari koleksi yang ada. Secara default, kapasitas awal
adalah 16 dan faktor beban adalah 0.75. Jika Anda mengetahui ukuran set Anda,
maka Anda bisa menspesifikasi kapasitas awal dan faktor beban di dalam
konstruktor. Sebaliknya bila Anda tidak mengetahuinya, sebaiknya digunakan
spesifikasi default. Faktor beban merupakan suatu nilai antara 0.0 sampai 1.0.
Faktor
beban merupakan takaran untuk mengukur seberapa penuh suatu set diijinkan
sebelum kapasitasnya ditambah. Ketika jumlah elemen melebihi perkalian antara
kapasitas dengan faktor beban, kapasitas secara otomatis akan digandakan. Sebagai
contoh, jika kapasitas adalah 16 dan faktor beban adalah 0.75, maka kapasitas
akan digandakan menjadi 32 bila ukuran set meraih 12 (16 * 0.75 = 12). Faktor
beban yang lebih tinggi akan mengurangi biaya memori namun meningkatkan waktu
pencarian. Secara umum, faktor beban default 0.75 merupakan pilihan terbaik
mengingat pertimbangan biaya memori dan waktu pencarian.
HashSet dapat
digunakan untuk menyimpan elemen-elemen bebas-duplikat. Demi efisiensi,
objek-objek yang ditambahkan ke dalam set hash perlu mengimplementasikan metode
hashCode. Ingat bahwa hashCode didefinisikan di dalam kelas Object. Kode hash atas dua objek harus
sama bila kedua objek adalah sama. Dua objek yang tidak sama bisa jadi memiliki
kode hash yang sama, tetapi Anda harus mengimplementasikan metode hashCode untuk menghindari terlalu
banyak kasus seperti itu. Kebanyakan kelas dalam JAVA API mengimplementasikan hashCode. Sebagai contoh, hashCode di dalam kelas Integer mengembalikan nilai balik int. hashCode di dalam kelas Character
mengembalikan kode Unicode atas suatu karakter. hashCode di dalam kelas String
mengembalikan
, dimana
adalah s.charAt(i).
Kode8.1
menyajikan suatu program yang menciptakan suatu set hash untuk menyimpan
string-string dan menggunakan suatu iterator untuk menjelajah elemen-elemen di
dalam set tersebut.
Kode8.1 UjiSetHash.java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
import java.util.*;
public class UjiSetHash {
public static void main(String[]
args) {
// Menciptakan suatu set hash
Set<String> set = new HashSet<String>();
// Menambahkan string-string ke dalam set
set.add("Klaten");
set.add("Balige");
set.add("Jogjakarta");
set.add("Mataram");
set.add("Siantar");
set.add("Jogjakarta ");
System.out.println(set);
// Mendapatkan suatu iterator untuk set
hash
Iterator<String> iterator = set.iterator();
// Menampilkan elemen-elemen di dalam set
hash
while(iterator.hasNext()) {
System.out.print(iterator.next().toUpperCase() + "
");
}
}
}
|
Keluaran
[Klaten, Jogjakarta,
Mataram, Siantar, Balige]
KLATEN JOGJAKARTA MATARAM
SIANTAR BALIGE
String-string
ditambahkan ke dalam set (baris 9-14). “Jogjakarta”ditambahkan
dua kali ke dalam set, namun hanya satu yang disimpan, karena set tidak
mengijinkan duplikasi elemen.
Seperti
yang tertampil di dalam keluaran, string-string tidak disimpan terurut sesuai
saat disisipkan ke dalam set. Tidak ada urutan khusus di dalam set hash. Untuk
menerapkan suatu urutan, Anda perlu menggunakan kelas LinkedHashSet, yang akan dikenalkan pada bagian selanjutnya.
Karena
set merupakan suatu instans dari Collection,
semua metode yang didefinisikan dalam Collection
dapat digunakan untuk set. Kode8.2 menyajikan suatu contoh yang mengeksplorasi
metode-metode di dalam antarmuka Collection.
Kode8.2 UjiMetodeDlmKoleksi.java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
public class UjiMetodeDlmKoleksi {
public static void main(String[]
args) {
// Menciptakan set1
java.util.Set<String> set1 = new
java.util.HashSet<String>();
// Menambahkan string ke dalam set1
set1.add("Batam");
set1.add("Siantar");
set1.add("Tebing Tinggi");
set1.add("Bandung");
set1.add("Bekasi");
System.out.println("set1 adalah
" + set1);
System.out.println(set1.size() + " elemen di dalam set1");
// Menghapus suatu string dari set1
set1.remove("Batam");
System.out.println("\nset1 adalah
" + set1);
System.out.println(set1.size() + " elemen
di dalam set1");
// Menciptakan set2
java.util.Set<String> set2 = new
java.util.HashSet<String>();
// Menambahkan string ke dalam set2
set2.add("Batam");
set2.add("Mataram");
set2.add("Bekasi");
System.out.println("\nset2 adalah
" + set2);
System.out.println(set2.size() + " elemen di dalam set2");
System.out.println("\nApakah
Klaten di dalam set2? "
+ set2.contains("Klaten"));
set1.addAll(set2);
System.out.println("\nSetelah
menambah set2 ke dalam set1, set1 adalah "
+ set1);
set1.removeAll(set2);
System.out.println("Setelah
menghilangkan set2 dari set1, set1 adalah "
+ set1);
set1.retainAll(set2);
System.out.println("Setelah
menghilangkan elemen sama di dalam set2 "
+ "dari set1, set1 adalah
" + set1);
}
}
|
Keluaran
set1 adalah [Bandung,
Tebing Tinggi, Bekasi, Batam, Siantar]
5 elemen di dalam set1
set1 adalah [Bandung,
Tebing Tinggi, Bekasi, Siantar]
4 elemen di dalam set1
set2 adalah [Bekasi, Batam,
Mataram]
3 elemen di dalam set2
Apakah Klaten di dalam
set2? false
Setelah menambah set2 ke
dalam set1, set1 adalah
[Bandung, Tebing Tinggi, Batam, Bekasi,
Mataram, Siantar]
Setelah menghilangkan set2
dari set1, set1 adalah
[Bandung, Tebing Tinggi, Siantar]
Setelah menghilangkan
elemen-elemen sama di dalam set2 dari set1, set1 adalah []
Program
menciptakan dua set (baris 4, 22). Metode size()
mengembalikan jumlah elemen di dalam suatu set (baris 14). Baris 17
set1.add("Batam");
menghilangkan
“Batam” dari set1. Metode contains
(baris 32) memeriksa apakah suatu elemen berada di dalam set atau tidak. Baris
34
set1.addAll(set2);
menambahkan set2 ke dalam set1.
Jadi, set1 menjadi [Bandung, Tebing Tinggi, Batam, Bekasi,
Mataram, Siantar].
Baris 38
set1.removeAll(set2);
menghapus
set2 dari set1. Jadi set1 menjadi [Bandung, Tebing Tinggi, Siantar].
Baris 42
set1.retainAll(set2);
menempatkan
elemen-elemen sama ke dalam set1.
Karena set1 dan set2 tidak memiliki elemen yang sama, set1 menjadi kosong.
8.4.2
LinkedHashSet
LinkedHashSet mewarisi
HashSet dengan implementasi
list-berantai atau senarai-berantai yang mendukung pengurutan elemen di dalam
set. Elemen-elemen di dalam HashSet
tidak terurut, tetapi elemen-elemen di dalam LinkedHashSet dapat dibuat berurutan seperti saat disisipkan ke
dalam set. LinkedHashSet dapat
diciptakan menggunakan salah satu dari empat konstruktornya, seperti
ditampilkan pada Gambar 8.3. Keempat konstruktor tersebut sama dengan
konstruktor pada HashSet.
Kode8.3
menyajikan suatu program uji untuk LinkedHashSet.
Program cuma mengganti HashSet pada
kode8.1 dengan LinkedHashSet.
Kode8.3 UjiLinkedHashSet.java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
import java.util.*;
public class UjiLinkedHashSet {
public static void main(String[]
args) {
// Menciptakan suatu set hash
Set<String> set = new LinkedHashSet<String>();
// Menambahkan string-string ke dalam set
set.add("Klaten");
set.add("Balige");
set.add("Jogjakarta");
set.add("Mataram");
set.add("Siantar");
set.add("Jogjakarta ");
System.out.println(set);
// Mendapatkan suatu iterator untuk set
hash
Iterator<String> iterator = set.iterator();
// Menampilkan elemen-elemen di dalam set
hash
while(iterator.hasNext()) {
System.out.print(iterator.next().toUpperCase() + "
");
}
}
}
|
Keluaran
[Klaten, Balige,
Jogjakarta, Mataram, Siantar]
KLATEN BALIGE JOGJAKARTA
MATARAM SIANTAR
Suatu LinkedHashSet diciptakan pada baris 6.
Seperti tertampil pada keluaran, string disimpan berurutan sama seperti ketika
dimasukkan ke dalam set. Karena LinkedHashSet
merupakan suatu set, LinkedHashSet tidak bisa menyimpan elemen-elemen duplikat.
LinkedHashSet
mempertahankan urutan ketika dimasukkan ke dalam set. Untuk memaksakan urutan
lain (misalnya, urutan menaik atau menurun), Anda bisa menggunakan kelas TreeSet yang akan dikenalkan pada
bagian selanjutnya.
8.4.3
TreeSet
SortedSet
merupakan suatu subantarmuka dari Set,
yang menjamin bahwa elemen-elemen di dalam set diurutkan. Lebih lagi,
subantarmuka SortedSet menyediakan
metode first() dan last() untuk mengembalikan elemen
pertama dan elemen terakhir di dalam suatu set, dan metode headSet(toElement) dan tailSet(fromElement)
untuk mengembalikan sebagian dari set yang memiliki elemen-elemen kurang dari toElement dan lebih dari atau sama
dengan fromElement.
NavigableSet mewarisi
SortedSet untuk menyediakan
metode-metode navigasi lower(e), floor(e), ceiling(e), dan higher(e)
yang mengembalikan elemen-elemen kurang dari, kurang dari atau sama dengan,
lebih dari atau sama dengan, dan lebih dari suatu elemen yang diberikan dan
mengembalikan null jika tidak
ditemukan elemen-elemen seperti itu. Metode pollFirst() dan pollLast()
menghapus dan mengembalikan elemen pertama dan elemen terakhir di dalam TreeSet.
TreeSet
mengimplementasikan antarmuka SortedSet.
Untuk menciptakan suatu TreeSet,
digunakan konstruktor, seperti tertampil pada Gambar 8.3. Anda bisa menambahkan
objek-objek ke dalam set tree sepanjang objek-objek tersebut bisa dibandingkan
satu sama lain. Ada dua cara membandingkan objek:
·
Menggunakan antarmuka Comparable.
Karena objek-objek yang ditambahkan ke dalam set merupakan instans dari Comparable, objek-objek tersebut bisa
dibandingkan menggunakan metode compareTo.
Beberapa kelas dalam JAVA API, seperti String,
Date, Calendar, dan semua kelas wrapper untuk tipe primitif,
mengimplementasikan antarmuka Comparable.
Pendekatan ini dinamai urutan alamiah.
·
Jika kelas tidak mengimplementasikan antarmuka Comparable, atau jika Anda tidak ingin menggunakan metode compareTo di dalam kelas yang
mengimplementasikan antarmuka Comparable,
maka spesifikasi suatu komparator untuk elemen-elemen di dalam set. Pendekatan
ini dinamai dengan urutan dengan komparator.
Kode8.4
menyajikan suatu contoh untuk mengurutkan elemen-elemen menggunakan antarmuka Comparable. Contoh terdahulu pada
kode8.3 menampilkan semua string dalam urutan yang sama ketika dimasukkan.
Contoh ini menulis-ulang contoh terdahulu untuk menampilkan string-string dalam
urutan alfabetikal menggunakan kelas TreeSet.
Kode8.4 UjiTreeSet.java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
import java.util.*;
public class UjiTreeSet {
public static void main(String[]
args) {
// Menciptakan suatu set hash
Set<String> set = new HashSet<String>();
// Menambah string ke dalam set
set.add("Klaten");
set.add("Balige");
set.add("Jogjakarta");
set.add("Mataram");
set.add("Siantar");
set.add("Jogjakarta");
TreeSet<String> treeSet = new
TreeSet<String>(set);
System.out.println("Set tree
terurut: " + treeSet);
// Menggunakan metode-metode dalam
antarmuka SortedSet
System.out.println("first():
" + treeSet.first());
System.out.println("last():
" + treeSet.last());
System.out.println("headSet():
" + treeSet.headSet("Jogjakarta"));
System.out.println("tailSet():
" + treeSet.tailSet("Jogjakarta"));
// Menggunakan metode-metode dalam
antarmuka NavigableSet
System.out.println("lower(\"P\"):
" + treeSet.lower("P"));
System.out.println("higher(\"P\"):
" + treeSet.higher("P"));
System.out.println("floor(\"P\"):
" + treeSet.floor("P"));
System.out.println("ceiling(\"P\"):
" + treeSet.ceiling("P"));
System.out.println("pollFirst():
" + treeSet.pollFirst());
System.out.println("pollLast():
" + treeSet.pollLast());
System.out.println("New tree set:
" + treeSet);
}
}
|
Keluaran
Set tree terurut: [Balige,
Jogjakarta, Klaten, Mataram, Siantar]
first(): Balige
last(): Siantar
headSet(): [Balige]
tailSet(): [Jogjakarta,
Klaten, Mataram, Siantar]
lower("P"):
Mataram
higher("P"):
Siantar
floor("P"):
Mataram
ceiling("P"):
Siantar
pollFirst(): Balige
pollLast(): Siantar
New tree set: [Jogjakarta,
Klaten, Mataram]
Contoh
ini menciptakan suatu set hash yang diisi dengan string, kemudian menciptakan
suatu set tree yang diisi dengan string yang sama. String-string tersebut
diurutkan di dalam set tree menggunakan metode compareTo di dalam antarmuka Comparable.
Elemen-elemen
di dalam set diurutkan begitu Anda menciptakan objek TreeSet dari suatu objek HashSet
menggunakan new TreeSet(hashSet)
(baris 16). Anda bisa menulis-ulang program untuk menciptakan suatu instans TreeSet menggunakan konstruktor
tanpa-argumennya, dan menambahkan string-string ke dalam objek TreeSet. Kemudian, setiap kali string
ditambahkan ke dalam objek TreeSet,
elemen-elemen di dalamnya akan diurutkan-ulang. Pendekatan yang digunakan dalam
contoh ini secara umum lebih efisien karena hanya memerlukan pengurutan
satu-kali.
Metode treeSet.first() mengembalikan elemen
pertama di dalam treeSet (baris 20).
Metode treeSet.last() mengembalikan
elemen terakhir di dalam treeSet
(baris 21). Metode treeSet.headSet(“Jogjakarta”)
mengembalikan elemen-elemen di dalam treeSet
sebelum Jogjakarta (baris 22). Metode treeSet.tailSet(“Jogjakarta”)
mengembalikan elemen-elemen di dalam treeSet
setelah Jogjakarta, termasuk Jogjakarta (baris 23).
Metode treeSet.lower(“P”) mengembalikan elemen
terbesar yang kurang dari “P” di
dalam treeSet (baris 26). Metode treeSet.higher(“P”) mengembalikan
elemen terkecil yang lebih dari “P”
di dalam treeSet (baris 27). Metode treeSet.floor(“P”) mengembalikan elemen
terbesar yang kurang dari atau sama dengan “P” di dalam treeSet
(baris 28). Metode treeSet.ceiling(“P”)
mengembalikan elemen terkecil yang lebih dari atau sama dengan “P” di dalam treeSet (baris 29). Metode treeSet.pollFirst()
menghapus elemen pertama di dalam treeSet
dan mengembalikan elemen yang dihapus (baris 30). Metode treeSet.pollLast() menghapus elemen terakhir di dalam treeSet dan mengembalikan elemen yang
dihapus (baris 31).
8.5
Antarmuka Comparator
Kadangkala
Anda ingin menyisipkan elemen-elemen ke dalam suatu set tree. Elemen-elemen
tersebut bisa jadi bukan instans dari java.lang.Comparable.
Anda dapat mendefinisikan suatu komparator untuk membandingkan elemen-elemen
ini. Untuk melakukannya, perlu diciptakan suatu kelas yang mengimplementasikan
antarmuka java.util.Comparator.
Antarmuka Comparator memiliki dua
metode, compare dan equals.
·
public int compare(Object elemen1, Object
elemen2)
Mengembalikan suatu nilai negatif jika elemen1 lebih kecil dari elemen2, suatu nilai positif jika elemen1 lebih besar dari elemen2, dan nilai nol jika elemen1 sama dengan elemen2.
·
public boolean equals(Object elemen)
Mengembalikan true
jika objek yang dispesifikasi juga merupakan suatu komparator dan menerapkan
pengurutan yang sama seperti komparator ini.
Metode equals juga didefinisikan di dalam
kelas Object. Oleh karena itu, Anda
tidak akan mendapatkan error kompilasi bahkan bila Anda tidak
mengimplementasikan metode equals di
dalam kelas komparator Anda. Namun, dalam beberapa kasus, pengimplementasian metode
ini dapat memperbaiki kinerja dengan mengijinkan program untuk menentukan
secara cepat apakah dua komparator yang berbeda dapat menerapkan pengurutan
yang sama.
Kode8.5
mendefinisikan suatu Comparator
untuk objek-objek geometri. ObjekGeometri
didefinisikan dalam Bab 1. Baris 4 mengimplementasikan Comparator<ObjekGeometri>. Baris 5 mengoverride metode compare untuk membandingkan dua objek
geometri. Kelas komparator tersebut juga mengimplementasikan Serializable. Agar struktur data dapat
berhasil diserialkan, komparator harus mengimplementasikan Serializable.
Kode8.5 KomparatorObjekGeometri.java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
import java.util.Comparator;
public class KomparatorObjekGeometri
implements Comparator<ObjekGeometri>, java.io.Serializable
{
public int compare(ObjekGeometri o1, ObjekGeometri o2){
double luas1 = o1.dapatLuas();
double luas2 = o2.dapatLuas();
if (luas1 < luas2)
return -1;
else if (luas1 == luas2)
return 0;
else
return 1;
}
}
|
Jika Anda
menciptakan suatu TreeSet
menggunakan konstruktor tanpa-argumennya, maka metode compareTo digunakan untuk membandingkan elemen-elemen di dalam set,
dengan asumsi bahwa kelas dari elemen-elemen tersebut mengimplementasikan Comparable. Untuk menggunakan suatu
komparator, Anda harus menggunakan konstruktor TreeSet(Comparator komparator) untuk menciptakan suatu set terurut
yang menggunakan metode compare di
dalam komparator untuk mengurutkan elemen-elemen di dalam set.
Kode8.6
menyajikan suatu program yang mendemonstrasikan bagaimana mengurutkan
elemen-elemen di dalam set tree menggunakan antarmuka Comparator. Contoh ini menciptakan suatu set tree yang memuat
objek-objek geometri pada baris 6-11. Objek-objek geometri tersebut diurutkan
menggunakan metode compare di dalam
antarmuka Comparator.
Kode8.6 UjiTreeSetDenganKomparator.java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
import java.util.*;
public class UjiTreeSetDenganKomparator {
public static void main(String[]
args) {
// Menciptakan set tree untuk objek-objek geometri menggunakan
komparator
Set<ObjekGeometri> set =
new TreeSet<ObjekGeometri>(new KomparatorObjekGeometri());
set.add(new PersegiPanjang(4, 5));
set.add(new Lingkaran(40));
set.add(new Lingkaran(40));
set.add(new PersegiPanjang(4, 1));
// Menampilkan objek-objek geometri di
dalam set tree
System.out.println("Suatu set
terurut yang memuat objek-objek geometri");
for (ObjekGeometri elemen: set)
System.out.println("luas =
" + elemen.dapatLuas());
}
}
|
Keluaran
Suatu set terurut yang
memuat objek-objek geometri
luas = 4.0
luas = 20.0
luas = 5026.548245743669
Kelas Lingkaran dan PersegiPanjang didefinisikan pada Bab1.2, keduanya merupakan
subkelas dari ObjekGeometri.
8.6
List
Suatu set
menyimpan elemen-elemen nonduplikat. Untuk mengijinkan elemen-elemen duplikat
disimpan di dalam suatu koleksi, Anda membutuhkan suatu list. Suatu list tidak
hanya dapat menyimpan elemen-elemen duplikat tetapi juga mengijinkan pengguna
untuk menentukan dimana elemen-elemen disimpan. Pengguna dapat mengakses elemen
melalui suatu indeks. Antarmuka List
mewarisi Collection untuk
mendefinisikan suatu koleksi terurut dengan elemen-elemen duplikat diijinkan
untuk disimpan di dalamnya. Antarmuka List menambahkan operasi-operasi
berorientasi-posisi, begitu pula suatu iterator list yang baru yang memampukan
pengguna untuk menjelajah list secara dua-arah. Metode-metode baru di dalam
antarmuka List ditampilkan pada
Gambar 8.4.
Gambar
8.4 Antarmuka List menyimpan elemen-elemen secara berurutan dan mengijinkan
duplikasi
Metode add(index, element) digunakan untuk
menyisipkan suatu elemen pada indeks tertentu,dan metode addAll(index, collection) untuk menyisipkan suatu koleksi pada
indeks tertentu. Metode remove(index)
digunakan untuk menghapus suatu elemen pada indeks tertentu dari list. Suatu
elemen baru dapat ditetapkan pada indeks tertentu menggunakan metode set(index, element).
Metode indexOf(element) digunakan untuk
memperoleh indeks dari kemunculan pertama atas elemen tertentu di dalam list,
dan Metode lastIndexOf(element)
digunakan untuk memperoleh indeks dari kemunculan terakhir atas elemen tertentu
di dalam list. Suatu sublist didapatkan menggunakan metode subList(fromIndex, toIndex).
Metode listIterator() atau listIterator(startIndex) mengembalikan
suatu instans dari ListIterator.
Antarmuka ListIterator mewarisi
antarmuka Iterator untuk menambah
kemampuan penyebaran dua-arah pada list. Metode-metode di dalam ListIterator ditampilkan pada Gambar
8.5.
Gambar
8.5 ListIterator memampukan Anda untuk menjelajah elemen secara
dua-arah (bidireksional)
Metode add(element) menyisipkan elemen
tertentu ke dalam list. Elemen tersebut disisipkan tepat sebelum elemen
berikutnya yang dikembalikan oleh metode next()
yang didefinisikan di dalam antarmuka Iterator,
jika ada, dan setelah elemen yang dikembalikan oleh metode previous(). Jika list tidak memiliki elemen, elemen baru menjadi
satu-satunya elemen dalam list. Metode set(element)
dapat digunakan untuk mengganti elemen terakhir yang dikembalikan oleh metode next() atau oleh metode previous() dengan elemen tertentu.
Metode hasNext() yang didefinisikan di dalam
antarmuka Iterator digunakan untuk memeriksa apakah iterator memiliki
elemen-elemen lagi yang akan disebarkan pada arah maju, dan metode hasPrevious() yang didefinisikan di
dalam antarmuka Iterator digunakan
untuk memeriksa apakah iterator memiliki elemen-elemen lagi yang akan
disebarkan pada arah mundur.
Metode next() yang didefinisikan di dalam
antarmuka Iterator mengembalikan
elemen berikutnya di dalam iterator, dan metode previous() yang didefinisikan di dalam antarmuka Iterator mengembalikan elemen
sebelumnya di dalam iterator. Metode nextIndex()
mengembalikan indeks dari elemen berikutnya di dalam iterator dan metode previousIndex() mengembalikan indeks
dari elemen berikutnya di dalam iterator.
Kelas AbstractList menyediakan implementasi
parsial untuk antarmuka List. Kelas AbstractSequentialList mewarisi AbstractList untuk menyediakan dukungan
bagi list berantai.
8.6.1
Kelas ArrayList dan LinkedList
Kelas ArrayList dan kelas LinkedList merupakan dua implementasi
konkrit dari antarmuka List. ArrayList menyimpan elemen-elemen di
dalam suatu array. Array tersebut diciptakan secara dinamis. Jika kapasitas
array dilampaui, maka suatu array yang lebih besar diciptakan dan semua elemen
dari array sekarang disalin kepada array yang baru tersebut. LinkedList menyimpan elemen-elemen di
dalam suatu senarai atau daftar atau list berantai. Mana dari dua kelas ini
yang akan Anda pakai tergantung dari kebutuhan spesifik Anda. Jika Anda perlu
untuk mendukung akses acak melalui suatu indeks tanpa penyisipan atau
penghapusan elemen-elemen kecuali pada ujung list, ArrayList menawarkan koleksi yang paling efisien. Namun jika
aplikasi Anda memerlukan penyisipan atau penghapusan elemen-elemen di mana saja
di dalam list, maka Anda harus memilih LinkedList.
Suatu list bisa bertambah atau berkurang secara dinamis. Begitu diciptakan, array
berukuran tetap. Jika aplikasi Anda tidak memerlukan penyisipan atau
penghapusan elemen-elemen, maka array merupakan struktur data paling efisien untuk tujuan
tersebut.
ArrayList
merupakan implementasi array atas antarmuka List, dengan kapasitas yang bisa diperbesar atau diperkecil. Kelas
ini juga menyediakan beberapa metode untuk memanipulasi ukuran array yang
digunakan secara internal untuk menyimpan list, seperti tertampil pada Gambar
8.6. Setiap instans dari ArrayList
memiliki suatu kapasitas, yang berupa ukuran array yang digunakan untuk
menyimpan elemen-elemen di dalam list. Begitu elemen-elemen ditambahkan pada
suatu ArrayList, kapasitasnya
bertambah secara otomatis. Suatu ArrayList
tidak secara otomatis menyusut. Anda bisa menggunakan metode trimToSize() untuk mereduksi kapasitas
array menjadi seukuran dengan list. Suatu ArrayList
dapat diciptakan menggunakan konstruktor tanpa-argumennya, ArrayList-(Collection), atau ArrayList(initialCapacity).
Gambar
8.6 ArrayList mengimplementasikan List
menggunakan array
LinkedList
merupakan implementasi list berantai dari antarmuka List. Kelas ini menyediakan beberapa metode untuk menarik,
menyisipkan, dan menghapus elemen-elemen dari kedua ujung list, seperti
tertampil pada Gambar 8.7. Suatu LinkedList
dapat diciptakan menggunakan konstruktor tanpa-argumennya atau LinkedList(Collection).
Gambar
8.7 LinkedList menyediakan beberapa metode untuk menambahkan dan
menyisipkan elemen-elemen pada kedua ujung list
Kode8.7
menyajikan suatu program yang menciptakan suatu array yang diisi dengan
angka-angka dan menyisipkan elemen-elemen baru pada lokasi-lokasi tertentu di
dalam list. Contoh ini juga menciptakan suatu list berantai dari list array
tersebut dan menyisipkan dan menghapus elemen-elemen dari list. Terakhir,
contoh ini juga menjelajah list secara maju maupun mundur.
Kode8.7 UjiArrayDanLinkedList.java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
import java.util.*;
public class UjiArrayDanLinkedList {
public static void main(String[]
args) {
List<Integer> arrayList = new ArrayList<Integer>();
arrayList.add(1); // 1 diautobox menjadi
new Integer(1)
arrayList.add(2);
arrayList.add(3);
arrayList.add(1);
arrayList.add(4);
arrayList.add(0, 10);
arrayList.add(3, 30);
System.out.println("Suatu list
integer di dalam list array:");
System.out.println(arrayList);
LinkedList<Object> linkedList = new LinkedList<Object>(arrayList);
linkedList.add(1, "merah");
linkedList.removeLast();
linkedList.addFirst("hijau");
System.out.println("Menampilkan
list berantai secara maju:");
ListIterator<Object> listIterator = linkedList.listIterator();
while (listIterator.hasNext()) {
System.out.print(listIterator.next() +
" ");
}
System.out.println();
System.out.println("Menampilkan
list berantai secara mundur:");
listIterator = linkedList.listIterator(linkedList.size());
while (listIterator.hasPrevious())
{
System.out.print(listIterator.previous()
+ " ");
}
}
}
|
Keluaran
Suatu list integer di dalam
list array:
[10, 1, 2, 30, 3, 1, 4]
Menampilkan list berantai
secara maju:
hijau 10 merah 1 2 30 3 1
Menampilkan list berantai
secara mundur:
1 3 30 2 1 merah 10 hijau
Suatu
list dapat memuat elemen-elemen yang identik. Integer 1 disimpan dua kali di
dalam list (baris 6, 9). ArrayList
dan LinkedList dioperasikan dengan
cara sama. Perbedaan penting dari keduanya ada pada implementasi internal, yang
mempengaruhi kinerjanya. ArrayList
sangat efisien untuk menarik atau mendapatkan elemen-elemen dan untuk
menyisipkan dan menghapus elemen-elemen pada kedua ujung list. LinkedList sangat efisien untuk
menyisipkan dan menghapus elemen-elemen di mana saja di dalam list.
8.6.2
Metode Statik Untuk List Dan Koleksi
Anda bisa
menggunakan TreeSet untuk menyimpan
elemen-elemen terurut di dalam suatu set. Tetapi dalam list, tidak ada
pengurutan. Akan tetapi, JCF menyediakan beberapa metode statik di dalam kelas Collection yang bisa dipakai untuk
mengurutkan suatu list. Kelas Collection
juga memuat metode binarySearch, reverse, shuffle, copy, dan fill untuk
memanipulasi list, dan metode max, min, disjoint, dan frequency
untuk memanipulasi koleksi, seperti tertampil pada Gambar 8.8.
Anda bisa
mengurutkan elemen-elemen komparabel di dalam list dengan urutan alamiah
melalui metode compareTo di dalam
antarmuka Comparable. Anda juga bisa
menspesifikasi suatu komparator untuk mengurutkan elemen. Sebagai contoh, kode
berikut mngurutkan string di dalam suatu list:
List<String> list =
Arrays.asList("merah",
"hijau", "biru");
Collections.sort(list);
System.out.println(list);
Keluarannya
adalah [biru, hijau, merah].
Kode
terdahulu mengurutkan suatu list dengan urutan menaik. Untuk mengurutkannya
secara menurun, Anda bisa menggunakan metode Collections.reverseOrder() untuk mengembalikan suatu objek Comparator yang mengurutkan elemen
secara menurun. Sebagai contoh, kode berikut mengurutkan string di dalam list
dengan urutan menurun:
List<String> list =
Arrays.asList("kuning",
"merah", "hijau",
"biru");
Collections.sort(list,
Collections.reverseOrder());
System.out.println(list);
Keluarannya
adalah [merah, kuning, hijau, biru].
Gambar
8.8 Kelas Collections memuat beberapa metode statik untuk memanipulasi
koleksi dan list
Anda bisa
menggunakan metode binarySearch
untuk mencari kunci di dalam list. List terlebih dahulu diurutkan secara
menaik. Jika kunci tidak berada dalam list, maka metode mengembalikan -( titik penyisipan + 1). Ingat bahwa titik
penyisipan adalah dimana item akan ditempatkan bila item tersebut berada di
dalam list. Sebagai contoh, kode berikut mencari beberapa kunci di dalam list
integer dan list string.
List<Integer> list1 =
Arrays.asList(2,
4, 7,
10, 11,
45, 50,
59, 60,
66);
System.out.println("(1)
Indeks: " + Collections.binarySearch(list1, 7));
System.out.println("(2)
Indeks: " + Collections.binarySearch(list1, 9));
List<String> list2 =
Arrays.asList("biru",
"hijau", "merah");
System.out.println("(3)
Indeks: " +
Collections.binarySearch(list2, "merah"));
System.out.println("(4)
Indeks: " +
Collections.binarySearch(list2,
"cyan"));
Keluarannya
adalah
(1) Indeks: 2
(2) Indeks: -4
(3) Indeks: 2
(4) Indeks: -2
Anda bisa
menggunakan metode reverse untuk
membalikkan elemen-elemen di dalam list. Sebagai contoh, kode berikut
menampilkan [biru, hijau, merah, kuning].
List<String> list =
Arrays.asList("kuning",
"merah", "hijau",
"biru");
System.out.println(list);
Collections.reverse(list);
Anda bisa
memakai metode shuffle(List) untuk
menata secara acak elemen-elemen di dalam suatu list. Sebagai contoh, kode
berikut mengacak elemen-elemen di dalam list.
List<String> list =
Arrays.asList("kuning",
"merah", "hijau",
"biru");
Collections.shuffle(list);
System.out.println(list);
Anda juga
bisa memakai metode shuffle(List,
Random) untuk mengacak elemen-elemen di dalam suatu list dengan objek Random tertentu. Pemakaian suatu objek Random tertentu berguna dalam
membangkitkan suatu list dengan runtun elemen identik untuk list awal yang
sama. Sebagai contoh, kode berikut mengacak elemen-elemen di dalam list.
List<String>
list1 = Arrays.asList("kuning", "merah", "hijau", "biru");
List<String>
list2 = Arrays.asList("kuning", "merah", "hijau", "biru");
Collections.shuffle(list1,
new Random(20));
Collections.shuffle(list2,
new Random(20));
System.out.println(list1);
System.out.println(list2);
Anda akan
melihat bahwa list1 dan list2 memiliki runtun elemen yang sama
sebelum dan sesudah pengacakan.
Anda
sapat memakai metode copy(det, src)
untuk menyalin semua elemen dari list sumber ke list tujuan dengan indeks yang
sama. List tujuan harus sama panjang dengan list sumber. Jika list tujuan lebih
panjang dari list sumber, maka elemen-elemen sisa di dalam list tujuan tidak
akan terpengaruhi. Sebagai contoh, kode berikut menyalin dari list1 ke list2.
List<String> list1 =
Arrays.asList("kuning", "merah", "hijau", "biru");
List<String> list2 =
Arrays.asList("putih",
"hitam");
Collections.copy(list1, list2);
System.out.println(list1);
Keluaran
untuk list1 adalah [putih, hitam,hijau, biru]. Metode copy
melakukan penyalinan dangkal. Hanya referensi dari elemen-elemen list sumber
yang disalin.
Anda bisa
memakai metode nCopies(int n, Object o)
untuk menciptakan suatu list immutabel yang memiliki n salinan dari objek tertentu. Sebagai contoh, kode berikut
menciptakan suatu list dengan lima objek Calendar.
List<GregorianCalendar> list1 = Collections.nCopies
(5, new GregorianCalendar(2005, 0, 1));
List yang
diciptakan dari metode nCopies
bersifat immutabel, jadi Anda tidak bisa menambah, menghapus, atau memperbarui
elemen di dalam list. Semua elemen memiliki referensi sama.
Anda bisa
menggunakan metode fill(List list,
Object o) untuk mengganti semua elemen di dalam list dengan elemen
tertentu. Sebagai contoh, kode berikut menampilkan [hitam, hitam, hitam].
List<String>
list = Arrays.asList("merah", "hijau", "biru");
Collections.fill(list,
"hitam");
System.out.println(list);
Anda bisa
menggunakan metode max dan min untuk menemukan elemen maksimum dan
minimum di dalam suatu koleksi. Elemen-elemen harus komparabel menggunakan
antarmuka Comparable atau antarmuka Comparator. Sebagai contoh, kode
berikut menampilkan string terbesar dan string terkecil di dalam suatu koleksi.
Collection<String> collection
= Arrays.asList("merah",
"hijau", "biru");
System.out.println(Collections.max(collection));
System.out.println(Collections.min(collection));
Metode disjoint(collection1, collection2)
mengembalikan true bila dua koleksi
tidak memiliki elemen yang sama. Sebagai contoh, di dalam kode berikut, disjoint(collection1, collection2)
mengembalikan false, tetapi disjoint-(collection1, collection3)
mengembalikan true.
Collection<String> collection1
= Arrays.asList("merah",
"hitam");
Collection<String> collection2
= Arrays.asList("merah",
"biru");
Collection<String> collection3
= Arrays.asList("kuning",
"hijau");
System.out.println(Collections.disjoint(collection1,
collection2));
System.out.println(Collections.disjoint(collection1,
collection3));
Metode frequency(collection, element)
menemukan jumlah kemunculan elemen di dalam koleksi. Sebagai contoh, frequency(koleksi, “merah”)
mengembalikan 2 di dalam kode berikut.
Collection<String> koleksi =
Arrays.asList("merah",
"kuning", "merah");
System.out.println(Collections.frequency(koleksi,
"merah"));
8.7 Kinerja Set dan List
Sekarang
akan dilakukan eksperimen untuk menguji kinerja set dan list. Kode8.8
menyajikan suatu program yang menunjukkan waktu eksekusi dalam menambah dan
menghapus elemen-elemen di dalam suatu set hash, set hash berantai, set tree,
list array, dan list berantai.
Kode8.8 UjiKinerjaSetList.java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
import java.util.*;
public class UjiKinerjaSetList {
public static void main(String[]
args) {
// Menciptakan suatu set hash, dan menguji
kinerjanya
Collection<Integer> set1 = new HashSet<Integer>();
System.out.println("Waktu untuk
set hash adalah " +
dapatWaktuUji(set1, 500000) + " milidetik");
// Menciptakan suatu set hash berantai,
dan menguji kinerjanya
Collection<Integer> set2 = new
LinkedHashSet<Integer>();
System.out.println("Waktu untuk
set hash berantai adalah " +
dapatWaktuUji(set2, 500000) + " milidetik");
// Menciptakan suatu set tree, dan menguji
kinerjanya
Collection<Integer> set3 = new TreeSet<Integer>();
System.out.println("Waktu untuk
set tree adalah " +
dapatWaktuUji(set3, 500000) + " milidetik");
// Menciptakan suatu list array, dan
menguji kinerjanya
Collection<Integer> list1 = new
ArrayList<Integer>();
System.out.println("Waktu untuk
list array adalah " +
dapatWaktuUji(list1, 60000) + " milidetik");
// Menciptakan suatu list berantai, dan
menguji kinerjanya
Collection<Integer> list2 = new
LinkedList<Integer>();
System.out.println("Waktu untuk
list berantai adalah " +
dapatWaktuUji(list2, 60000) + " milidetik");
}
public static long dapatWaktuUji(Collection<Integer> c, int ukuran) {
long waktuMulai =
System.currentTimeMillis();
// Menambah angka 0, 1, 2, ..., ukuran - 1
ke dalam list array
List<Integer> list = new
ArrayList<Integer>();
for (int i = 0; i <
ukuran; i++)
list.add(i);
Collections.shuffle(list); // Mengacak list array
// Menambah elemen ke dalam kontainer
for (int elemen: list)
c.add(elemen);
Collections.shuffle(list); // Mengacak list array
// Menghapus elemen ke dalam kontainer
for (int elemen: list)
c.remove(elemen);
long waktuAkhir =
System.currentTimeMillis();
return waktuAkhir - waktuMulai; // Mengembalikan waktu eksekusi
}
}
|
Keluaran
Waktu untuk set hash adalah
2355 milidetik
Waktu untuk set hash
berantai adalah 2153 milidetik
Waktu untuk set tree adalah
3604 milidetik
Waktu untuk list array
adalah 11497 milidetik
Waktu untuk list berantai
adalah 16286 milidetik
Metode dapatWaktuUji menciptakan suatu list
integer yang berbeda dari 0 sampai ukuran-1
(baris 35-37), mengacak list (baris 39), menambah elemen-elemen dari list ke
kontainer c (baris 42-43), mengacak
list kembali (baris 45), menghapus elemen-elemen dari kontainer (baris 48-49),
dan terakhir mengembalikan waktu eksekusi (baris 52).
Program
menciptakan suatu set hash (baris 6), suatu set hash berantai (baris 11), suatu
set tree (baris 16), suatu list array (baris 21), dan suatu list berantai (baris
26). Program memperoleh waktu eksekusi untuk menambah dan menghapus 500000
elemen di dalam ketiga set dan menambah dan menghapus 60000 elemen di dalam
kedua list.
Seperti
yang Anda perhatikan, set lebih efisien dari list. Jika set cukup dan cocok untuk
aplikasi Anda, gunakan set. Bila Anda tidak memerlukan pengurutan di dalam
aplikasi, gunakan set hash.
8.8 Kelas Vector dan Stack
JCF
dikenalkan dengan JAVA 2. Beberapa struktur data yang didukung belakangan
adalah kelas Vector dan kelas Stack. Kedua kelas ini didesain-ulang
agar sesuai dengan JCF.
Vector
sama dengan ArrayList, kecuali bahwa
kelas Vector memuat beberapa metode
tersinkronisasi untuk mengakses dan memodifikasi vektor. Metode tersinkronisasi
tersebut dapat mencegah kerusakan atau korupsi data ketika suatu vektor diakses
dan dimodifikasi oleh dua atau lebih thread secara bersamaan. Pada banyak
aplikasi, hal ini tidak menjadi masalah dan tidak perlu. Penggunaan ArrayList lebih efisien daripada
penggunaan Vector.
Kelas Vector mengimplementasikan antarmuka List. Kelas ini juga mempunyai
metode-metode yang dimuat di dalam kelas Vector
awal yang didefinisikan sebelum kehadiran JAVA 2, seperti tertampil pada Gambar
8.9.
Gambar
8.9 Kelas Vector dalam JAVA 2 mengimplementasikan List dan juga memuat semua metode di dalam kelas Vector awal
Kebanyakan
metode-metode tambahan di dalam kelas Vector
yang dicantumkan di dalam diagram UML pada Gambar 8.9 sama dengan metode-metode
di dalam antarmuka List. Sebagai
contoh, addElement(Object element)
sama dengan metode add(Object element),
kecuali bahwa metode addElement
telah disinkronisasi. Gunakan ArrayList
jika Anda tidak membutuhkan sinkronisasi, karena ArrayList bekerja lebih cepat dari Vector.
Dalam
JCF, Stack diimplementasikan sebagai
suatu ekstensi dari Vector, seperti
diilustrasikan pada Gambar 8.10.
Gambar
8.10 Kelas Stack mewarisi Vector
untuk menyediakan struktur data dengan gaya FIFO (first-in, first-out)
Kelas Stack dikenalkan sebelum JAVA 2.
Metode-metode yang ditampilkan pada Gambar 8.10 digunakan sebelum JAVA 2.
Metode empty() sama dengan isEmpty(). Metode peek() menengok atau mengintip elemen teratas tumpukan tanpa
menghapusnya. Metode pop() menghapus
atau membuang elemen teratas dari tumpukan dan menjadikannya nilai balik.
Metode push(Object element)
memeriksa apakah elemen tertentu berada dalam tumpukan atau tidak.
8.9 Antrian dan Antrian Prioritas
Antrian
merupakan struktur data dengan gaya FIFO. Elemen disambungkan ke ujung antrian
dan dihapus dari awal antrian. Di dalam antrian prioritas, elemen-elemen
ditugasi prioritas. Ketika mengakses elemen, elemen dengan prioritas tertinggi
dihapus terlebih dahulu. Bagian ini akan mengenalkan antrian dan antrian
prioritas dalam JAVA API.
Antarmuka
Queue mewarisi java.lang.Collection dengan operasi-operasi tambahan untuk
menyisipkan, mengekstraksi, dan menginspeksi, seperti tertampil pada Gambar
8.11.
Metode offer digunakan untuk menambah suatu
elemen ke antrian. Metode ini sama dengan metode add dalam antarmuka Collection,
tetapi metode offer lebih sering
digunakan untuk antrian. Metode poll
dan remove sama, kecuali bahwa poll() mengembalikan null jika antrian kosong, sedangkan remove() akan melempar ekspesi pada
situasi itu. Metode peek dan element sama, kecuali bahwa peek() mengembalikan null jika antrian kosong, sedangkan element() akan melempar ekspesi pada
situasi itu.
Gambar
8.11 Antarmuka Queue mewarisi Collection
untuk menyediakan operasi-operasi tambahan seperti penyisipan, ekstraksi, dan
inspeksi.
8.9.1 Deque dan LinkedList
Kelas LinkedList mengimplementasikan
antarmuka Deque, yang mewarisi
antarmuka Queue, seperti tertampil
pada Gambar 8.12. Sehingga Anda bisa menggunakan LinkedList untuk menciptakan suatu antrian.
Gambar
8.12 LinkedList mengimplementasikan List
dan Deque
Deque mendukung
penyisipan dan penghapusan elemen pada kedua ujung antrian. Nama deque merupakan singkatan dari “double-ended queue” dan diucapkan dengan
“deck”. Antarmuka Deque mewarisi Queue
dengan beberapa metode tambahan untuk menyisipkan dan menghilangkan kedua ujung
antrian. Metode addFirst(e), removeFirst(), addLast(e), removeLast(),
getFirst(), dan getLast() didefinisikan di dalam antarmuka Deque.
Kode8.9
menunjukkan suatu contoh penggunaan antrian untuk menyimpan string. Baris 4
menciptakan suatu antrian menggunakan LinkedList.
Empat string ditambahkan ke dalam antrian pada baris 5-8. Metode size() yang didefinisikan di dalam
antarmuka Collection mengembalikan
jumlah elemen di dalam antrian (baris 10). Metode remove() mengambil dan menghapus elemen di kepala antrian (baris
11).
Kode8.9 UjiAntrian.java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
public class UjiAntrian {
public static void main(String[]
args) {
java.util.Queue<String> antrian =
new java.util.LinkedList<String>();
antrian.offer("Aurora");
antrian.offer("Adam");
antrian.offer("Lizzy");
antrian.offer("Nicholaus");
while(antrian.size() > 0)
System.out.print(antrian.remove() +
" ");
}
}
|
Keluaran
Aurora Adam Lizzy Nicholaus
Kelas PriorityQueue mengimplementasikan suatu
antrian prioritas, seperti tertampil pada Gambar 8.13. Secara default, antrian
prioritas menata elemen-elemennya sesuai dengan urutan alamiah menggunakan Comparable. Elemen dengan nilai
terkecil ditugasi prioritas tertinggi, jadi dihapus dari antrian pertama kali.
Jika terdapat beberapa elemen dengan prioritas tertinggi yang sama, maka ikatan
berubah tak-beraturan. Anda juga bisa menspesifikasi suatu pengurutan
menggunakan Comparator di dalam konstruktor PriorityQueue-(initialCapacity, comparator).
Kode8.10
menunjukkan suatu contoh penggunaan antrian prioritas untuk menyimpan beberapa
string. Baris 5 menciptakan suatu antrian prioritas untuk menyimpan beberapa
string menggunakan konstruktor tanpa-argumen. Antrian prioritas ini menata
string sesuai urutan alamiah, sehingga string dihapus dari antrian dengan urutan
menaik. Baris 16-17 menciptakan suatu antrian prioritas menggunakan komparator
yang diperoleh dari Collections.reverse-
Order(), yang mengurutkan string secara terbalik, sehingga string dihapus
dari antrian secara menurun.
Gambar
8.13 Kelas PriorityQueue mengimplementasikan suatu antrian prioritas
Kode8.10 DemoAntrianPrioritas.java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
import java.util.*;
public class DemoAntrianPrioritas {
public static void main(String[]
args) {
PriorityQueue<String> antrian1 = new
PriorityQueue<String>();
antrian1.offer("Gaby");
antrian1.offer("Artha");
antrian1.offer("Glory");
antrian1.offer("Philip");
System.out.println("Antrian
prioritas menggunakan Comparable:");
while (antrian1.size() > 0) {
System.out.print(antrian1.remove() +
" ");
}
PriorityQueue<String> antrian2 = new
PriorityQueue<String>(
4, Collections.reverseOrder());
antrian2.offer("Gaby");
antrian2.offer("Artha");
antrian2.offer("Glory ");
antrian2.offer("Philip");
System.out.println("\nAntrian
prioritas menggunakan komparator:");
while (antrian2.size() > 0) {
System.out.print(antrian2.remove() +
" ");
}
}
}
|
Keluaran
Antrian prioritas
menggunakan Comparable:
Artha Gaby Glory Philip
Antrian prioritas
menggunakan komparator:
Philip Glory Gaby Artha
8.10 Peta
Dimisalkan
program Anda menyimpan jutaan mahasiswa dan sangat sering melakukan pencarian
menggunakan NIK (nomor induk kependudukan). Struktur data yang efisien untuk
melakukan ini adalah peta atau map. Peta merupakan suatu kontainer yang
menyimpan elemen bersama dengan kunci. Kunci sama dengan indeks. Di dalam List, indeks adalah integer. Di dalam Map, kunci bisa berupa sembarang objek.
Suatu peta tidak bisa memuat kunci duplikat. Setiap kunci memetakan satu nilai.
Suatu kunci yang berpasangan dengan nilai membentuk suatu entri, yang disimpan
di dalam peta, seperti tertampil pada Gambar 8.14.
Gambar
8.14 Entri memuat sepasang
kunci/nilai, disimpan di dalam suatu peta
Terdapat
tiga jenis peta: HashMap, LinkedHashMap, dan TreeMap. Beberapa fitur bersama dari ketiga peta ini didefinisikan
di dalam antarmuka Map. Relasi
ketiganya ditampilkan pada Gambar 8.15.
Antarmuka
Map menyediakan beberapa metode
untuk queri, pembaruan, dan untuk mendapatkan koleksi nilai dan sehimpunan
kunci, seperti tertampil pada Gambar 8.16.
Gambar
8.15 Suatu peta menyimpan pasangan
kunci/nilai
Gambar
8.16 Antarmuka Map memetakan kunci kepada nilai
Beberapa
metode pembaru yang didefinisikan adalah termasuk clear, put, putAll, dan remove. Metode clear()
menghapus semua entri di dalam peta. Metode put(K key, V value) menghubungkan suatu nilai dengan suatu kunci di
dalam peta. Jika peta sebelumnya memuat suatu pemetaan untuk kunci ini, maka
nilai lama yang berkaitan dengan kunci tersebut yang dikembalikan atau
dijadikan nilai balik. Metode putAll(Map
m) menambah peta tertentu kepada peta ini. Metode remove(Object key) menghapus elemen peta untuk kunci tertentu dalam
peta.
Beberapa
metode queri yang didefinisikan termasuk containsKey,
containsValue, isEmpty, dan size.
Metode containsKey(Object key)
memeriksa apakah peta memiliki pemetaan untuk kunci tertentu. Metode containsValue(Object value) memeriksa
apakah peta memiliki pemetaan untuk nilai tertentu. Metode isEmpty() memeriksa apakah peta memiliki pemetaan atau tidak.
Metode size() mengembalikan jumlah
pemetaan di dalam peta.
Anda
bisa memperoleh suatu set kunci di dalam peta menggunakan metode keySet(), dan mendapatkan sekoleksi
nilai di dalam peta menggunakan metode values().
Metode entrySet() mengembalikan
suatu set objek yang mengimplementasikan antarmuka Map.Entry<K, V>, dimana Entry
merupakan antarmuka inner dari antarmuka Map,
seperti tertampil pada Gambar 8.17. Setiap objek di dalam set merupakan
sepasang kunci/nilai tertentu di dalam peta.
Gambar
8.17 Antarmuka Map.Entry beroperasi pada suatu entri di dalam peta
Kelas AbstractMap merupakan suatu kelas yang
mengimplementasikan semua metode di dalam antarmuka Map kecuali metode entrySet().
Gambar
8.18 JCF menyediakan tiga kelas peta
konkrit
Antarmuka
SortedMap mewarisi antarmuka Map untuk mempertahankan pemetaan
dengan urutan menaik dengan beberapa metode tambahan firstKey() dan lastKey()
untuk mengembalikan kunci terendah dan kunci tertinggi, metode headMap(toKey) untuk mengembalikan
bagian atau seporsi peta yang memiliki kunci lebih rendah dari toKey, metode tailMap(fromKey) untuk mengembalikan bagian atau seporsi peta yang
memiliki kunci lebih tinggi dari atau sama dengan fromKey.
Kelas HashMap, LinkedHashMap, dan TreeMap
merupakan tiga implementasi konkrit dari antarmuka Map, seperti tertampil pada Gambar 8.18.
Kelas HashMap efisien untuk melokasi suatu
nilai, menyisipkan suatu pemetaan, dan menghapus suatu pemetaan.
LinkedHashMap
mewarisi HashMap dengan suatu
implementasi link-berantai yang mendukung suatu pengurutan entri di dalam peta.
Entri di dalam suatu HashMap tidak
terurut, tetapi entri di dalam suatu LinkedHashMap
dapat diambil atau ditarik secara berurutan sesuai saat disisipkan ke dalam
peta (dikenal dengan urutan penyisipan) atau sesuai urutan terakhir kali
diakses (dikenal dengan urutan akses). Konstruktor tanpa-argumen menciptakan
suatu LinkedHashMap dengan urutan
penyisipan. Untuk menciptakan suatu LinkedHashMap
dengan urutan akses, digunakan LinkedHashMap(initialCapacity,
loadFactor, true).
Kelas TreeMap efisien untuk menjelajah kunci
dengan tatanan terurut. Kunci dapat diurutkan menggunakan antarmuka Comparable atau antarmuka Comparator. Jika Anda menciptakan suatu
TreeMap menggunakan konstruktor
tanpa-argumennya, metode compareTo
di dalam antarmuka Comparable
digunakan untuk membandingkan elemen-elemen di dalam peta, bila diasumsikan
bahwa kelas elemen meng-implementasikan antarmuka Comparable. Untuk menggunakan suatu komparator, Anda harus
menggunakan konstruktor TreeMap(Comparator
comparator) untuk menciptakan suatu peta terurut yang menggunakan metode compare di dalam komparator untuk
mengurutkan elemen di dalam peta berdasarkan kunci yang ada.
SortedMap
merupakan subantarmuka dari Map,
yang menjamin bahwa entri di dalam peta diurutkan. Subantarmuka ini juga
menyediakan metode firstKey() dan lastKey() untuk mengembalikan kunci
pertama dan kunci terakhir di dalam peta, dan metode headMap(toKey) dan tailMap(fromKey)
untuk mengembalikan seporsi atau bagian peta yang memiliki kunci lebih rendah
dari toKey dan lebih tinggi dari
atau sama dengan fromKey.
NavigableMap
mewarisi SortedMap untuk menyediakan
beberapa metode navigasi lowerKey(key),
floorKey(key), ceilingKey(key), dan higherKey(key)
yang mengembalikan kunci kurang dari, kurang dari atau sama dengan, lebih dari
atau sama dengan, dan lebih dari kunci yang diberikan (key) dan mengembalikan null bila tidak terdapat kunci yang dicari.
Metode pollFirstEntry() dan pollLastEntry() menghapus dan mengembalikan
entri pertama dan entri terakhir di dalam peta tree.
Kode8.11
menyajikan suatu contoh untuk menciptakan suatu peta hash, peta hash berantai,
dan peta tree yang memetakan mahasiswa pada umur. Program pertama-tama
menciptakan suatu peta hash dengan nama mahasiswa sebagai kunci dan umur
sebagai nilai. Program kemudian menciptakan suatu peta tree dari peta hash dan
menampilkan pemetaan dengan urutan kunci secara menaik. Terakhir, program
menciptakan suatu peta hash berantai, menambah entri ke dalam peta, dan
menampilkan entri-entri di dalam peta.
Kode8.11 UjiPeta.java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
import java.util.*;
public class UjiPeta {
public static void main(String[]
args) {
// Menciptakan suatu HashMap
Map<String, Integer> hashMap = new HashMap<String,
Integer>();
hashMap.put("Sintong",
30);
hashMap.put("Munir", 31);
hashMap.put("Agung", 29);
hashMap.put("Nyoman",
29);
System.out.println("Menampilkan
entri di dalam HashMap");
System.out.println(hashMap +
"\n");
// Menciptakan suatu TreeMap dari HashMap
Map<String, Integer> treeMap=
new TreeMap<String, Integer>(hashMap);
System.out.println("Menampilkan
entri dengan urutan kunci menaik");
System.out.println(treeMap);
// Menciptakan suatu LinkedHashMap
Map<String, Integer> linkedHashMap =
new LinkedHashMap<String, Integer>(16, 0.75f, true);
linkedHashMap.put("Sintong",
30);
linkedHashMap.put("Munir",
31);
linkedHashMap.put("Agung",
29);
linkedHashMap.put("Nyoman",
29);
// Menampilkan umur untuk Agung
System.out.println("Umur
" + "Agung adalah " +
linkedHashMap.get("Agung").intValue());
System.out.println("\nMenampilkan
entri dalam LinkedHashMap");
System.out.println(linkedHashMap);
}
}
|
Keluaran
Menampilkan entri di dalam
HashMap
{Agung=29, Sintong=30,
Nyoman=29, Munir=31}
Menampilkan entri dengan
urutan kunci menaik
{Agung=29, Munir=31,
Nyoman=29, Sintong=30}
Umur Agung adalah 29
Menampilkan entri dalam
LinkedHashMap
{Sintong=30, Munir=31,
Nyoman=29, Agung=29}
Seperti
tertampil pada keluaran, urutan entri di dalam HashMap adalah acak. Entri di dalam TreeMap memiliki urutan kunci menaik. Entri di dalam LinkedHashMap berurutan sesuai dengan
akses, dari yang telah lama diakses sampai yang baru saja diakses.
Semua kelas
konkrit yang mengimplementasikan antarmuka Map
paling sedikit memiliki dua konstruktor. Satu adalah konstruktor tanpa-argumen
yang menciptakan suatu peta kosong, konstruktor yang lain adalah yang
menciptakan suatu peta dari instans Map.
Jadi, new TreeMap(String,
Integer)<hashMap> (baris 16-17) menciptakan suatu peta tree dari
suatu peta hash.
Anda
bisa menciptakan peta hash berantai dengan urutan akses atau urutan penyisipan.
Suatu peta hash berantai dengan urutan akses diciptakan pada baris 22-23. Entri
yang paling baru diakses ditempatkan di akhir peta. Entri dengan kunci Agung
diakses terakhir diakses pada baris 31, jadi ditempatkan di akhir peta pada
baris 34.
8.10.1 Studi Kasus: Jumlah Kemunculan
Kata
Studi
kasus ini menulis suatu program yang menghitung jumlah kemunculan kata di dalam
suatu teks dan menampilkan kata-kata dan frekuensi kemunculannya dengan urutan
alfabetikal. Program menggunakan suatu TreeMap
untuk menyimpan suatu entri yang memuat suatu kata dan frekuensi kemunculannya.
Untuk setiap kata, diperiksa apakah sudah dijadikan kunci di dalam peta atau
belum. Jika belum, kata tersebut sebagai kunci dan nilai 1 ditambahkan ke dalam
peta untuk membentuk suatu entri. Jika
sudah, nilai untuk kata tersebut (kunci) diinkremen sebanyak 1 di dalam peta.
Diasumsikan bahwa kata di dalam teks adalah case-insensitive, artinya tidak
membedakan antara huruf besar dengan huruf kecil. Kata Orang sama dengan kata orang.
Kode8.12 memberikan solusi terhadap permasalahan ini.
Kode8.12 HitungJumlahKemunculanKata.java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
import java.util.*;
public class HitungJumlahKemunculanKata {
public static void main(String[]
args) {
// Menetapkan teks di dalam suatu string
String teks = "Teknik Elektro
Universitas Gadjah Mada " +
"Teknik Elektro Universitas
Mataram ";
// Menciptakan
TreeMap, menampung kata (kunci) dan
jumlah kemunculan (nilai)
TreeMap<String, Integer> peta = new TreeMap<String,
Integer>();
String[] kata = teks.split(" ");
for (int i = 0; i <
kata.length; i++) {
String kunci = kata[i].toLowerCase();
if (kunci.length() > 0) {
if (peta.get(kunci) == null) {
peta.put(kunci, 1);
}
else {
int nilai =
peta.get(kunci).intValue();
nilai++;
peta.put(kunci, nilai);
}
}
}
// Get all entries into a set
Set<Map.Entry<String, Integer>> entrySet = peta.entrySet();
// Get kunci and nilai from each entry
for (Map.Entry<String, Integer>
entry: entrySet)
System.out.println(entry.getValue() + "\t" + entry.getKey());
}
}
|
Keluaran
2 elektro
1 gadjah
1 mada
1 mataram
2 teknik
2 universitas
No comments:
Post a Comment