1

HASHING

1. PENDAHULUAN 1.1.LATAR BELAKANG

Dalam kehidupan sehari hari pengolahan data sering kali menjadi pelit mana kala ditemukan data yang sama. Sehingga seseorang sering bingung ketika disuruh untuk

membedakan sebuah data yang diinginkan. Selain itu keamanan dan kerahasiaan data pada

jaringan computer saat ini juga menjadi isu yang sangat penting dan terus berkembang.

Berkenaan dengan hal tersebut maka diperlukan suatu fungsi hash untuk mengatasi

permasalahan. Hashing merupakan metode untuk menyimpan dan mengambil catatan dari

database. Hal ini memungkinkan kita untuk melakukan penyisipan, menghapus, dan mencari

catatan berdasarkan nilai kunci pencarian. Hashing adalah metode pencari pilihan karena

sangat efisien ketika diterapkan dengan benar. Bahkan, system hash yang diprogram dengan

benar biasanya melihat hanya satu atau dua catatan untuk setiap pencarian, insert, atau

menghapus operasi. Waktu pencarian data melalui hashing jauh lebih effisien dari pada

pencarian data biner pada array yang diurutkan dari n catatan dengan waktu O (log n), atau

pencarian data dengan binary tree yang mana memiliki waktu O(log n). Namun pada

kenyataannya hashing sulit untuk diterapkan dengan benar.

Hashing bekerja dengan melakukan perhitungan melalui sebuah key (kunci) pencarian

dengan cara mengidentifikasi posisi dalam hash table yang berisi catatan dengan key dari

data data yang ada pada database dengan inisialisasi key yaitu K. Fungsi yang melakukan perhitungan pada table hash disebut fungsi hash dan diberi lambing dengan huruf h.

Pada dasarnya sistem hashing digunkan untuk mengatur pencarian suatu posisi data dalam

table hash yang dikenal dengan slot.

1.2.RUMUSAN MASALAH

a) Pengertian hashing. b) Fungsi hashing. c) Separate chaining. d) Hash table tanpa linked list. e) Rehashing. f) Hash table di perpustakaan standar g) Extendible hashing.

1.3.TUJUAN PENULISAN

Dengan adanya makalah ini maka dapat diketahui tentang apa itu hashing yang

ternyata sangat berfungsi dalam pengolahan database. Selain itu dengan adanya makalah ini

maka dapat diketahui fungsi apa saja yang menyusun sebuah metode hashing, kendala apa

yang bisa ditemui serta penyelesaiannya dengan hashing karena dalam makalah ini terdapat

beberapa teknik yang dapat digunakan jika terjadi collision (tabrakan) atau dengan kata lain

record menghasilkan nilai hash yang sama.

2. PEMBAHASAN 2.1.PENGERTIAN HASHING

Hasing adalah teknik untuk melakukan penambahan,penghapusan,dan pencarian

dengan rata rata waktu konstan. Selain itu hashing juga dikenal dengan sebutan hash table. Hash tables adalah array dengan sel-sel yang ukurannya telah ditentukan dan dapat berisi

data atau key yang berkesesuaian dengan data. Selain itu Hash tables merupakan struktur

data yang sering digunakan untuk mengimplementasikan ADT pada sebuah Dictionary, yaitu

ADT yang hanya mengizinkan pencarian, penyisipan, dan penghapusan elemen-elemen yang

ada didalamnya.

2

Pada hakekatnya hash table merupakan solusi yang sangat effisien dalam mengatasi

masalah pencarian pada sebuah data. Hal ini dikarenakan table hash seperti halnya hash Map

menyimpan setiap pasangan kunci atau nilai dari setiap data. Jika diketahui sebah kuncinya

maka bukan hal yang mustahil lagi untuk mencari atau mengetahui nilai dari data tersebut.

Namun lain halnya jika hash table diimplementasikan pada system set data maka untuk

mencari sebuah nilai kita harus mencari kunci di dalam table hash padahal semua nilai yang

berada dalam table berisi null.

Pada berbagai macam algoritma untuk pencarian data dalam menemukan sebuah item

suatu data maka dipelukan mencari item yang tidak diinginkan juga. Begitu pula dengan

