Rangkuman Hashing

_Hashing_
by : BINUSIAN

• Binary search dan interpolation search memberikan hasil pencarian dalam waktu yang cukup singkat. Kedua algoritma pencarian ini mengharuskan data (record) telah diurutkan, sehingga cukup lama.

• Hashing bertujuan untuk mendapatkan posisi (lokasi, alamat) record secara langsung (immediate, direct) pada waktu dicari.


• Struktur data penyimpan record disebut hash table. Fungsi untuk menentukan posisi record berdasarkan nilai kunci record disebut hashing function.
posisi = hash (kunci)

• Suatu hashing function yang baik harus memenuhi dua syarat:
1. penghitungannya cepat
2. menghasilkan nilai yang terdistribusi merata

Beberapa pendekatan hash function:

1. Digit selection.
Hash function ini menentukan nilai hash dengan memilih beberapa angka dari nilai kunci. Misalnya nilai kunci berupa sembilan angka dan jumlah data tidak lebih dari 1000 maka nila hash dapat diambil dari antara angka tersebut misalnya d7d8d9.

key = d1d2d3d4d5d6d7d8d9
H(key) = key mod 1000

2. Division.
Hash function ini menentukan nilai hash dengan
membangi nilai kunci dengan nilai tertentu.

H(key) = key mod m = h sehingga 0 £ h £ m-1

Penentuan nilai m cukup penting, harus dicari sedekimian rupa sehingga hasil bagi cukup terdistribusi.

3. Multiplication.
Perkalian dilakukan dengan bilangan itu sendiri. Karena hasil perkalian membentuk angka yang cukup besar maka lakukan seleksi angka. Misalkan kunci terdiri dari lima angka, hasil perkaliannya membentuk 10 angka.

key = d1d2d3d4d5
d1d2d3d4d5 x d1d2d3d4d5 = r1r2r3r4r5r6r7r8r9r10

• Perfect hashing function adalah fungsi hash yang menjamin semua nilai hasil penghitungan bersifat unik (tidak timbul collision). Fungsi ini mensyaratkan semua nilai kunci sudah harus diketahui sejak semula. Salah satunya diusulkan Cichelli untuk mengolah reserved word bahasa Pascal yang jumlahnya 36 buah. Hash function yang digunakan adalah

H(key) = L + g(key[1]) + g(key[L])
dengan L adalah panjang kunci

_Linear Probing_
• Function linearprobe( ) mengadakan penelusuran secara linier. Bila penelusuran telah mencapai posisi terakhir maka pindah ke posisi pertama (% M).
• Pada linear probing semua nilai kunci yang di-hash ke lokasi yang sama akan menjalani proses penelu-suran lokasi yang sama sampai ditemukan lokasi kosong, ini disebut primary clustering. Nilai kunci yang berbeda, misalnya 27 akan di-hash ke lokasi 4 yang telah ditempati.

int linearprobe(tHashtbl ht, int addr, int M)
{
while((ht.tabel[++addr].kode % M) != -1);
return addr;
}

int buildhashtable(tHashtbl *ht, tHashrec a, int M)
{
int addr = hash(a.kode, M);
if((*ht).tabel[addr].kode == a.kode) return 0;
if((*ht).tabel[addr].kode != -1)
addr = linearprobe(*ht, addr, M);
(*ht).tabel[addr].kode = a.kode;
strcpy((*ht).tabel[addr].nama, a.nama);
strcpy((*ht).tabel[addr].kontrib, a.kontrib);
return 1;
}

int search(tHashtbl ht, tHashrec *rec, int M, int key)
{
int addr = hash(key, M);
if (ht.tabel[addr].kode == -1) return -1;
while (ht.tabel[addr].kode != key) addr= (addr + 1) % M;
(*rec).kode = ht.tabel[addr].kode;
strcpy((*rec).nama, ht.tabel[addr].nama);
strcpy((*rec).kontrib, ht.tabel[addr].kontrib);
return 1;
}

_Double Hashing_
• Double hashing bertujuan untuk mengatasi primary clustering, terhadap nilai hash yang berbeda mestinya dilakukan pencarian lokasi kosong dengan pergeseran yang berbeda. Metode ini menggunakan hash function kedua bila terjadi collision. Hash function kedua ini melibatkan nilai kunci, digunakan untuk mendapatkan jarak loncatan, tidak seperti linier probing yang loncat ke posisi berikutnya.
Misalkan hash function kedua adalah 8 – (key %8).
Terhadap data “26, James Gray, DB & trans processing “, dihitung
hash2 (26) = 8 – (26 % 8) = 6.
hash1(26) = 26 % 23 = 3; posisi 3 telah terisi maka lanjutkan perhitungan: (3 + 6) % 23 = 9 , posisi telah ditemukan
• Contoh lain misalnya akan ditambahkan data “54, Manuel Blum, Computational complexity”, dihitung
hash2(54) = 8- (54 % 8) = 2
hash1(54) = 54 % 23 = 8 ; posisi 8 telah terisi maka lanjutkan perhitungan: (8 + 2) % 23 = 10 , posisi telah terisi
(10+2) % 23 = 12, posisi telah terisi
(12+2) % 23 = 14, posisi ditemukan











