Hashtables menyediakan cara yang berguna untuk mengoptimalkan kinerja aplikasi.
Hashtable bukanlah konsep baru di bidang komputer. Mereka dirancang untuk mempercepat pemrosesan komputer, yang sangat lambat menurut standar saat ini, dan memungkinkan Anda dengan cepat menemukan entri tertentu ketika menanyakan banyak entri data. Meskipun mesin modern ribuan kali lebih cepat, tabel hash masih merupakan alat yang berguna untuk mendapatkan performa terbaik dari aplikasi Anda.
Bayangkan Anda memiliki file data yang berisi sekitar seribu catatan - misalnya catatan pelanggan untuk bisnis kecil - dan sebuah program yang membaca catatan tersebut ke dalam memori untuk diproses. Setiap catatan berisi lima digit nomor ID pelanggan unik, nama pelanggan, alamat, saldo rekening, dll. Asumsikan bahwa catatan tidak diurutkan berdasarkan nomor ID pelanggan. Oleh karena itu, jika program ingin menggunakan nomor pelanggan sebagai "kunci" untuk menemukan catatan pelanggan tertentu, satu-satunya cara untuk menemukannya adalah dengan mencari setiap catatan secara berurutan. Kadang-kadang, ia akan menemukan catatan yang Anda perlukan dengan cepat; namun kadang-kadang, sebelum program menemukan catatan yang Anda perlukan, ia hampir mencari catatan terakhir. Jika Anda ingin mencari di antara 1.000 catatan, kemudian menemukan satu catatan memerlukan program untuk memeriksa rata-rata 500,5 ((1000 + 1)/2) catatan. Jika Anda sering perlu mencari data, Anda mungkin memerlukan cara yang lebih cepat untuk menemukan data.
Salah satu cara untuk mempercepat pencarian Anda adalah dengan memecah catatan menjadi beberapa bagian sehingga alih-alih mencari satu daftar besar, Anda mencari beberapa daftar pendek. Untuk nomor ID pelanggan numerik kami, Anda dapat membuat 10 daftar - satu daftar nomor ID dimulai dengan 0, satu daftar nomor ID dimulai dengan 1, dan seterusnya. Jadi untuk mengetahui nomor ID pelanggan 38016, Anda hanya perlu mencari daftar yang dimulai dengan angka 3. Jika terdapat 1.000 catatan dan rata-rata panjang setiap daftar adalah 100 (1.000 catatan dibagi menjadi 10 daftar), maka jumlah rata-rata perbandingan untuk mencari catatan turun menjadi sekitar 50 (lihat Gambar 1).
Tentu saja, jika sekitar satu dari sepuluh nomor pelanggan dimulai dengan angka 0, sepersepuluh lainnya dimulai dengan angka 1, dan seterusnya, maka pendekatan ini akan berhasil dengan baik. Jika 90% nomor pelanggan dimulai dengan 0, maka daftar tersebut akan memiliki 900 catatan, yang memerlukan rata-rata 450 perbandingan per pencarian. Selain itu, 90% pencarian yang perlu dilakukan program adalah angka yang dimulai dengan 0. Oleh karena itu, angka perbandingan rata-rata berada jauh di luar cakupan operasi matematika sederhana.
Akan lebih baik jika kita dapat mendistribusikan catatan dalam daftar kita sedemikian rupa sehingga setiap daftar memiliki entri yang hampir sama, terlepas dari distribusi angka dalam nilai kuncinya. Kami memerlukan cara untuk memadukan jumlah pelanggan dan mendistribusikan hasilnya dengan lebih baik. Sebagai contoh, kita dapat mengambil masing-masing digit suatu bilangan, mengalikannya dengan suatu bilangan besar (yang bervariasi tergantung pada posisi digit tersebut), menjumlahkan hasilnya untuk menghasilkan total, membagi bilangan tersebut dengan 10, dan memberikan sisanya sebagai Indeks nilai (indeks). Ketika sebuah record dibaca, program menjalankan fungsi hash ini pada nomor pelanggan untuk menentukan di daftar mana record tersebut berada. Saat pengguna perlu melakukan kueri, fungsi hash yang sama digunakan sebagai "kunci" untuk nomor pelanggan sehingga daftar yang benar dapat dicari. Struktur data seperti ini disebut tabel hash.
Hashtable di Jawa
Java berisi dua kelas, java.util.Hashtable dan java.util.HashMap , yang menyediakan mekanisme hashtable multiguna. Kedua kelas ini sangat mirip dan umumnya menyediakan antarmuka publik yang sama. Namun keduanya memiliki beberapa perbedaan penting, yang akan saya bicarakan nanti.
Objek Hashtable dan HashMap memungkinkan Anda menggabungkan kunci dan nilai dan memasukkan pasangan kunci/nilai ke dalam tabel menggunakan metode put (). Anda kemudian bisa mendapatkan nilainya dengan memanggil metode get(), meneruskan kunci sebagai parameter. Kunci dan nilai dapat berupa objek apa saja asalkan memenuhi dua persyaratan dasar. Perhatikan bahwa karena kunci dan nilai harus berupa objek, tipe primitif harus dikonversi menjadi objek menggunakan metode seperti Integer(int).
Untuk menggunakan objek kelas tertentu sebagai kunci, kelas tersebut harus menyediakan dua metode, sama dengan() dan kode hash(). Kedua metode ini ada di java.lang.Object , jadi semua kelas dapat mewarisi kedua metode ini; namun, penerapan kedua metode ini di kelas Object umumnya tidak berguna, jadi Anda biasanya perlu membebani sendiri kedua metode ini.
Metode Equals() membandingkan objeknya dengan objek lain dan mengembalikan nilai true jika kedua objek mewakili informasi yang sama. Metode ini juga bertujuan untuk memastikan bahwa kedua objek berada dalam kelas yang sama. Object.equals() mengembalikan nilai true jika kedua objek referensi adalah objek yang identik, yang menjelaskan mengapa metode ini umumnya tidak cocok. Dalam kebanyakan kasus, Anda memerlukan cara untuk membandingkan bidang demi bidang, jadi kami menganggap objek berbeda yang mewakili data yang sama adalah sama.
Metode HashCode() menghasilkan nilai int dengan menjalankan fungsi hash menggunakan konten objek. Hashtable dan HashMap menggunakan nilai ini untuk mengetahui di keranjang (atau daftar) mana pasangan kunci/nilai berada.
Sebagai contoh, kita dapat melihat kelas String, karena ia mempunyai metode sendiri yang mengimplementasikan kedua metode ini. String.equals() membandingkan dua objek String karakter demi karakter dan mengembalikan nilai true jika stringnya sama:
Copy kode kodenya sebagai berikut:
String Namasaya = "Einstein";
// Tes berikut ini adalah
// selalu benar
if ( Namaku.sama dengan("Einstein") )
{ ...
String.hashCode() menjalankan fungsi hash pada string. Kode numerik setiap karakter dalam string dikalikan dengan 31, dan hasilnya bergantung pada posisi karakter dalam string. Hasil perhitungan tersebut kemudian dijumlahkan sehingga menghasilkan total. Proses ini mungkin tampak rumit, namun menjamin distribusi nilai yang lebih baik. Ini juga menunjukkan seberapa jauh Anda bisa melangkah ketika mengembangkan metode hashCode() Anda sendiri, dengan yakin bahwa hasilnya unik.
Misalnya, saya ingin menggunakan tabel hash untuk mengimplementasikan katalog buku dan menggunakan nomor ISBN buku tersebut sebagai kunci pencarian untuk mencari. Saya dapat menggunakan kelas String untuk membawa detailnya dan menyiapkan metode sama dengan() dan kode hash() (lihat Daftar 1). Kita dapat menambahkan pasangan kunci/nilai ke tabel hash menggunakan metode put () (lihat Daftar 2).
Metode Put () menerima dua parameter, keduanya bertipe Object. Parameter pertama adalah kunci; parameter kedua adalah nilai. Metode Put () memanggil metode hashCode() kunci dan membagi hasilnya dengan jumlah daftar dalam tabel. Gunakan sisanya sebagai nilai indeks untuk menentukan ke daftar mana rekaman tersebut ditambahkan. Perhatikan bahwa kuncinya unik dalam tabel; jika Anda memanggil put () dengan kunci yang ada, entri yang cocok diubah sehingga merujuk ke nilai baru dan nilai lama dikembalikan ( Ketika kunci tidak ada dalam tabel , put () mengembalikan nilai nol).
Untuk membaca nilai dari tabel, kita menggunakan kunci pencarian dengan metode get(). Ia mengembalikan referensi Objek yang dikonversi ke tipe yang benar:
Copy kode kodenya sebagai berikut:
Catatan Buku br =
(Catatan Buku)isbnTable.get(
"0-345-40946-9");
Sistem.keluar.println(
"Penulis:" + br.penulis
+ "Judul:" + br.judul);
Metode lain yang berguna adalah hapus(), yang digunakan hampir sama dengan get(). Metode ini menghapus entri dari tabel dan mengembalikannya ke program pemanggil.
kelasmu sendiri
Jika Anda ingin menggunakan tipe primitif sebagai kunci, Anda harus membuat objek dengan tipe yang sama. Misalnya, jika Anda ingin menggunakan kunci integer, Anda harus menggunakan konstruktor Integer(int) untuk menghasilkan objek dari integer. Semua kelas pembungkus seperti Integer, Float, dan Boolean memperlakukan nilai primitif sebagai objek, dan membebani metode sama dengan() dan kode hash(), sehingga dapat digunakan sebagai kunci. Banyak kelas lain yang disediakan di JDK juga seperti ini (bahkan kelas Hashtable dan HashMap mengimplementasikan metode sama dengan() dan hashCode() mereka sendiri), tetapi Anda harus memeriksa dokumentasi sebelum menggunakan objek dari kelas mana pun sebagai kunci tabel hash. Penting juga untuk memeriksa sumber kelas untuk melihat bagaimana equal() dan hashCode() diimplementasikan. Misalnya, Byte, Character, Short, dan Integer semuanya mengembalikan nilai integer yang diwakili sebagai kode hash. Ini mungkin sesuai atau mungkin tidak sesuai dengan kebutuhan Anda.
Menggunakan Hashtable di Java
Jika Anda ingin membuat tabel hash yang menggunakan objek kelas yang Anda definisikan sebagai kunci, maka Anda harus memastikan bahwa metode sama dengan() dan kode hash() kelas tersebut memberikan nilai yang berguna. Pertama-tama lihat kelas yang Anda perluas untuk menentukan apakah implementasinya memenuhi kebutuhan Anda. Jika tidak, Anda harus membebani metode ini secara berlebihan.
Batasan desain dasar dari setiap metode sama dengan() adalah metode tersebut harus mengembalikan nilai true jika objek yang diteruskan ke metode tersebut termasuk dalam kelas yang sama dan bidang datanya disetel ke nilai yang mewakili data yang sama. Anda juga harus memastikan bahwa jika Anda meneruskan argumen kosong ke metode tersebut, kode Anda akan kembali
Copy kode kodenya sebagai berikut:
salah：boolean publik sama dengan(Objek o)
{
jika ( (o == nol)
||. !(o contoh Kelasku))
{
kembali salah;
}
// Sekarang bandingkan kolom data...
Selain itu, ada beberapa aturan yang harus diingat saat merancang metode hashCode(). Pertama, metode harus mengembalikan nilai yang sama untuk objek tertentu, terlepas dari berapa kali metode tersebut dipanggil (tentu saja, selama konten objek tidak berubah di antara panggilan. Saat menggunakan objek sebagai kunci tabel hash, Ini seharusnya dihindari). Kedua, jika dua objek yang didefinisikan oleh metode sama dengan() Anda sama, keduanya juga harus menghasilkan kode hash yang sama. Ketiga, dan ini lebih merupakan pedoman daripada prinsip, Anda harus mencoba merancang metode Anda sehingga menghasilkan hasil yang berbeda untuk konten objek yang berbeda. Tidak masalah jika terkadang objek berbeda menghasilkan kode hash yang sama. Namun, jika metode hanya dapat mengembalikan nilai dalam rentang 1 hingga 10, maka hanya 10 daftar yang dapat digunakan, berapa pun jumlah daftar dalam tabel hash.
Faktor lain yang perlu diingat saat mendesain sama dengan() dan kode hash() adalah kinerja. Setiap panggilan ke put () atau get() melibatkan pemanggilan hashCode() untuk menemukan daftar yang benar. Saat get() memindai daftar untuk menemukan kuncinya, ia memanggil sama dengan() untuk setiap elemen dalam daftar. Terapkan metode ini agar berjalan secepat dan seefisien mungkin, terutama jika Anda berencana membuat kelas Anda tersedia untuk umum, karena pengguna lain mungkin ingin menggunakan kelas Anda dalam aplikasi berperforma tinggi yang mengutamakan kecepatan eksekusi.
Kinerja yang dapat di-hash
Faktor utama yang mempengaruhi efisiensi tabel hash adalah rata-rata panjang daftar dalam tabel, karena rata-rata waktu pencarian berhubungan langsung dengan panjang rata-rata tersebut. Tentunya, untuk mengurangi panjang rata-rata, Anda harus menambah jumlah daftar di tabel hash; Anda akan mendapatkan efisiensi pencarian terbaik jika jumlah daftar sangat banyak sehingga sebagian besar atau semua daftar hanya berisi satu catatan. Namun, hal ini mungkin keterlaluan. Jika tabel hash Anda memiliki lebih banyak daftar daripada entri data, maka Anda tidak perlu mengeluarkan biaya memori sebesar itu, dan dalam beberapa kasus, tidak mungkin orang menerima pendekatan ini.
Pada contoh sebelumnya, kita mengetahui sebelumnya berapa banyak record yang kita miliki, 1.000. Mengetahui hal ini, kami dapat memutuskan berapa banyak daftar tabel hash yang harus kami isi untuk mencapai kompromi terbaik antara kecepatan pencarian dan efisiensi penggunaan memori. Namun, dalam banyak kasus, Anda tidak mengetahui sebelumnya berapa banyak catatan yang akan Anda proses; file tempat data dibaca mungkin terus bertambah, atau jumlah catatan dapat berubah secara signifikan dari hari ke hari.
Kelas Hashtable dan HashMap menangani masalah ini dengan memperluas tabel secara dinamis saat entri ditambahkan. Kedua kelas memiliki konstruktor yang menerima jumlah awal daftar dalam tabel, dan faktor beban sebagai parameter:
Hashtable publik(
int kapasitas awal,
faktor beban mengambang)
HashMap publik(
int kapasitas awal,
faktor beban mengambang)
Kalikan kedua angka ini untuk menghitung nilai kritis. Setiap kali entri baru ditambahkan ke tabel hash, hitungannya diperbarui, dan ketika hitungannya melebihi nilai kritis, tabelnya di-reset (pengulangan). (Ukuran daftar ditingkatkan menjadi dua kali ukuran sebelumnya ditambah 1, dan semua entri dipindahkan ke daftar yang benar.) Konstruktor default menetapkan kapasitas awal menjadi 11 dan faktor beban menjadi 0,75, sehingga nilai kritisnya adalah 8. Ketika catatan kesembilan ditambahkan ke tabel, tabel hash diubah skalanya sehingga memiliki 23 daftar, dan nilai kritis baru akan menjadi 17 (bagian bilangan bulat dari 23*0,75). Anda dapat melihat bahwa faktor beban adalah batas atas jumlah rata-rata daftar dalam tabel hash, yang berarti bahwa, secara default, tabel hash jarang memiliki banyak daftar yang berisi lebih dari satu catatan. Bandingkan contoh awal kami, di mana kami memiliki 1.000 catatan yang tersebar di 10 daftar. Jika kita menggunakan nilai default, tabel ini akan diperluas hingga berisi lebih dari 1.500 daftar. Tapi Anda bisa mengendalikannya. Jika jumlah daftar dikalikan dengan faktor muatan lebih besar dari jumlah entri yang Anda proses, tabel tidak akan pernah dibuat ulang, jadi kita bisa mengikuti contoh di bawah ini:
Copy kode kodenya sebagai berikut:
// Tabel tidak akan diulang sampai selesai
// memiliki 1.100 entri (10*110):
Hashtable myHashTable =
Hashtable baru (10, 110.0F);
Anda mungkin tidak ingin melakukan ini kecuali Anda tidak ingin menghemat memori untuk daftar kosong dan tidak keberatan dengan waktu pencarian tambahan, yang mungkin terjadi pada sistem tertanam. Namun, pendekatan ini dapat berguna karena pengaturan ulang memerlukan komputasi yang mahal, dan pendekatan ini memastikan bahwa pengaturan ulang tidak pernah terjadi.
Perhatikan bahwa meskipun memanggil put () dapat menyebabkan tabel bertambah (menambah jumlah daftar), memanggil delete() tidak akan memiliki efek sebaliknya. Jadi, jika Anda memiliki tabel besar dan menghapus sebagian besar entri di dalamnya, Anda akan mendapatkan tabel besar namun sebagian besar kosong.
Hashtable dan HashMap
Ada tiga perbedaan penting antara kelas Hashtable dan HashMap. Perbedaan pertama terutama karena alasan historis. Hashtable didasarkan pada kelas Kamus lama, dan HashMap adalah implementasi antarmuka Peta yang diperkenalkan di Java 1.2.
Mungkin perbedaan yang paling penting adalah metode Hashtable bersifat sinkron, sedangkan metode HashMap tidak. Artinya, meskipun Anda dapat menggunakan Hashtable dalam aplikasi multi-thread tanpa melakukan tindakan khusus apa pun, Anda juga harus menyediakan sinkronisasi eksternal untuk HashMap. Metode yang mudah digunakan adalah dengan menggunakan metode staticsynchronousMap() dari kelas Collections, yang membuat objek Map yang aman untuk thread dan mengembalikannya sebagai objek yang dienkapsulasi. Metode objek ini memungkinkan Anda mengakses HashMap yang mendasarinya secara sinkron. Hasilnya adalah Anda tidak dapat menghentikan sinkronisasi di Hashtable saat Anda tidak membutuhkannya (seperti dalam aplikasi single-thread), dan sinkronisasi menambah banyak overhead pemrosesan.
Perbedaan ketiga adalah hanya HashMap yang memungkinkan Anda menggunakan nilai null sebagai kunci atau nilai entri tabel. Hanya satu record dalam HashMap yang bisa menjadi kunci kosong, namun sejumlah entri bisa menjadi nilai kosong. Artinya jika kunci pencarian tidak ditemukan dalam tabel, atau jika kunci pencarian ditemukan tetapi nilainya nol, maka get() akan mengembalikan nol. Jika perlu, gunakan metode containerKey() untuk membedakan kedua situasi tersebut.
Beberapa informasi menyarankan bahwa ketika sinkronisasi diperlukan, gunakan Hashtable, jika tidak gunakan HashMap. Namun karena HashMap dapat disinkronkan saat dibutuhkan, HashMap memiliki lebih banyak fungsi daripada Hashtable, dan tidak didasarkan pada kelas lama, beberapa orang berpikir bahwa HashMap lebih disukai daripada Hashtable dalam berbagai situasi.
Tentang Properti
Terkadang, Anda mungkin ingin menggunakan tabel hash untuk memetakan string kunci ke string nilai. Ada beberapa contoh string lingkungan di DOS, Windows dan Unix. Misalnya, string kunci PATH dipetakan ke string nilai C:/WINDOWS;C:/WINDOWS/SYSTEM. Hashtables adalah cara sederhana untuk merepresentasikannya, namun Java menyediakan cara lain.
Kelas Java .util.Properties adalah subkelas Hashtable yang dirancang untuk digunakan dengan kunci dan nilai String. Penggunaan objek Properties mirip dengan penggunaan Hashtable, tetapi kelas menambahkan dua metode penghemat waktu yang harus Anda ketahui.
Metode Store() menyimpan konten objek Properties ke file dalam bentuk yang dapat dibaca. Metode Load() justru sebaliknya, digunakan untuk membaca file dan mengatur objek Properties agar berisi kunci dan nilai.
Perhatikan bahwa karena Properties memperluas Hashtable, Anda dapat menggunakan metode put () superclass untuk menambahkan kunci dan nilai yang bukan objek String. Ini tidak disarankan. Selain itu, jika Anda menggunakan store() dengan objek Properties yang tidak berisi objek String, store() akan gagal. Sebagai alternatif untuk put () dan get(), Anda harus menggunakan setProperty() dan getProperty(), yang menggunakan parameter String.
Oke, saya harap Anda sekarang tahu cara menggunakan tabel hash untuk mempercepat pemrosesan Anda