pencarian data pada sebuah list yang tidak terurut, diperlukan pengecekan isi satu persatu

item hingga item yang dicari ditemukan. Mungkin dalam pencarian data akan lebih mudah

jika pencarian pasangan nilai dengan kunci pada table hash bisa dilakukan secara langsung

tanpa harus mencari item lain yang tidak diperlukan dalam pencarian item.

Katakanlah kunci dari sebuah nilai pada table hash adalah integer dari 0 99, maka pasangan dari j=kunci tersebut bisa disimpan dalam sebuah array A yang berisi100 elemen. Sedangkan

kunci dari nilai tersebut diberi lambang sebagai N dengan kata lain dapat ditulis A[N]. kunci

N tersebut yang akan membantu pencarian data secara langsung. Namun hal ini tidak bisa

digunakan secara terus menerus, andaikata ada 4 milyar lokasi untuk menyimpan data pada sebuah array, tentunya akan menjadi suatu masalah karena dirasakan kurang effisien dan

membutuhkan banyak ruang memori untuk menyimpan data. Misal data yang dimasukkan

berupa string yang tidak diketaui berapa panjang datanya maka diperlukan pula penyimpanan

data pada ruang memori yang tak terbatas. Dapat kita simpulkan bahwa array tidak dapat

digunakan untuk menyimpan semua kunci pada hash table.

Untuk mengatasi hal tersebut di atas dalam menyimpan data pada sebuah array maka

indeks pada array tidak sama dengan kunci melainkan indeks pada array dihitung dari kunci.

Indeks array dari hasil perhitungan kunci disebut dengan kode hash. Sedangkan fungsi untuk

menghitung kode hash disebut dengan fungsi hash. Untuk mencari sebuah kunci dalam table

hash, hanya diperlukan menghitung kode hash kunci kemudian menunjuk lokasi dari kode

hash tersebut. Sebagai contoh, misal hasil penghitungan kunci dari kode hash adalah 17 maka

array yang ditunjuk dalah array dengan indeks 17.

Mungkin saja dalam suatu array ditemukan dua atau lebih kunci yang terletak pada

lokasi yang sama sehingga akan ada lebih sedikit lokasi array. Hal semacam ini disebut

dengan collision atau tabrakan data. Tabrakan data bukanlah suatu masalah , hal ini

dikarenakan mungkin saja suatu kunci memiliki kode hash yang sama dengan kode hash

kunci lain. Oleh sebab itu table hash harus bisa menangani tabrakan data tersebut dengan

baik.

Pada java , setiap lokasi pada array sebenarnya adalah suatu list berantai yang berisi

pasangan kunci atau nilai (ada kemungkinan list kosong). Jika dua item memiliki kode hash

yang sama, maka kedua item tersebut akan ada pada list yang sama. Strukturnya bisa

digambarkan sebagai berikut:

3

Gambar 1.1 struktur list item pada array

Keterangan: Pada gambar di atas, hanya ada satu item dengan kode hash 0, tidak ada item

dengan kode hash 1, dua item dengan kode hash 2, dan seterusnya. Pada tabel hash yang

dirancang dengan benar, hampir semua list berantai berisi nol atau satu elemen saja,

dengan rata-rata panjang list kurang dari 1. Meskipun kode hash dari suatu kunci mungkin

tidak membawa kita langsung pada kunci yang kita mau, akan tetapi tidak akan lebih dari

satu atau dua item yang harus kita cari sebelum kita sampai pada item yang kita inginkan.

Agar bekerja dengan benar, jumlah item dalam tabel hash harus kurang dari besarnya array.

Pada Java, ketika jumlah item melebihi 75% ukuran array, maka array tersebut akan diganti

dengan array yang lebih besar dan semua item pada array yang lama dipindahkan ke array

baru.

Pada umumnya ukuran hash table (Table Size) lebih besar dari jumlah data yang akan

disimpan. Untuk setiap key, digunakan fungsi hash untuk memetakan key pada bilangan

antara 0 sampai Tablesize-1.Untuk menambahkan data atau pencarian,ditentukan key dari

data tersebut dan digunakan sebuah fungsi hash untuk memetakan elemen pada indeks dari

hash table.

2.2.HASH FUNCTION