Semula Menjadi
Kode Nama Kode Nama
[0] 46 John McCarthy … 46 John McCarthy …
[1]
[2] 25 Donald E. Knuth … 25 Donald E. Knuth …
[3] 49 C.A.R. Hoare … 49 C.A.R. Hoare …
[4] 50 Raj Reddy … 50 Raj Reddy …
[5] 5 John Hopcroft … 5 John Hopcroft …
[6]
[7] 30 Dennis M. Ritchie … 30 Dennis M. Ritchie …
[8] 8 Marvin Minsky … 8 Marvin Minsky …
[9] 26 James Gray …
[10] 33 Niklaus Wirth … 33 Niklaus Wirth …
[11]
[12] 35 E.W. Dijkstra … 35 E.W. Dijkstra …
[13]
[14] 54 Manuel Blum …

int hash2(int n)
{
return (8 - (n % 8));
}
int doublehash(tHashtbl ht, int addr, int u, int M)
{
while((ht.tabel[addr+=u].kode % M) != -1);
return addr;
}
int buildhashtable(tHashtbl *ht, tHashrec a, int M)
{
int addr = hash(a.kode, M), step;
if ((*ht).tabel[addr].kode == a.kode) return 0;
if ((*ht).tabel[addr].kode != -1) {
step = hash2(a.kode);
addr = doublehash(*ht, addr, step, M);
}

(*ht).tabel[addr].kode = a.kode;
strcpy((*ht).tabel[addr].nama, a.nama);
strcpy((*ht).tabel[addr].kontrib, a.kontrib);
return 1;
}
int search(tHashtbl ht, tHashrec *rec, int M, int key)
{
int addr = hash(key, M);
int step = hash2(key);
if (ht.tabel[addr].kode == -1) return -1;
while (ht.tabel[addr].kode != key) addr= (addr+step ) % M;
(*rec).kode = ht.tabel[addr].kode;
strcpy((*rec).nama, ht.tabel[addr].nama);
strcpy((*rec).kontrib, ht.tabel[addr].kontrib);
return 1;
}

_Separate Chaining_
• Pada separate chaining data ditampung dalam array of pointer. Masng-masing pointer akan menunjuk ke
• linked list sehingga tidak akan menimbulkan collision. Kunci yang memiliki nilai hashing yang sama disimpan pada satu linked link yang sama.

# include
# include
# include
# include
struct thashrec {
int kode;
char nama[21];
char kontrib [41];
} ;
typedef struct thashrec tHashrec;
struct thashlink {
tHashrec data;
struct thashlink *next;
} ;
typedef struct thashlink tHashlink;
struct thashtbl {
tHashlink * tabel[23];
} ;
typedef struct thashtbl tHashtbl;
void inithashtable(tHashtbl *ht, int M)
{
for (int i = 0; i < M; i++) (*ht).tabel[i] = NULL;
}
int hash(int n, int M)
{
return (n % M);
}

void buildhashtable(tHashtbl *ht, tHashrec a, int M)
{
int addr = hash(a.kode, M);
tHashlink *node, *curr;
node = (tHashlink *) malloc (sizeof(tHashlink));
node->data.kode = a.kode;
strcpy(node->data.nama, a.nama);
strcpy(node->data.kontrib, a.kontrib);
node->next= NULL;
curr = (*ht).tabel[addr];
if (curr == NULL) (*ht).tabel[addr] = node;
else {
while(curr->next!= NULL) curr= curr-> next;
curr->next= node;
}
}

int search(tHashtbl ht, tHashrec *a, int kunci, int M)
{
int addr = hash(kunci, M);
tHashlink *curr;
if (ht.tabel[addr] == NULL) return 0;
curr = ht.tabel[addr];
while (curr != NULL) {
if (curr->data.kode == kunci) {
(*a).kode= curr->data.kode;
strcpy((*a).nama, curr->data.nama);
strcpy((*a).kontrib, curr->data.kontrib);
return 1;
}
curr = curr->next;
}
return 1;
}

• Pada modul inithashtable()parameter foraml berupa array of linked-list yang berfungsi sebagai hash table. Seluruh elemen array diberi nilai awal NULL.

• Hash table dikirim ke modul buildhashtable( ) untuk ditambahkan satu simpul. Data yang akan ditambahkan berada pada record a. Fungsi hash() menghitung posisi addr berdasarkan nilai field kode pada record a. Satu simpul baru dibentuk dan diacu oleh node. Data baru disalin ke node dan selanjutnya node dikaitkan pada hash table posisi addr. Untuk mengaitkan node ke hash table posisi addr maka perlu memeriksa keberadaan linked list pada posisi ini, apakah sudah terbentuk atau belum.