Hash Table
Terakhir diperbarui
Hash table adalah struktur data yang menyimpan item dalam array berisi bucket. Untuk menempatkan atau mencari sebuah key, hash table memasukkan key itu ke fungsi hash lalu mengambil sisa bagi hasilnya dengan jumlah bucket, dan hasil itulah indeks bucket-nya, didapat dalam O(1). Tekan Putar di atas untuk melihat setiap key di-hash ke sebuah bucket dan disimpan, lalu sebuah pencarian langsung melompat ke bucket yang tepat.
Saat dua key di-hash ke bucket yang sama, yang disebut tabrakan (collision), visualisasi ini memakai separate chaining: setiap bucket menyimpan list kecil, dan key yang bertabrakan ditambahkan ke list itu. Selama tabelnya tidak terlalu penuh (load factor rendah) dan fungsi hash menyebarkan key dengan baik, rantainya tetap pendek dan penyisipan, pencarian, serta penghapusan bernilai O(1) secara rata-rata.
Kompleksitas waktu
| Operasi | Rata-rata | Kasus terburuk |
|---|---|---|
| Penyisipan | O(1) | O(n) (semua key bertabrakan) |
| Pencarian | O(1) | O(n) |
| Penghapusan | O(1) | O(n) |
| Ruang | O(n) | O(n) |
Konsep kunci
| Istilah | Arti |
|---|---|
| Fungsi hash | Memetakan key ke indeks bucket |
| Tabrakan (collision) | Dua key jatuh di bucket yang sama |
| Separate chaining | Setiap bucket menyimpan list berisi entri yang bertabrakan |
| Open addressing | Alternatifnya: cari slot kosong berikutnya |
| Load factor | entri / bucket, penentu kapan resize terjadi |
Contoh penerapan
Menyisipkan key 20, 34, 9, 13 ke tabel dengan 7 bucket, memakai hash(k) = k % 7:
| Langkah | Struktur | Aksi |
|---|---|---|
Sisipkan 20 | bucket 6: [20] | 20 % 7 = 6, bucket 6 kosong, simpan 20 |
Sisipkan 34 | bucket 6: [20, 34] | 34 % 7 = 6, bertabrakan dengan 20, tambahkan 34 ke rantai |
Sisipkan 9 | bucket 2: [9] | 9 % 7 = 2, bucket 2 kosong, simpan 9 |
Sisipkan 13 | bucket 6: [20, 34, 13] | 13 % 7 = 6, tabrakan, tambahkan 13 ke rantai bucket 6 |
Cari 34 | bucket 6: [20, 34, 13] | 34 % 7 = 6, pindai rantai: 20 bukan, 34 cocok, ditemukan |
Kapan memakai hash table
| Pakai saat | Hindari saat |
|---|---|
Kamu butuh penyisipan, pencarian, dan penghapusan rata-rata O(1) berdasarkan key | Kamu butuh key yang tetap terurut: pakai BST yang seimbang |
| Key tidak punya urutan yang berguna dan kamu hanya menguji keanggotaan dengan pencocokan persis | Kamu butuh range query atau pencarian key terdekat |
| Kamu sanggup memakai sedikit memori tambahan untuk bucket dan load factor yang rendah | Memori sangat terbatas dan setiap byte berarti |
| Ada fungsi hash yang bagus untuk tipe key-mu | Latensi kasus terburuk harus dibatasi: tabrakan membuatnya O(n) |
Kode Hash Table
Implementasi Hash Table yang rapi dan siap dijalankan dalam Python, JavaScript, Java, C++, C. Pilih bahasa, salin kodenya, atau buka langsung di Coddy Playground.
Kode Hash Table dalam Python
Python
1class HashTable:2 def __init__(self, size=8):3 self.size = size4 self.buckets = [[] for _ in range(size)]5
6 def _index(self, key):7 # Hash the key to a bucket; different keys can collide8 return sum(ord(ch) for ch in key) % self.size9
10 def set(self, key, value):11 bucket = self.buckets[self._index(key)]12 for i, (k, _) in enumerate(bucket):13 if k == key:14 bucket[i] = (key, value) # update existing key15 return16 bucket.append((key, value)) # chain on collision17
18 def get(self, key):19 for k, v in self.buckets[self._index(key)]:20 if k == key:21 return v22 raise KeyError(key)23
24 def delete(self, key):25 bucket = self.buckets[self._index(key)]26 for i, (k, _) in enumerate(bucket):27 if k == key:28 del bucket[i]29 return30 raise KeyError(key)31
32
33table = HashTable()34table.set("apple", 3)35table.set("banana", 7)36table.set("cherry", 5)37
38print("apple ->", table.get("apple"))39print("banana ->", table.get("banana"))40table.set("apple", 10)41print("apple ->", table.get("apple"))42table.delete("banana")43print("bucket sizes:", [len(b) for b in table.buckets])Kode Hash Table dalam JavaScript
JavaScript
1class HashTable {2 constructor(size = 8) {3 this.size = size;4 this.buckets = Array.from({ length: size }, () => []);5 }6
7 // Fold character codes into a bucket index8 hash(key) {9 let h = 0;10 for (const ch of key) h = (h * 31 + ch.charCodeAt(0)) % this.size;11 return h;12 }13
14 set(key, value) {15 const bucket = this.buckets[this.hash(key)];16 const pair = bucket.find(([k]) => k === key);17 if (pair) pair[1] = value;18 else bucket.push([key, value]); // Separate chaining on collision19 }20
21 get(key) {22 const bucket = this.buckets[this.hash(key)];23 const pair = bucket.find(([k]) => k === key);24 return pair ? pair[1] : undefined;25 }26
27 delete(key) {28 const bucket = this.buckets[this.hash(key)];29 const index = bucket.findIndex(([k]) => k === key);30 if (index === -1) return false;31 bucket.splice(index, 1);32 return true;33 }34}35
36const table = new HashTable();37table.set("apple", 3);38table.set("banana", 7);39table.set("cherry", 5);40table.set("apple", 4);41console.log("apple ->", table.get("apple"));42console.log("banana in bucket", table.hash("banana"));43table.delete("cherry");44console.log("cherry after delete:", table.get("cherry"));Kode Hash Table dalam Java
Java
1public class Main {2 static class Entry {3 String key; int value;4 Entry next; // chain for keys sharing a bucket5 Entry(String key, int value) { this.key = key; this.value = value; }6 }7
8 static final int CAPACITY = 8;9 static Entry[] buckets = new Entry[CAPACITY];10
11 static int index(String key) { return Math.abs(key.hashCode()) % CAPACITY; }12
13 static void put(String key, int value) {14 int i = index(key);15 for (Entry e = buckets[i]; e != null; e = e.next) {16 if (e.key.equals(key)) { e.value = value; return; }17 }18 Entry entry = new Entry(key, value);19 entry.next = buckets[i]; // prepend to the chain20 buckets[i] = entry;21 }22
23 static Integer get(String key) {24 for (Entry e = buckets[index(key)]; e != null; e = e.next) {25 if (e.key.equals(key)) return e.value;26 }27 return null;28 }29
30 static void remove(String key) {31 int i = index(key);32 Entry prev = null;33 for (Entry e = buckets[i]; e != null; prev = e, e = e.next) {34 if (e.key.equals(key)) {35 if (prev == null) buckets[i] = e.next;36 else prev.next = e.next;37 return;38 }39 }40 }41
42 public static void main(String[] args) {43 put("apple", 3); put("banana", 7); put("cherry", 5);44 System.out.println("apple -> " + get("apple"));45 put("apple", 10); // update in place46 System.out.println("apple -> " + get("apple"));47 remove("banana");48 System.out.println("banana -> " + get("banana"));49 }50}Kode Hash Table dalam C++
C++
1#include <iostream>2#include <string>3#include <vector>4
5struct HashTable {6 static constexpr int CAPACITY = 8;7 // Separate chaining: each bucket holds (key, value) pairs8 std::vector<std::vector<std::pair<std::string, int>>> buckets{CAPACITY};9
10 size_t hash(const std::string& key) const {11 size_t h = 0;12 for (char c : key) h = h * 31 + static_cast<unsigned char>(c);13 return h % CAPACITY;14 }15
16 void set(const std::string& key, int value) {17 auto& bucket = buckets[hash(key)];18 for (auto& entry : bucket) {19 if (entry.first == key) {20 entry.second = value; // update existing key21 return;22 }23 }24 bucket.push_back({key, value});25 }26
27 const int* get(const std::string& key) const {28 for (const auto& entry : buckets[hash(key)]) {29 if (entry.first == key) return &entry.second;30 }31 return nullptr;32 }33
34 void erase(const std::string& key) {35 auto& bucket = buckets[hash(key)];36 for (size_t i = 0; i < bucket.size(); ++i) {37 if (bucket[i].first == key) {38 bucket.erase(bucket.begin() + i);39 return;40 }41 }42 }43};44
45int main() {46 HashTable table;47 table.set("apple", 3);48 table.set("banana", 7);49 table.set("apple", 4); // overwrites the old value50 for (const std::string& key : {"apple", "banana", "grape"}) {51 const int* value = table.get(key);52 if (value != nullptr) std::cout << key << " = " << *value << "\n";53 else std::cout << key << " not found\n";54 }55 table.erase("banana");56 std::cout << "banana after erase: "57 << (table.get("banana") ? "found" : "not found") << "\n";58 return 0;59}Kode Hash Table dalam C
C
1#include <stdio.h>2#include <stdlib.h>3#include <string.h>4
5#define CAPACITY 86
7// Separate chaining: each bucket is a linked list of entries8typedef struct Entry {9 char key[16];10 int value;11 struct Entry* next;12} Entry;13
14Entry* buckets[CAPACITY];15
16unsigned int hash(const char* key) {17 unsigned int h = 5381; // djb2, then modulo the bucket count18 for (; *key; key++) h = h * 33 + (unsigned char)*key;19 return h % CAPACITY;20}21
22void set(const char* key, int value) {23 unsigned int i = hash(key);24 for (Entry* e = buckets[i]; e != NULL; e = e->next) {25 if (strcmp(e->key, key) == 0) {26 e->value = value; // update existing key27 return;28 }29 }30 Entry* e = malloc(sizeof(Entry));31 strcpy(e->key, key);32 e->value = value;33 e->next = buckets[i];34 buckets[i] = e;35}36
37int* get(const char* key) {38 for (Entry* e = buckets[hash(key)]; e != NULL; e = e->next) {39 if (strcmp(e->key, key) == 0) return &e->value;40 }41 return NULL;42}43
44void removeKey(const char* key) {45 Entry** link = &buckets[hash(key)];46 while (*link != NULL) {47 if (strcmp((*link)->key, key) == 0) {48 Entry* old = *link;49 *link = old->next;50 free(old);51 return;52 }53 link = &(*link)->next;54 }55}56
57void printBuckets(void) {58 for (int i = 0; i < CAPACITY; i++) {59 printf("bucket %d:", i);60 for (Entry* e = buckets[i]; e != NULL; e = e->next) {61 printf(" (%s=%d)", e->key, e->value);62 }63 printf("\n");64 }65}66
67int main(void) {68 set("apple", 3);69 set("banana", 7);70 set("apple", 4); // overwrites the old value71 set("grape", 9);72 printBuckets();73 int* value = get("apple");74 printf("get(apple): %d\n", value ? *value : -1);75 removeKey("banana");76 printf("banana after remove: %s\n", get("banana") ? "found" : "not found");77 return 0;78}FAQ Hash Table
Apa itu hash collision dan bagaimana cara menyelesaikannya?
Tabrakan (collision) terjadi saat dua key yang berbeda di-hash ke bucket yang sama. Dua solusi yang umum adalah separate chaining (setiap bucket menyimpan list, dan key yang bertabrakan ditambahkan ke sana, seperti yang ditampilkan di sini) dan open addressing (mencari slot kosong berikutnya di dalam array). Keduanya menjaga pencarian tetap benar; perbedaannya ada pada tata letak memori dan performa saat tabel penuh.
Berapa kompleksitas waktu hash table?
Penyisipan, pencarian, dan penghapusan bernilai
O(1) secara rata-rata jika fungsi hash menyebarkan key secara merata dan load factor dijaga tetap rendah. Pada kasus terburuk, yaitu ketika setiap key bertabrakan di satu bucket, semuanya merosot menjadi O(n), itulah sebabnya fungsi hash yang bagus dan resize itu penting.Apa itu load factor?
Load factor adalah jumlah entri yang disimpan dibagi jumlah bucket. Saat nilainya bertambah, rantai makin panjang dan operasi melambat, jadi sebagian besar hash table melakukan resize (hash ulang ke array yang lebih besar) begitu nilainya melewati ambang seperti 0,75.
Kapan sebaiknya memakai hash table, bukan binary search tree?
Pakai hash table saat kamu hanya butuh pencarian dengan pencocokan persis dan ingin kecepatan rata-rata
O(1) tanpa kebutuhan urutan. Pakai binary search tree yang seimbang saat kamu butuh key yang terurut, range query, atau pencarian predecessor/successor, yang tidak bisa dilakukan hash table secara efisien. BST memberi jaminan operasi O(log n), sedangkan hash table menukar jaminan itu dengan performa rata-rata yang lebih cepat.Apa perbedaan separate chaining dan open addressing?
Separate chaining menyimpan key yang bertabrakan dalam list per bucket, jadi satu bucket bisa menampung banyak entri dan tabel tidak pernah benar-benar penuh. Open addressing menyimpan semuanya di dalam array itu sendiri dan mencari slot kosong berikutnya saat terjadi tabrakan. Cara ini ramah cache, tetapi performanya turun tajam saat load factor mendekati 1 dan butuh penanganan penghapusan yang hati-hati. Chaining tahan terhadap load factor yang lebih tinggi; open addressing memakai memori dengan lebih ringkas.
Mengapa hash table tidak bisa diandalkan untuk menjaga key tetap sesuai urutan penyisipan atau terurut?
Fungsi hash sengaja menyebarkan key ke berbagai bucket untuk menghindari penumpukan, jadi urutan iterasi mencerminkan tata letak bucket, bukan urutan penyisipan atau urutan terurut. Jika kamu butuh urutan, pakai map/tree yang berurutan atau struktur seperti map yang mempertahankan urutan penyisipan (misalnya
dict di Python mempertahankan urutan penyisipan, tetapi itu jaminan dari bahasanya, bukan sifat bawaan hash table). Jangan pernah berasumsi urutan iterasi sama dengan urutan kamu menyisipkan key, kecuali bahasanya menjanjikannya secara eksplisit.Sumber terkait
Visualisasi lainnya