Merupakan fungsi yang menerima masukan string yang panjangnya sembarang, lalu

mentransformasikannya menjadi string keluaran yang panjangnya tetap (fixed) (umumnya

berukuran jauh lebih kecil daripada ukuran string semula). Fungsi hash sering juga disebut

fungsi enkripsi satu arah, atau disebut juga message diggest. Fungsi hash digunakan untuk

menjamin servis otentikasi dan integritas suatu pesan atau file. Suatu fungsi hash (h)

memetakan bit-bit string dengan panjang sembarang ke sebuah string dengan panjang tertentu

misal n. Dengan domain D dan range R maka proses hashing merupakan proses pemetaan

suatu input string menjadi output. Output dari fungsi hash disebut nilai hash atau hasil hash.

Fungsi hash satu arah adalah sebuah fungsi hash yang berjalan hanya satu arah

sehingga mudah untuk menghitung nilai hash dari pre-image, tetapi sangat sulit untuk

membangkitkan pre-image dari nilai hash-nya.

Fungsi hash satu arah tersebut dibuat berdasarkan ide tentang fungsi pemampatan.

Fungsi hash adalah sebuah fungsi atau persamaan matematika yang mengambil input dengan

panjang variabel (preimage) dan merubahnya menjadi panjang yang tetap (biasanya lebih

pendek), keluarannya biasa disebut nilai hash.

Persamaan fungsi hash:

4

h = H(M)

M = pesan kuran sembarang

h = nilai hash (hash value) atau pesan-ringkas (messagedigest)

h

5

Struktur data lain dapat digunakan sebagai pengganti senarai berkait. Misalnya

dengan binary tree, kompleksitas terburuk bisa diturunkan menjadi O(log n) dari yang

sebelumnya O(n). Namun demikian , karena setiap senarai diharapkan untuk tidak panjang h,

struktur data binary tree kurang effisien kecuali table hash tersebut memang didesain untuk

jumlah record yang banyak atau kemungkinan terjadi bentrokan sangat besar yang mungkin

terjadi karena masukan memang disengaja agar terjadi bentrokan.

Gambar 1.3 contoh separate chaining

Collisions

Merupakan tabrakan data dimana jika didalam suatu data diisi sebuah data yang sama karena

fungsi hash bukan merupakan fungsi satu ke satu. Dengan fungsi hash yang baik, hal seperti

ini akan sangat jarang terjadi, tapi pasti akan terjadi. Jika hal seperti ini terjadi, record-record

tersebut tidak bisa menempati lokasi yang sama. Sebagai ilustrasi , misal dalam suatu data

terdapat seseorang bernama NED dengan table hash dari fungsi hash berrindeks N = 19, E =

5, dan D = 4 adalah 19+5+4 = indeks 28. Kemudian kita masukkan nama Fred yang memiliki

indeks sama yaitu 28. Hal inilah yang akan mengakibatkan suatu tabrakan data atau

collisions.

2.4.HASH TABEL WITHOUT LINKED LIST

Berbeda dengan separate chaining, pada hash table tanpa linked list data disimpan di

dalam hash table tersebut. Bukan senarai berkait yang bisa bertambah secara terus menerus.

Dengan demikian data yang disimpan tidak mungkin bisa lebih banyak dari banyak ruang

yang ada pada table hash.

Jika suatu record akan dimasukkan ke dalam table hash pada lokasi sesuai nilai hash

nya dan tenyata lokasi tersebut sudah diisi dengan record lain maka harus dicari lokasi

alternative yang masih belum terisi dengan cara tertentu. Cara ini disebut dengan open

addressing. Ada beberapa metode untuk menemukan lokasi baru yang masih kosong. Dalam

proses menemukan lokasi baru ini harus menggunakan pola tertentu agar record yang

disimpan tetap bisa dicari dengan mudah saat dibutuhkan kemudian. Metode metode yang sering digunakan adalah :

1. Linear Probing

6

Dengan menambahkan suatu interval pada hasil yang diperoleh dari fungsi hash

sampai ditemukan lokasi yang belum terisi. Interval yang biasa digunakan adalah 1. Ilustrasi

Resolusi bentrokan dengan Linear Probing:

Gambar 1.4 Metode Linear Probing

