Implementasi Hash Table

-

Implementasi Hash Table pada Buku Telpon

Hash Table

Hashing merupakan teknik yang digunakan untuk menyusun dan mengakses elemen data dalam List dengan waktu yang relatif konstan melalui manipulasi key untuk mengidentifikasi lokasi dalam List.

Hash function merupakan fungsi yang digunakan untuk memanipulasi key dari elemen data dalam List untuk mengidentifikasi lokasi aslinya di list. Fungsi ini akan memetakan list data yang ukurannya berubah-ubah ke ukuran tetap. Nilai kembalian dari fungsi hash disebut dengan Hash Values.

Hash table adalah sebuah struktur data yang terdiri atas sebuah tabel dan fungsi yang bertujuan untuk memetakan nilai kunci yang unik untuk setiap record menjadi angka (hash) lokasi record tersebut dalam sebuah tabel. 

Keunggulan dari struktur hash table ini adalah waktu aksesnya yang cukup cepat, jika record yang dicari langsung berada pada angka hash lokasi penyimpanannya. Akan tetapi pada kenyataannya sering sekali ditemukan hash table yang recordrecordnya mempunyai angka hash yang sama (bertabrakan).

Karena pemetaan hash function yang digunakan bukanlah pemetaan satu-satu, (antara dua record yang tidak sama dapat dibangkitkan angka hash yang sama) maka dapat terjadi bentrokan (collision) dalam penempatan suatu data record. Untuk mengatasi hal ini, maka perlu diterapkan kebijakan resolusi bentrokan (collision resolution policy) untuk menentukan lokasi record dalam tabel. Umumnya kebijakan resolusi bentrokan adalah dengan mencari lokasi tabel yang masih kosong pada lokasi setelah lokasi yang berbentrokan. 

Hash table menggunakan memori penyimpanan utama berbentuk array dengan tambahan algoritma untuk mempercepat pemrosesan data. Pada intinya hash table merupakan penyimpanan data menggunakan key value yang didapat dari nilai data itu sendiri. Dengan key value tersebut didapat hash value. Jadi hash function merupakan suatu fungsi sederhana untuk mendapatkan hash value dari key value suatu data. Yang perlu diperhatikan untuk membuat hash function adalah:

–       ukuran array/table size(m),
–       key value/nilai yang didapat dari data(k),
–       hash value/hash index/indeks yang dituju(h).

Berikut implementasi hash table
Output


Komentar

Posting Komentar

Postingan populer dari blog ini

Rekursif - Tower of Hanoi

-
Rekursi Rekursif merupakan teknik memanggil dirinya sendiri secara berulang-ulang. Biasanya rekursif ini dipakai untuk sesuatu yang membutuhkan perulangan seperti factorial. Sebenarnya teknik rekursif ini merupakan teknik yang mudah karena teknik rekursif ini seperti rumus matematika aslinya. Tower of Hano/Menara Hanoi adalah sebuah permainan matematis atau teka-teki. Permainan ini terdiri dari tiga tiang dan sejumlah cakram dengan ukuran berbeda-beda yang bisa dimasukkan ke tiang mana saja. Permainan dimulai dengan cakram-cakram yang tertumpuk rapi berurutan berdasarkan ukurannya dalam salah satu tiang, cakram terkecil diletakkan teratas, sehingga membentuk kerucut. Tujuan dari teka-teki ini adalah untuk memindahkan seluruh tumpukan ke tiang yang lain, mengikuti aturan berikut: Hanya satu cakram yang boleh dipindahkan dalam satu waktu. Setiap perpindahan berupa pengambilan cakram teratas dari satu tiang dan memasukkannya ke tiang lain, di atas cakram lain yang mungkin sudah ada di...
Baca selengkapnya

Konsep dan Pemakaian Array

-
Gambar
     Array adalah sebuah variabel yang bisa menyimpan banyak data dalam satu variabel. Array menggunakan indeks untuk memudahkan akses terhadap data yang disimpannya. Indeks array selalu dimulai dari 0. Indeks Array tidak selalu dalam bentuk angka. Bisa juga karakter atau teks. 1. Array App Output 2. Low Array Output 3. High Array Output 4. Ordered Array Output 5. Class Data Array Output
Baca selengkapnya

Implementasi Stack

-
Gambar
  Stack       Stack merupakan suatu struktur data yang berbentuk tumpukan di mana proses memasukkan dan mengeluarkan data dilakukan pada satu “pintu” yang sama. Hal ini berbeda dengan struktur data Queue/antrian yang menggunakan dua “pintu”, satu pintu untuk masuk antrian dan pintu lainnya untuk keluar dari antrian. Stack atau tumpukan biar mudah memahaminya bisa diibaratkan sebagai suatu tumpukan kardus di mana hanya data yang terletak paling atas yang bisa diambil. Data yang terletak ditengah-tengah atau pun yang berada paling bawah bisa diambil jika data yang terletak di atasnya sudah diambil terlebih dahulu. Struktur data Stack merupakan struktur data yang bersifat IFO (Last in First Out) artinya data yang masuk terakhir adalah data yang bisa keluar terlebih dahulu. Data E adalah data yang terakhir dimasukkan (method Push) oleh karenanya berada pada posisi paling atas. Jika ingin mengambil data B maka terlebih dahulu harus mengeluarkan (method Pop) berturut-...
Baca selengkapnya