Java menyimpan kumpulan value secara native ke dalam Array. Tapi masalahnya adalah Array itu fixed size dan menyimpan value berdasarkan index. Java menyediakan utilitas untuk menyelesaikan permasalahan itu dengan beberapa Collection yang bisa digunakan untuk kasus yang spesifik. Value yang disimpan jadi lebih dinamis ukurannya dan diolah menggunakan berbagai struktur data.
Collection
Collection adalah abstrak dari semua jenis Collection. Collection terdiri dari beberapa sub-interface seperti List, Queue, BlockingQueue, Deque, Set, dan NavigableSet.
List
List adalah Collection yang menyimpan value berdasarkan posisi. Ini adalah Collection yang paling mirip dengan Array. Kita bisa mengubah atau mendapatkan value di posisi index manapun lewat method add() dan get(). Contoh implementasinya yaitu ArrayList, LinkedList, Vector, dan CopyOnWriteArrayList.
ArrayList
ArrayList adalah List yang menyimpan value menggunakan Array. Value tersebut disimpan ke dalam Object Array. Setiap penambahan value, Array tersebut akan diganti ke Array baru yang meng-copy value sebelumnya secara native dengan size tambahan sesuai jumlah value yang ditambah. Makanya ArrayList bisa dinamis. Karena menggunakan Array, method add() dan get() kompleksitasnya O(1) seperti Array. Untuk pencarian menggunakan method contains() kompleksitasnya jadi O(n) karena harus looping untuk mencari value ke-n.
List<Integer> integers = new ArrayList<>();
integers.add(10);
integers.add(3);
integers.add(7);
System.out.println("integers = " + integers); // [10, 3, 7]Vector
Vector adalah List yang menyimpan value menggunakan Array seperti ArrayList tapi Thread-Safe. Jaman sekarang Vector jarang digunakan karena semua method-nya synchronized sehingga lambat.
List<Integer> integers = new Vector<>();
integers.add(10);
integers.add(3);
integers.add(7);
System.out.println("integers = " + integers); // [10, 3, 7]CopyOnWriteArrayList
CopyOnWriteArrayList adalah List yang juga menggunakan Array dan Thread-Safe. Ini lebih baik dari Vector karena hanya synchronized saat ada perubahan. Tiap ada perubahan, Array-nya akan di-copy sebelum diubah. Tiap diakses, referensi Array-nya juga akan dioper ke parameter method lain sehingga saat Array-nya diganti oleh thread lain referensinya aman dari anomaly.
List<Integer> integers = new CopyOnWriteArrayList<>();
integers.add(10);
integers.add(3);
integers.add(7);
System.out.println("integers = " + integers); // [10, 3, 7]LinkedList
LinkedList adalah List yang menyimpan value menggunakan objek Node yang memiliki referensi terhadap value selanjutnya dan sebelumnya. Jadi di dalam LinkedList ada objek Node yang menyimpan value pertama dan terakhir. Lalu Node tersebut juga memiliki referensi terhadap Node kedua, dan Node kedua memiliki referensi Node ketiga, begitu seterusnya. Selain List, LinkedList juga mengimplementasi Deque. Setiap penambahan dan penghapusan value di akhir atau di depan kompleksitasnya O(1). Saat penambahan value di tengah atau saat menggunakan method get() maupun contains() kompleksitasnya jadi O(n) karena kita butuh mengakses dari Node pertama hingga Node ke-n untuk mendapatkan value.
List<Integer> integers = new LinkedList<>();
integers.add(10);
integers.add(3);
integers.add(7);
System.out.println("integers = " + integers); // [10, 3, 7]Queue
Queue adalah Collection yang mengeluarkan value sesuai urutan dari paling depan hingga paling belakang. Pada List kita bisa menentukan posisinya mau ditambahkan di mana atau mau ambil value dari posisi index berapapun. Sedangkan pada Queue kita hanya bisa menambah value melalui method offer() serta mengeluarkan value dari posisi paling depan melalui method poll(). Best practice menggunakan Queue adalah tidak menggunakan looping iterator untuk menampilkan value, tapi menggunakan method poll() karena fungsinya berbeda dengan List. Contoh implementasinya yaitu PriorityQueue, PriorityBlockingQueue, ConcurrentLinkedQueue, dan impelementasi dari BlockingQueue, TransferQueue, dan Deque.
PriorityQueue
PriorityQueue adalah Queue yang menempatkan value yang terkecil atau yang terbesar (defaultnya yang terkecil) di posisi paling depan sehingga setiap value yang keluar dari depan nanti sesuai sorting atau sesuai konfigurasi. Value yang digunakan wajib mengimplementasi Comparable atau di-sorting sesuai konfigurasi pada constructor. Misalkan kita menggunakan method poll() pada Queue Integer, maka value yang keluar adalah value yang terkecil. Setelah keluar, value lainnya diurutkan lagi untuk mencari value terkecil dan ditempatkan di posisi paling depan. Perlu diingat, PriorityQueue tidak mengurutkan semua value seperti Tree, hanya bagian depan saja. Karena value-nya di-sorting, maka pada method offer() dan poll() kompleksitasnya O(log n). PriorityQueue juga memiliki versi thread-safe, yaitu PriorityBlockingQueue.
Queue<Integer> integers = new PriorityQueue<>();
integers.offer(10);
integers.offer(3);
integers.offer(7);
while(!integers.isEmpty()){
System.out.print(integers.poll() + " ");
} // 3 7 10ConcurrentLinkedQueue
ConcurrentLinkedQueue adalah Queue yang mengeluarkan value sesuai urutan masuk berbasis Node tapi secara thread-safe tanpa blocking sama sekali. ConcurrentLinkedQueue juga memiliki versi Deque pada class ConcurrentLinkedDeque.
Queue<Integer> integers = new ConcurrentLinkedQueue<>();
integers.offer(10);
integers.offer(3);
integers.offer(7);
while(!integers.isEmpty()){
System.out.print(integers.poll() + " ");
} // 10 3 7BlockingQueue
BlockingQueue adalah queue dengan kemampuan spesial, yaitu bisa ngeblok saat penginputan atau penghapusan. Di sini ada 2 behavior khusus, yaitu take() yang bisa memblok akses dari thread lain dan mendapatkan & membuang value paling depan, dan put() yang bisa memblok akses dari thread lain dan menambahkan value ke Queue. Contoh implementasinya adalah ArrayBlockingQueue, LinkedBlockingQueue, SynchronousQueue, PriorityBlockingQueue, dan TransferQueue.
ArrayBlockingQueue
ArrayBlockingQueue adalah BlockingQueue yang berbasis Array. Kita wajib menentukan batas kapasitas Queue saat bikin objek. Jika itu melebihi kapasitas, maka akan diblok saat melakukan penginputan hingga thread lain membuang salah satu elemen. Begitu juga saat kapasitasnya masih kosong, maka akan diblok hingga thread lain menambahkan elemen.
BlockingQueue<Integer> integers = new ArrayBlockingQueue<>(1); //set capacity to 1
integers.put(1); //put a number
integers.put(2); //capacity is already full, will wait until availableLinkedBlockingQueue
LinkedBlockingQueue adalah BlockingQueue yang berbasis Node. Kita bisa menentukan batas kapasitas Queue saat bikin objek maupun tidak. Tidak ada validasi kapasitas jika tidak ditentukan kapasitasnya saat bikin objek. Jika kapasitasnya ditentukan saat bikin objek, maka behaviornya sama seperti ArrayBlockingQueue. LinkedBlockingQueue juga memiliki versi Deque pada class LinkedBlockingDeque.
BlockingQueue<Integer> integers = new LinkedBlockingQueue<>(); //no capacity limit
integers.put(1); //put a number
integers.put(2); //no block since no capacity limit
integers.take(); //return 1
BlockingQueue<Integer> ints = new LinkedBlockingQueue<>(1); //set capacity to 1
ints.put(1); //put a number
ints.put(2); //capacity is already full, will wait until availableSynchronousQueue
SynchronousQueue tidak menyimpan kumpulan value, melainkan memblok Queue setelah diinput hingga value tersebut dibuang. Jika ada thread lain yang ingin menginput value, maka akan diblok dan harus nunggu hingga value tersebut dibuang.
ExecutorService executor = Executors.newFixedThreadPool(2);
BlockingQueue<Integer> queue = new SynchronousQueue<>();
Runnable producer = () -> {
try {
queue.put(1); //this will block queue inputted from other threads until consumed
} catch (InterruptedException ex) {
ex.printStackTrace();
}
};
Runnable consumer = () -> {
try {
System.out.println("consumedValue = " + queue.take()); //get & remove value, then unblock
} catch (InterruptedException ex) {
ex.printStackTrace();
}
};
executor.execute(producer);
executor.execute(consumer);
executor.awaitTermination(500, TimeUnit.MILLISECONDS);
executor.shutdown();TransferQueue
Ini Queue yang berbeda dari Queue lainnya karena memiliki behavior transfer() yang bertugas menginput value ke Queue dan memblok thread tersebut hingga valuenya dipakai oleh thread lain mirip SynchronousQueue. Yang membedakan dengan SynchronousQueue adalah valuenya disimpan dalam antrian hingga dibuang dengan kapasitas tidak terbatas dan thread lain masih bisa input secara asynchronous. TransferQueue hanya memiliki implementasi LinkedTransferQueue.
ExecutorService executor = Executors.newFixedThreadPool(4);
TransferQueue<Integer> queue = new LinkedTransferQueue<>();
Runnable producer = () -> {
try {
queue.transfer(1); //this will store the value into queue and block this thread until consumed
} catch (InterruptedException ex) {
ex.printStackTrace();
}
};
Runnable produce2 = () -> {
try {
TimeUnit.SECONDS.sleep(1);
System.out.println("queue = " + queue); //this will show queue saved
queue.transfer(10); //this will store the value into queue and block this thread until consumed
} catch (InterruptedException ex) {
ex.printStackTrace();
}
};
Runnable consumer = () -> {
try {
TimeUnit.SECONDS.sleep(2);
System.out.println("consumedValue = " + queue.take()); //this will get & remove value, then unblock thread that input this value
} catch (InterruptedException ex) {
ex.printStackTrace();
}
};
Runnable consumer2 = () -> {
try {
TimeUnit.SECONDS.sleep(2);
System.out.println("consumedValue = " + queue.take()); //this will get & remove value, then unblock thread that input this value
} catch (InterruptedException ex) {
ex.printStackTrace();
}
};
executor.execute(producer);
executor.execute(consumer);
executor.execute(produce2);
executor.execute(consumer2);
executor.awaitTermination(500, TimeUnit.MILLISECONDS);
executor.shutdown();Deque
Deque (Double Ended Queue) adalah Collection yang mengeluarkan value dari paling depan hingga paling belakang, maupun dari paling belakang hingga paling depan. Deque juga mengimplementasi Queue tapi dengan behavior bisa menambah value dari depan lewat method push() dan mengeluarkan value dari belakang lewat method pollLast(). Contoh implementasinya yaitu ArrayDeque, LinkedList, LinkedBlockingDeque, dan ConcurrentLinkedDeque.
ArrayDeque
ArrayDeque adalah Deque yang menyimpan value berbasis Array. Di sini value yang disimpan ditandai “head” atau “tail” sebagai penanda value paling depan atau paling belakang. ArrayDeque juga memiliki kompleksitas O(1) pada method offer() dan poll().
Deque<Integer> integers = new ArrayDeque<>();
integers.offer(10);
integers.offer(3);
integers.push(7);
while(!integers.isEmpty()){
System.out.print(integers.poll() + " ");
} // 7 10 3
System.out.println();
integers.offer(1);
integers.offer(8);
integers.push(5);
while(!integers.isEmpty()){
System.out.print(integers.pollLast() + " ");
} // 8 1 5Set
Set adalah Collection yang menyimpan value unik. Set umumnya menggunakan fitur key pada Map. Contoh implementasinya yaitu HashSet, LinkedHashSet, EnumSet, ConcurrentHashMapKeySet, CopyOnWriteArraySet, dan implementasi dari NavigableSet.
HashSet
HashSet adalah Collection yang menyimpan value unik dengan cara mengkalkulasi hash code dari value tersebut untuk menentukan apakah value tersebut sudah ada atau belum. HashSet memanfaatkan fitur key pada HashMap, di mana valuenya disimpan dalam Objek Node Array dan index-nya berdasarkan hasil kalkulasi hash code. Untuk itu value yang disimpan di HashSet wajib meng-override method hashCode() & equals() dengan baik. Karena menggunakan index dari kalkulasi hash code, method add() & contains() kompleksitasnya jadi O(1), paling cepat dibanding Collection lain. Kecuali ada konflik hash code, kompleksitasnya bisa jadi O(log n) maupun O(n).
Set<String> integers = new HashSet<>();
integers.add("aaaxc");
integers.add("ccc");
integers.add("bb");
System.out.println("integers = " + integers); // [bb, ccc, aaaxc]LinkedHashSet
LinkedHashSet adalah varian dari HashSet di mana selain berbasis hash code, juga menyimpan referensi antar Node seperti LinkedList. Jika pada HashSet saat looping urutannya tergantung kalkulasi hash code, maka pada LinkedHashSet saat looping urutannya sesuai urutan Node. Selain itu kompleksitasnya sama dengan HashSet.
Set<String> strings = new LinkedHashSet<>();
strings.add("aaaxc");
strings.add("ccc");
strings.add("bb");
System.out.println("strings = " + strings); // [aaaxc, ccc, bb]EnumSet
EnumSet adalah Collection yang hanya menyimpan Enum value. Di sini algoritmanya lebih simple, value disimpan ke dalam Object Array dengan posisi index sesuai urutan value yang ditulis pada class Enum-nya. Jadi di dalam class Enum ada method ordinal() yang menyimpan posisi urutan value Enum saat ditulis. Saat menggunakan method add() maupun contains() kompleksitasnya selalu O(1) tanpa konflik.
Set<TimeUnit> units = EnumSet.of(TimeUnit.DAYS, TimeUnit.SECONDS);
units.add(TimeUnit.HOURS);
System.out.println("units = " + units); //[SECONDS, HOURS, DAYS]ConcurrentHashMapKeySet
ConcurrentHashMapKeySet adalah Set dengan fitur thread-safe karena menggunakan ConcurrentHashMap di dalam internalnya. Algoritmanya mirip dengan HashSet tapi dengan lock pada saat ada perubahan agar thread-safe.
Set<Integer> integers = ConcurrentHashMap.newKeySet();
integers.add(10);
integers.add(3);
integers.add(7);
System.out.println("integers = " + integers); // [3, 7, 10]CopyOnWriteArraySet
CopyOnWriteArraySet adalah Set yang menggunakan CopyOnWriteArrayList dengan fitur pengecekan value saat penambahan agar value-nya unik. CopyOnWriteArraySet juga Thread-Safe dan hanya synchronized saat ada perubahan saja. Kompleksitasnya sama seperti CopyOnWriteArrayList.
Set<Integer> integers = new CopyOnWriteArraySet<>();
integers.add(10);
integers.add(3);
integers.add(7);
System.out.println("integers = " + integers); // [10, 3, 7]NavigableSet
NavigableSet adalah Collection yang menyimpan value secara unik dan bisa diakses dari paling depan, belakang, atau yang mendekati value input. Di sini ada method floor() untuk mendapatkan value yang sama atau mendekati lebih kecil dan ceiling() untuk mendapatkan value yang sama atau mendekati lebih besar dari input. Juga ada method lower() untuk mendapatkan value yang lebih kecil dan higher() untuk mendapatkan value yang lebih besar dari input. Lalu ada method first() dan last() untuk mendapatkan value pertama dan terakhir yang di-sorting. Contoh implementasinya adalah TreeSet dan ConcurrentSkipListSet.
TreeSet
TreeSet adalah Collection yang menyimpan value secara unik dan semua valuenya di-sorting menggunakan Tree data structure. Value yang bisa digunakan adalah yang mengimplementasi Comparable, seperti String dan wrapper object, atau di-sorting sesuai konfigurasi pada constructor. Kompleksitasnya adalah O(log n) untuk semua method perubahan dan akses data.
NavigableSet<Integer> navigableSet = new TreeSet<>();
navigableSet.add(10);
navigableSet.add(3);
navigableSet.add(7);
System.out.println("navigableSet = " + navigableSet); // [3, 7, 10]
System.out.println("navigableSet = " + navigableSet.ceiling(7)); // 7
System.out.println("navigableSet = " + navigableSet.ceiling(9)); // 10
System.out.println("navigableSet = " + navigableSet.floor(9)); // 7
System.out.println("navigableSet = " + navigableSet.higher(7)); // 10
System.out.println("navigableSet = " + navigableSet.lower(10)); // 7
System.out.println("navigableSet = " + navigableSet.first()); // 3
System.out.println("navigableSet = " + navigableSet.last()); // 10ConcurrentSkipListSet
ConcurrentSkipListSet adalah Collection yang menyimpan value secara unik menggunakan Skip List data structure dan thread-safe. Skip List mengurutkan data berdasarkan value dan menghubungkannya lewat Node ke dalam beberapa layer tanpa locking. Sama seperti TreeSet, data yang disimpan juga unik dan di-sorting sesuai konfigurasi pada Constructor. Kompleksitasnya juga sama, yaitu O(log n) untuk semua method perubahan dan akses data.
NavigableSet<Integer> navigableSet = new ConcurrentSkipListSet<>();
navigableSet.add(10);
navigableSet.add(3);
navigableSet.add(7);
System.out.println("navigableSet = " + navigableSet); // [3, 7, 10]
System.out.println("navigableSet = " + navigableSet.ceiling(7)); // 7
System.out.println("navigableSet = " + navigableSet.ceiling(9)); // 10
System.out.println("navigableSet = " + navigableSet.floor(9)); // 7
System.out.println("navigableSet = " + navigableSet.higher(7)); // 10
System.out.println("navigableSet = " + navigableSet.lower(10)); // 7
System.out.println("navigableSet = " + navigableSet.first()); // 3
System.out.println("navigableSet = " + navigableSet.last()); // 10Map
Map adalah Collection khusus yang menyimpan 2 tipe data, yaitu key dan value, yang disebut juga sebagai Entry. Setiap key disimpan secara unik, jika ada key yang sama saat input maka Entry lama akan dihapus. Contoh implementasinya yaitu HashMap, LinkedHashMap, IdentityHashMap, WeakHashMap, Hashtable, EnumMap, dan implementasi dari NavigableMap & ConcurrentMap.
HashMap
HashMap adalah Map yang menyimpan Entry berdasarkan hash code dari key. Tipe data yang akan digunakan sebagai key wajib meng-override method hashCode() dan equals() dengan baik. Ini adalah implementasi Map yang paling sering dipakai untuk sebagian besar kasus. Behind the scene, Entry tersebut disimpan ke dalam objek Node Array pada index berdasarkan hasil kalkulasi hash code. Jika terjadi konflik, misalkan ada 2 key dengan hasil kalkulasi yang sama, maka akan dibandingkan key tersebut menggunakan method equals(). Jika berbeda, maka objek tersebut disimpan pada index yang sama secara LinkedList. Karena key yang disimpan berdasarkan index dari hash code, proses pencarian menggunakan containsKey() dan penginputan menggunakan put() kompleksitasnya O(1) selama tidak ada konflik key. Worst case-nya O(n) jika terjadi konflik karena akan disimpan secara LinkedList. Tapi HashMap juga bisa jadi O(log(n)) jika ada lebih dari 8 node dalam satu index (which is jarang terjadi) atau size-nya lebih dari 64, karena proses handle konfliknya ga LinkedList lagi, melainkan Red-Black Binary Tree.
Map<String, Integer> map = new HashMap<>();
map.put("satu", 1);
map.put("tiga", 3);
map.put(new String("tiga"), 3); // same value with "tiga" above and will replace
map.put("dua", 2);
System.out.println("map = " + map); // {dua=2, tiga=3, satu=1}LinkedHashMap
LinkedHashMap adalah Map yang meng-extend HashMap tapi dengan kemampuan menyimpan urutan Entry masuk. Jadi masing-masing Node di LinkedHashMap juga menyimpan referensi terhadap Entry pertama, kedua, ketiga, dan seterusnya. Sehingga ketika looping Entry yang ditampilkan sesuai urutan masuk. Berbeda dengan HashMap yang urutannya ketika looping tergantung kalkulasi hash code. Kompleksitasnya sama dengan HashMap.
Map<String, Integer> map = new LinkedHashMap<>();
map.put("satu", 1);
map.put("tiga", 3);
map.put("dua", 2);
System.out.println("map = " + map); // {satu=1, tiga=3, dua=2}IdentityHashMap
IdentityHashMap adalah Map yang berbasis hash code seperti HashMap. Yang membedakan adalah saat resolusi konflik. Jika pada HashMap saat terjadi konflik akan membandingkan value dari key lewat method equals(). Pada IdentityHashMap yang dibandingkan adalah instance objek lewat operator ==. Sisanya tidak ada perbedaan, kompleksitasnya pun sama.
Map<String, Integer> map = new IdentityHashMap<>();
map.put("satu", 1);
map.put("tiga", 3);
map.put(new String("tiga"), 3); // different instance with "tiga" above, no replace
map.put("dua", 2);
System.out.println("map = " + map); // {satu=1, tiga=3, dua=2, tiga=3}WeakHashMap
WeakHashMap adalah Map yang juga berbasis hash code, akan tetapi dengan behavior otomatis menghapus Entry yang key-nya sudah dihapus oleh Garbage Collector. Contohnya seperti ini:
Map<BigDecimal, String> weakHashMap = new WeakHashMap<>();
BigDecimal key = BigDecimal.valueOf(1000);
weakHashMap.put(key, "seribu");
System.out.println(weakHashMap); // {1000=seribu}
key = null; // remove reference key
System.gc(); // run the garbage collector
System.out.println(weakHashMap); // {} Entry is garbage-collectedHashtable
Hashtable adalah Map legacy yang berbasis hash tapi Thread-Safe. Secara performa lebih lambat dari HashMap karena Thread-Safe. Jaman sekarang ini sudah jarang digunakan, kalaupun ingin Map yang Thread-Safe lebih baik gunakan ConcurrentHashMap karena Hashtable melakukan synchronized pada setiap method read & write.
Map<String, Integer> map = new Hashtable<>();
map.put("satu", 1);
map.put("tiga", 3);
map.put("dua", 2);
System.out.println("map = " + map); // {dua=2, tiga=3, satu=1}EnumMap
EnumMap adalah Map yang menyimpan key berupa Enum. Value tersebut disimpan ke dalam sebuah Object Array yang posisinya berdasarkan ordinal dari Enum. Ini lebih optimal untuk menyimpan data yang key-nya berupa Enum dibanding menggunakan HashMap karena algoritmanya lebih simple. Kompleksitasnya selalu O(1) dan tanpa konflik karena ordinal sudah pasti unik.
Map<TimeUnit, Integer> map = new EnumMap<>(TimeUnit.class);
map.put(TimeUnit.DAYS, 1);
map.put(TimeUnit.MICROSECONDS, 3);
map.put(TimeUnit.HOURS, 2);
System.out.println("map = " + map); // {MICROSECONDS=3, HOURS=2, DAYS=1}NavigableMap
NavigableMap adalah Map yang menyimpan Entry yang bisa diakses dari paling depan, belakang, atau yang mendekatinya. Contoh implementasinya adalah TreeMap dan ConcurrentSkipListMap.
TreeMap
TreeMap adalah Map yang menyimpan Entry berdasarkan key yang di-sorting dengan cara membandingkan key menggunakan Tree data structure. TreeSet menggunakan fitur key pada TreeMap untuk menyimpan data unik dan terurut. Tipe data yang bisa digunakan sebagai key adalah yang mengimplementasi Comparable atau sorting-nya ditentukan sesuai konfigurasi pada constructor. Kompleksitas pada TreeMap adalah O(log n) untuk semua perubahan dan akses data.
NavigableMap<Integer, String> navigableMap = new TreeMap<>();
navigableMap.put(10, "sepuluh");
navigableMap.put(3, "tiga");
navigableMap.put(7, "tujuh");
System.out.println("navigableMap = " + navigableMap); // {3=tiga, 7=tujuh, 10=sepuluh}
System.out.println("navigableMap = " + navigableMap.ceilingEntry(7)); // 7=tujuh
System.out.println("navigableMap = " + navigableMap.ceilingEntry(9)); // 10=sepuluh
System.out.println("navigableMap = " + navigableMap.floorEntry(9)); // 7=tujuh
System.out.println("navigableMap = " + navigableMap.higherEntry(7)); // 10=sepuluh
System.out.println("navigableMap = " + navigableMap.lowerEntry(10)); // 7=tujuh
System.out.println("navigableMap = " + navigableMap.firstEntry()); // 3=tiga
System.out.println("navigableMap = " + navigableMap.lastEntry()); // 10=sepuluhConcurrentSkipListMap
ConcurrentSkipListMap adalah Map yang menyimpan Entry menggunakan Skip List data structure, yaitu valuenya di-sorting lewat node yang dihubungkan lewat beberapa layer. Ini juga dipakai oleh ConcurrentSkipListSet untuk menyimpan data unik. Key yang digunakan juga harus mengimplementasi Comparable atau di-sorting sesuai konfigurasi pada constructor. Yang paling membedakan dengan TreeMap adalah ConcurrentSkipListMap thread-safe tanpa locking, makanya ConcurrentSkipListMap juga mengimplementasi ConcurrentMap. Kompleksitasnya O(log n) untuk semua perubahan dan pembacaan data.
NavigableMap<Integer, String> navigableMap = new ConcurrentSkipListMap<>();
navigableMap.put(10, "sepuluh");
navigableMap.put(3, "tiga");
navigableMap.put(7, "tujuh");
System.out.println("navigableMap = " + navigableMap); // {3=tiga, 7=tujuh, 10=sepuluh}
System.out.println("navigableMap = " + navigableMap.ceilingEntry(7)); // 7=tujuh
System.out.println("navigableMap = " + navigableMap.ceilingEntry(9)); // 10=sepuluh
System.out.println("navigableMap = " + navigableMap.floorEntry(9)); // 7=tujuh
System.out.println("navigableMap = " + navigableMap.higherEntry(7)); // 10=sepuluh
System.out.println("navigableMap = " + navigableMap.lowerEntry(10)); // 7=tujuh
System.out.println("navigableMap = " + navigableMap.firstEntry()); // 3=tiga
System.out.println("navigableMap = " + navigableMap.lastEntry()); // 10=sepuluhConcurrentMap
ConcurrentMap adalah Map menyimpan Entry secara thread-safe. Contoh implementasinya adalah ConcurrentHashMap dan ConcurrentSkipListMap.
ConcurrentHashMap
ConcurrentHashMap adalah HashMap yang thread-safe. Cara kerjanya mirip dengan HashMap. Hanya saja pada ConcurrentHashMap semua perubahan data pada Node yang sama akan di-lock agar thread-safe. Yang di-lock bukan keseluruhan Node atau objek, tapi Node yang berubah saja. Sedangkan untuk pembacaan data tidak ada locking. Cukup efisien untuk Concurrency. Untuk kompleksitasnya sama seperti HashMap.
ConcurrentMap<String, Integer> map = new ConcurrentHashMap<>();
map.put("satu", 1);
map.put("tiga", 3);
map.put("dua", 2);
System.out.println("map = " + map); // {dua=2, tiga=3, satu=1}Verdict
Itulah macam-macam Collection pada Java. Kesimpulannya adalah:
- Dahulukan penggunaan interface yang paling tinggi seperti menggunakan Collection pada parameter agar fleksibel, kecuali ada kebutuhan spesifik untuk menggunakan interface atau class tertentu;
- Jangan overuse menggunakan List untuk semua hal, untuk kasus spesifik pertimbangkan Collection lain;
- ArrayList adalah Collection yang umum digunakan untuk banyak kasus karena paling mirip dengan Array tapi dinamis;
- LinkedList jarang digunakan sebagai List karena ga efisien saat akses value;
- Queue cocok untuk menampilkan value sesuai urutan keluar, bukan untuk looping value yang disimpan;
- PriorityQueue cocok untuk menampilkan value yang keluar secara terurut;
- BlockingQueue cocok untuk menampung value sesuai ketentuan dan ngeblok jika di luar ketentuan;
- Deque cocok untuk mengeluarkan value dari urutan paling depan maupun belakang;
- HashSet dan HashMap paling populer digunakan pada Set dan Map karena cukup cepat;
- ConcurrentHashMapKeySet dan ConcurrentHashMap cocok untuk kasus sederhana yang memerlukan thread-safe;
- LinkedHashSet dan LinkedHashMap cocok untuk kasus yang membutuhkan urutan masuk saat diakses;
- EnumSet dan EnumMap cocok untuk tipe data Enum karena kompleksitasnya selalu O(1) tanpa konflik;
- TreeSet dan TreeMap cocok untuk menyimpan data unik yang di-sorting dan dapat melakukan navigasi value;
- ConcurrentSkipListSet dan ConcurrentSkipListMap cocok untuk menyimpan data yang di-sorting dan thread-safe;
- Untuk Collection yang berbasis hash, tipe datanya wajib meng-override
hashCode()danequals()agar optimal; - Untuk Collection yang berbasis sorting value, tipe datanya wajib mengimplementasi Comparable atau sorting-nya ditentukan lewat konfigurasi pada constructor;