2. Kuadrat Probing Disebut juga dengan Squared Probing. Hampir sama dengan linear probing, hanya

saja pada quadratic probing hasil yang diperoleh dari fungsi hash ditambahkan dengan

kuadrat dari interval yang digunakan.

3. Double hashing Pada method double hashing, jika lokasi yang diperoleh dengan fungsi hash sudah

terisi, maka dilakukan proses hash lagi sampai ditemukan lokasi yang belum terisi.

2.5. REHASHING

Jika table sudah terlalu penuh, maka waktu yang dibutuhkan untuk memproses dan

mengoperasikan data akan menjadi terlalu lama. Penempatan data mungkin gagal untuk

membuka alamat hashing dengan resolusi kuadrat. Masalah ini dapat terjadi jika kepindahan

data terlalu banyak yang bercampur dengan penyisipan data.

Solusi untuk masalah ini adalah dengan membuat table lain yang memiliki ukuran

sekitar dua kali lebih besar dari table hash sebelumnya dan dengan fungsi hash sama.

Kemudian menye-can data table hash lama, menghitung nilai hash yang baru untuk setiap

elemen yang tidak dihapus kemudian memasukkannya ke dalam table hash yang baru.

Rehashing merupakan operasi yang memakan banyak waktu, yaitu O(N). hal ini

dikarenakan terdapat N elemen yang harus di-rehash dan ukuran table sekitar 2N. Jika

hashing dilakukan sebagai bagian dari system interaktif, maka operasi ini tidak akan

menguntungkan karena akan memperlambat eksekusi program. Meskipun demikian, operasi

rehashing sangat jarang terjadi sehingga tidak perlu terlalu dirisaukan.

Rehashing menyerupai separate chaining hash table. Hal ini terbukti dari rehashing

sederhana yang menyediakan implementasi dari separate chaining hash table.

2.6. HASH TABLE PADA PERPUSTAKAAN STANDAR

Perpustakaan Standar mencakup implementasi dari Set dan Map, dengan nama

HashSet dan HashMap. HashSet dan HashMap diimplementasikan dengan menggunakan

separate chaining hash table. Item dalam HashSet (atau tombol di HashMap) harus

menyediakan metode kode hash. Dalam hal ini terdapat 3 peta, yaitu:

7

1) Sebuah peta dimana kuncinya adalah panjang kata, dan nilainya adalah semua kata-kata yang menyusun panjang kata.

2) Sebuah peta dimana kuncinya adalah perwakilan, dan nilai adalah koleksi semua kata dengan perwakilan itu.

3) Sebuah peta dimana kuncinya adalah kata, dan nilai adalah koleksi semua kata-kata yang berbeda hanya dalam satu karakter dari kata itu.

Karena urutan dari panjang kata yang diproses tidak bermasalah maka peta pertama

bisa menjadi HashMap. Karena perwakilan tidak diperlukan setelah peta kedua dibangun,

maka peta kedua bisa manjadi HashMap. Peta ketiga juga bisa menjadi HashMap, kecuali

kita ingin printHighChangeables untuk abjad daftar subset dari kata-kata yang dapat diubah

menjadi sejumlah besar kata lainnya.

Kinerja HashMap cenderung lebih unggul dari TreeMap, namun sulit untuk

mengetahui pasti tanpa menulis kode dua arah. Baik HashMap maupun TreeMap sama-sama

baik untuk mendeklarasikan variable menggunakan interface type Map yang kemudian

mengubah instansiasi dari TreeMap ke HashMap lalu melakukan tes waktu.

Di java, jenis perpustakaan yang patut dimasukkan ke HashSet atau sebagai kunci ke dalam

HashMap adalah sama, dan kode hash didefinisikan.

2.7.EXTENDIBLE HASHING

Extendible hashing berkaitan dengan kasus dimana jumlah data terlalu besar untuk

cocok di memori utama. Pertimbangan utama adalah jumlah akses disk yang dibutuhkan

untuk mengambil data.

Semisal kita asumsikan bahwa pada titik tertentu kita memiliki N catatan untuk

menyimpan nilai N dari waktu ke waktu. Jika hashing probing atau hashing chaining separate

yang digunakan bermasalah, maka akan terjadi tabrakan yang dapat menyebabkan beberapa

