Pengertian Struktur Data Hash Table
Struktur data Hash Table adalah struktur data yang digunakan untuk menyimpan dan mengelola data dengan cepat dan efisien. Ini beroperasi dengan prinsip kunci-nilai, di mana setiap elemen data memiliki kunci yang unik yang digunakan untuk mengakses atau memanipulasinya.
Hash Table (Tabel Hash) adalah struktur data yang mengorganisir data ke dalam pasangan kunci-nilai. Ini menggunakan fungsi hash untuk mengonversi kunci menjadi indeks dalam array.
Dengan cara ini, akses ke data menjadi sangat cepat karena kita dapat langsung menghitung indeks tempat data disimpan. Ini cocok untuk pencarian, penyisipan, penghapusan, dan pembaruan data dalam waktu konstan , asalkan tidak ada konflik dalam fungsi hash (collision).
Kegunaan Struktur Data Hash Table
- Pencarian Cepat: Dapat digunakan untuk mencari data dengan cepat berdasarkan key. Ini sangat berguna dalam aplikasi seperti basis data, kamus, dan cache.
- Penyimpanan Data: Hash table dapat digunakan untuk menyimpan data dengan efisien. Data dapat diambil dan dimasukkan ke dalam tabel dengan waktu konstan, asalkan tidak ada collision yang signifikan.
- Implementasi Struktur Data Lain: Hash table dapat digunakan untuk mengimplementasikan struktur data lain, seperti set dan map.
Cara kerja Struktur Data Hash Table
1. Inisialisasi
Hash Table awalnya dibuat dengan ukuran tertentu, yang biasanya merupakan bilangan prima. Ukuran ini dapat disesuaikan sesuai kebutuhan.
2. Fungsi Hash
Hash Table menggunakan fungsi hash untuk memetakan nilai yang diberikan dengan kunci tertentu ke indeks dalam array. Fungsi hash ini harus menghasilkan nilai yang unik untuk setiap kunci yang berbeda, sehingga elemen-elemen dapat disimpan dengan benar.
3. Pemetaan Nilai
Ketika sebuah elemen baru ditambahkan ke Hash Table, fungsi hash digunakan untuk menentukan indeks tempat elemen tersebut akan disimpan dalam array. Ini memungkinkan akses cepat ke elemen berdasarkan kunci.
4. Penanganan Bentrokan
Dalam beberapa kasus, dua kunci yang berbeda dapat menghasilkan nilai hash yang sama. Ini disebut bentrokan. Hash Table harus memiliki mekanisme untuk menangani bentrokan ini.
Beberapa metode yang umum digunakan adalah chaining (menggunakan linked list untuk menyimpan elemen dengan nilai hash yang sama) dan linear probing (mencari slot kosong berikutnya dalam array jika terjadi bentrokan).
5. Operasi Utama
Operasi utama yang digunakan dalam Hash Table adalah pencarian (untuk mencari elemen berdasarkan kunci), penambahan (untuk menambahkan elemen baru), dan penghapusan (untuk menghapus elemen). Fungsi hash digunakan dalam operasi ini untuk menentukan indeks elemen yang akan diakses atau dimodifikasi.
6. Efisiensi
Efisiensi Hash Table tergantung pada efisiensi fungsi hash yang digunakan. Fungsi hash yang baik harus menghasilkan distribusi nilai hash yang merata untuk menghindari bentrokan yang berlebihan.
Selain itu, ukuran Hash Table juga dapat mempengaruhi efisiensi, karena ukuran yang terlalu kecil dapat menyebabkan banyak bentrokan, sementara ukuran yang terlalu besar dapat menyebabkan pemborosan memori.
Operasi dalam Struktur Data Hash Table
- Pencarian (Search): Digunakan untuk mencari elemen/data dalam Hash Table berdasarkan kunci atau indeksnya. Pencarian dilakukan dengan menggunakan fungsi hash untuk menghasilkan indeks elemen yang dicari.
- Penyisipan (Insertion): Operasi ini digunakan untuk menyisipkan elemen/data baru ke dalam Hash Table. Elemen baru akan ditempatkan pada indeks yang dihasilkan oleh fungsi hash.
- Penghapusan (Deletion): Digunakan untuk menghapus elemen/data dari Hash Table berdasarkan kunci atau indeksnya. Elemen yang dihapus akan dihapus dari indeks yang dihasilkan oleh fungsi hash.
- Update: Operasi ini digunakan untuk mengubah nilai elemen/data yang sudah ada dalam Hash Table. Nilai elemen dapat diubah berdasarkan kunci atau indeksnya.
- Collision Handling: Collision terjadi ketika dua atau lebih elemen memiliki indeks yang sama setelah melalui fungsi hash. Operasi ini digunakan untuk menangani collision dan memastikan bahwa elemen-elemen dengan indeks yang sama dapat disimpan dan diakses dengan benar.
- Resize: Operasi ini digunakan untuk mengubah ukuran Hash Table jika jumlah elemen/data yang disimpan melebihi kapasitas yang ditentukan. Resize dilakukan untuk menjaga efisiensi dan kinerja Hash Table.
- Iterasi: Operasi yang digunakan untuk mengakses dan memproses semua elemen/data yang ada dalam Hash Table secara berurutan.
Contoh Program Struktur Data Hash Table
import java.util.HashMap;
public class HashTableExample {
public static void main(String[] args) {
// Membuat objek Hash Table
HashMap<String, Integer> hashTable = new HashMap<>();
// Menambahkan data ke Hash Table
hashTable.put("John", 25);
hashTable.put("Jane", 30);
hashTable.put("Alice", 28);
// Mengakses data dalam Hash Table
int johnAge = hashTable.get("John");
System.out.println("John's age: " + johnAge);
// Menghapus data dari Hash Table
hashTable.remove("Jane");
// Menampilkan semua data dalam Hash Table
for (String name : hashTable.keySet()) {
int age = hashTable.get(name);
System.out.println(name + "'s age: " + age);
}
}
}
Program di atas menggunakan kelas HashMap
dari Java untuk membuat dan mengelola Hash Table. Data berupa pasangan kunci-nilai, di mana kunci adalah nama dan nilai adalah usia. Program ini menunjukkan cara menambahkan data, mengakses data berdasarkan kunci, menghapus data, dan menampilkan semua data dalam Hash Table.