Tabel Hash adalah struktur data yang digunakan untuk menyimpan dan mengambil data dengan cepat. Ia bekerja dengan menggunakan fungsi hash untuk memetakan kunci item yang disimpan ke indeks tertentu dalam array, sehingga memungkinkan untuk mengakses data dalam waktu yang konstan, berapa pun ukuran kumpulan datanya .
Dalam tabel hash, data disimpan dalam pasangan nilai kunci. Saat Anda ingin menambahkan atau mengambil item dari tabel, Anda memberikan kuncinya dan fungsi hash memetakan kunci tersebut ke indeks tertentu dalam array. Nilai tersebut kemudian disimpan pada indeks tersebut, atau diambil dari indeks tersebut, tergantung kasusnya.
Tabel hash sangat efisien untuk menyimpan dan mengambil data dan banyak digunakan dalam berbagai aplikasi seperti database, cache, dan peta hash dalam bahasa pemrograman. Mereka menawarkan pencarian, penyisipan, dan penghapusan yang cepat, menjadikannya pilihan populer untuk mengimplementasikan array, set, dan peta asosiatif.
Implementasi ini memiliki ukuran tetap untuk tabel hash, yang ditentukan saat objek HashTable dibuat. Ia memiliki metode hash() yang mengambil kunci sebagai masukan dan mengembalikan indeks dalam array tempat nilai harus disimpan atau diambil. Metode insert(), get(), dan remove() menggunakan metode hash() untuk menemukan indeks dan kemudian melakukan operasi terkait pada nilai yang disimpan pada indeks tersebut.
class HashTable {
constructor(size) {
this.size = size;
this.buckets = new Array(size);
}
hash(key) {
let hash = 0;
for (let i = 0; i < key.length; i++) {
hash += key.charCodeAt(i);
}
return hash % this.size;
}
insert(key, value) {
let index = this.hash(key);
if (!this.buckets[index]) {
this.buckets[index] = [];
}
this.buckets[index].push({key, value});
}
get(key) {
let index = this.hash(key);
if (!this.buckets[index]) return null;
for (let i = 0; i < this.buckets[index].length; i++) {
if (this.buckets[index][i].key === key) {
return this.buckets[index][i].value;
}
}
return null;
}
remove(key) {
let index = this.hash(key);
if (!this.buckets[index]) return null;
for (let i = 0; i < this.buckets[index].length; i++) {
if (this.buckets[index][i].key === key) {
this.buckets[index].splice(i, 1);
return;
}
}
}
}
const hashTable = new HashTable(10);
hashTable.insert('abc', 123);
hashTable.insert('def', 456);
console.log(hashTable.get('abc')); // 123
console.log(hashTable.get('def')); // 456
hashTable.remove('abc');
console.log(hashTable.get('abc')); // null
Fungsi Hash
Fungsi hash adalah fungsi yang mengambil masukan (disebut “kunci”) dan mengembalikan keluaran berukuran tetap (disebut “nilai hash” atau “kode hash”) yang dihitung berdasarkan kunci. Tujuan utama dari fungsi hash adalah untuk mengambil masukan yang besar dan memetakannya ke keluaran yang lebih kecil sedemikian rupa sehingga relatif mudah untuk menemukan kunci asli berdasarkan nilai hash, namun tidak mungkin untuk menghasilkan kunci asli berdasarkan pada nilai hash saja.
Properti utama dari fungsi hash yang baik adalah:
- Efisien untuk dihitung: Fungsi hash harus cepat untuk dihitung dan tidak memerlukan banyak sumber daya.
- Deterministik: Masukan yang sama harus selalu menghasilkan keluaran yang sama, sehingga kunci yang sama dapat dengan mudah ditemukan menggunakan nilai hash yang sama.
- Distribusi seragam: Output dari fungsi hash harus didistribusikan secara merata pada rentang nilai hash yang mungkin, sehingga kunci didistribusikan secara merata di seluruh tabel hash.
- Tahan benturan: Fungsi hash harus meminimalkan kemungkinan dua kunci berbeda memiliki nilai hash yang sama, yang juga dikenal sebagai tabrakan.
Fungsi hash banyak digunakan dalam berbagai aplikasi, seperti penyimpanan dan pengambilan data, kriptografi, dan penambangan data. Dalam konteks tabel hash, fungsi hash yang baik harus mampu memetakan kunci dari item yang disimpan ke indeks unik dalam susunan tabel hash, sehingga setiap kunci dapat dengan mudah dimasukkan dan diambil.
Ada banyak fungsi hash berbeda yang dapat digunakan, dan pilihan fungsi hash bergantung pada kebutuhan spesifik aplikasi. Beberapa fungsi hash yang umum mencakup hash modulo, hash universal, dan hash kriptografi.
Berikut beberapa contoh fungsi hash lainnya yang dapat digunakan dalam tabel hash:
Modulo hash
Fungsi hash ini menggunakan operator modulo untuk memetakan kunci ke indeks dalam array tabel hash. Misalnya:
function moduloHash(key, size) {
let hash = 0;
for (let i = 0; i < key.length; i++) {
hash += key.charCodeAt(i);
}
return hash % size;
}
Hash kriptografi
Ini adalah jenis fungsi hash yang menggunakan fungsi hash yang dihasilkan secara acak untuk setiap kunci, yang membuatnya lebih tahan terhadap serangan tabrakan. Berikut adalah contoh fungsi hash universal:
const crypto = require('crypto');
function cryptographicHash(key) {
return crypto.createHash('sha1').update(key).digest('hex');
}
Tabel hash berukuran dinamis
Tabel hash dapat diimplementasikan dengan mengubah ukuran array secara dinamis, yang berarti ukuran array dapat berubah berdasarkan jumlah elemen dalam tabel.
Salah satu cara umum untuk mengimplementasikan tabel hash berukuran dinamis adalah dengan menggunakan faktor beban, yang merupakan ukuran seberapa penuh tabel hash. Ketika jumlah elemen dalam tabel hash melebihi ambang batas tertentu (ditentukan oleh faktor beban), ukuran array akan diubah ke ukuran yang lebih besar untuk memberikan ruang bagi lebih banyak elemen. Demikian pula, ketika jumlah elemen berada di bawah ambang batas tertentu, array akan diubah ukurannya ke ukuran yang lebih kecil untuk menghemat ruang.
Berikut adalah contoh bagaimana tabel hash berukuran dinamis dapat diimplementasikan dalam JavaScript menggunakan sintaks ES6:
class HashTable {
constructor() {
this.size = 8;
this.buckets = new Array(this.size);
this.numElements = 0;
}
hash(key) {
let hash = 0;
for (let i = 0; i < key.length; i++) {
hash += key.charCodeAt(i);
}
return hash % this.size;
}
insert(key, value) {
this.numElements++;
let index = this.hash(key);
if (!this.buckets[index]) {
this.buckets[index] = [];
}
this.buckets[index].push({ key, value });
if (this.numElements > this.size * 0.75) {
this.resize(this.size * 2);
}
}
get(key) {
let index = this.hash(key);
if (!this.buckets[index]) return null;
for (let i = 0; i < this.buckets[index].length; i++) {
if (this.buckets[index][i].key === key) {
return this.buckets[index][i].value;
}
}
return null;
}
remove(key) {
this.numElements--;
let index = this.hash(key);
if (!this.buckets[index]) return null;
for (let i = 0; i < this.buckets[index].length; i++) {
if (this.buckets[index][i].key === key) {
this.buckets[index].splice(i, 1);
if (this.numElements < this.size * 0.25) {
this.resize(this.size / 2);
}
return;
}
}
}
resize(newSize) {
let oldBuckets = this.buckets;
this.size = newSize;
this.buckets = new Array(this.size);
this.numElements = 0;
for (let i = 0; i < oldBuckets.length; i++) {
if (oldBuckets[i]) {
for (let j = 0; j < oldBuckets[i].length; j++) {
this.insert(oldBuckets[i][j].key, oldBuckets[i][j].value);
}
}
}
}
}
Implementasi bawaan tabel hash
JavaScript memiliki beberapa kelas bawaan yang menggunakan tabel hash untuk menyimpan dan mengambil data secara efisien. Beberapa contohnya meliputi:
- Peta - Kelas Peta adalah kumpulan pasangan nilai kunci yang dapat diulang sesuai urutan penambahannya. Ia menggunakan tabel hash untuk menyimpan data dan menyediakan waktu penyisipan, penghapusan, dan pencarian O(1) yang efisien.
- Set - Kelas Set adalah kumpulan nilai unik yang dapat diulang sesuai urutan penambahannya. Ia juga menggunakan tabel hash untuk menyimpan data dan menyediakan waktu penyisipan, penghapusan, dan pencarian O(1) yang efisien.
Kelas bawaan ini menyediakan cara mudah untuk menggunakan tabel hash dalam JavaScript dan bisa sangat berguna untuk menyimpan dan memanipulasi data secara efisien.
Secara keseluruhan, tabel hash adalah struktur data yang kuat dan efisien yang dapat meningkatkan kinerja banyak aplikasi secara signifikan. Jika Anda mengerjakan proyek di mana Anda perlu menyimpan dan mengambil data secara efisien, pertimbangkan untuk menggunakan tabel hash untuk membantu Anda mencapai tujuan Anda.