blok diperiksa selama pencarian, bahkan untuk didistribusikan pada hash table. Sehingga

memperpanjang waktu pencarian.

3. PENUTUP 3.1.KESIMPULAN

Hasing adalah teknik untuk melakukan penambahan,penghapusan,dan pencarian dengan rata

rata waktu konstan. Selain itu hashing juga dikenal dengan sebutan hash table. Hash tables adalah array dengan sel-sel yang ukurannya telah ditentukan dan dapat berisi data atau key

yang berkesesuaian dengan data. Pada hakekatnya hash table merupakan solusi yang sangat

effisien dalam mengatasi masalah pencarian pada sebuah data. Hal ini dikarenakan table hash

seperti halnya hash Map menyimpan setiap pasangan kunci atau nilai dari setiap data. Array

tidak dapat digunakan untuk menyimpan semua kunci pada hash table sehingga untuk

mengatasi hal tersebut dalam menyimpan data pada sebuah array maka indeks pada array

tidak sama dengan kunci melainkan indeks pada array dihitung dari kunci. Indeks array dari

hasil perhitungan kunci disebut dengan kode hash. Sedangkan fungsi untuk menghitung kode

hash disebut dengan fungsi hash. Fungsi hash merupakan fungsi yang menerima masukan

string yang panjangnya sembarang, lalu mentransformasikannya menjadi string keluaran

yang panjangnya tetap (fixed) (umumnya berukuran jauh lebih kecil daripada ukuran string

semula).

Separate chaining merupakan salah satu teknik untuk menyelesaikan permasalahan

ketika terjadi collision dalam memori pada table. Collision merupakan tabrakan data dimana

jika didalam suatu data diisi sebuah data yang sama karena fungsi hash bukan merupakan

fungsi satu ke satu. Dengan fungsi hash yang baik, hal seperti ini akan sangat jarang terjadi,

tapi pasti akan terjadi. Berbeda dengan separate chaining, pada hash table tanpa linked list

data disimpan di dalam hash table tersebut. Dalam proses menemukan lokasi baru ini harus

8

menggunakan pola tertentu agar record yang disimpan tetap bisa dicari dengan mudah saat

dibutuhkan kemudian. Metode metode yang sering digunakan adalah : 1. Linear Probing 2. Kuadrat Probing 3. Double hashing

Terdapat pula rehashing yang merupakan metode untuk mengatasi masalah dalam

pengolahan data dengan cara memindahkan data dari hash table lama ke hash table yang

baru. Hash table sering digunakan untuk mengimplementasikan cache, baik dalam perangkat

lunak (misalnya cache pada browser internet kita) dan perangkat keras (misalnya, memori

cache komputer modern). Hash table juga digunakan dalam implementasi hardware dari

router. Secara garis besar fungsi hash paling banyak digunakan dalam keamanan jaringan

computer dan internet.

3.2.SARAN

Makalah ini sangat jauh dari kesempurnaan, maka dari itu kelompok kami sangat

mengharapkan kritik dan saran untuk makalah ini yang tentunya sangat bermanfaat bagi

penulis dalam menyempurnakan makalah ini. Semoga makalah ini bias menjadi salah satu

acuan dalam pembuatan makalah selanjutnya.

9

DAFTAR PUSTAKA

Aprizal, Aries. 2009. Keamanan Komputer .

http://unila.academia.edu/ariesaprizal/Papers/1589275/Keamanan_Komputer diakses tanggal

23 Mei 2012.

Anonim. 2008. Virtual Consulting Knowledge Educational. http://www.ilmukomputer.com/

diakses tanggal 20 Mei 2012.

Pratama,Junaedi.2009. Makalah Keamanan Komputer.

http://www.informatika.org~rinaldiMatdis2007-2008MakalahMakalahIF2153-0708-061.pdf diakses

tanggal 20 Mei 2012.

Agus. 2008. Java Enkripsi. http://www.om4gus.blogspot.com/2008/02/java-enkripsi-

md5.html diakses tanggal 21 Mei 2012

Anonim. 2008. Kamus Internet Detail.

http://www.telkom.net/kamus_internet_detail.php?cid=2&id=431 diakses tanggal 21 Mei

2012.