TUGAS 7
SISTEM BERKAS
Dosen
Pengampu : Edhy Sutanta ST.M.Kom
Disusun
Oleh:
NAMA : EKA YANI
NIM : 131.05.1092
JURUSAN
TEKNIK INFORMATIKA
FAKULTAS
TEKNOLOGI INDUSTRI
INSTITUT
SAINS & TEKNOLOGI AKPRIND YOGYAKARTA
2016
KATA PENGANTAR
Segala puji
hanya milik Allah SWT, Shalawat dan
salam selalu tercurahkan kepada Rasulullah SAW. Berkat limpahan dan
rahmat-NyA penyusun mampu menyelesaikan tugas 7
ini guna memenuhi tugas mata kuliah Sistem Berkas. Dalam penyusunan tugas atau
materi ini, tidak sedikit hambatan yang penulis hadapi. Namun penulis menyadari
bahwa kelancaran dalam penyusunan tugas ini tidak lain berkat
bantuan, dorongan dan bimbingan dosen serta teman-teman yang mendukung laporan
ini, sehingga kendala-kendala yang
penulis hadapi teratasi. Laporan ini disusun agar pembaca dapat memperluas ilmu
tentang bagaimana Mahasiswa mampu memberikan ulasan
terkait organisasi berkas tentang perhitungan dengan menggunakan metode hashing.
Tugas ini di susun oleh
penyusun dengan berbagai rintangan. Baik itu yang datang dari diri penyusun maupun
yang datang dari luar. Namun dengan penuh kesabaran dan terutama pertolongan
dari Allah akhirnya tugas ini dapat terselesaikan. Semoga postingan ini dapat memberikan wawasan yang lebih luas dan menjadi sumbang pemikiran
kepada pembaca khususnya para mahasiswa Institut Sains & Teknologi AKPRIND
Yogyakarta. Kami sadar bahwa makalah ini masih banyak kekurangan dan jauh dari
sempurna. Untuk itu, kepada dosen pengampu matakuliah Sistem Berkas kami meminta masukannya demi perbaikan di masa yang akan
datang dan mengharapkan kritik dan saran dari para pembaca.
Yogyakarta,
30-Juni-2016
Salam
Kriuk dari Penyusu,
1.
Pengertian
Hashing
Hashing adalah transformasi aritmatik sebuah string dari karakter menjadi nilai yang merepresentasikan string aslinya. Menurut bahasanya, hash berarti memenggal dan kemudian menggabungkan. Hashing digunakan sebagai metode untuk menyimpan data dalam sebuah array agar penyimpanan data, pencarian data, penambahan data, dan penghapusan data dapat dilakukan dengan cepat. Ide dasarnya adalah menghitung posisi record yang dicari dalam array, bukan membandingkan record dengan isi pada array. Fungsi yang mengembalikan nilai atau kunci disebut fungsi hash (hash function) dan array yang digunakan disebut tabel hash (hash table). Hash table menggunakan struktur data array asosiatif yang mengasosiasikan record dengan sebuah field kunci unik berupa bilangan (hash) yang merupakan representasi dari record tersebut.
Secara teori, kompleksitas waktu
(T(n)) dari fungsi hash yang ideal adalah O(1). Untuk mencapai itu
setiap record membutuhkan suatu kunci yang unik. Fungsi hash menyimpan
nilai asli atau kunci pada alamat yang sama dengan nilai hashnya. Pada
pencarian suatu nilai pada tabel hash, yang pertama dilakukan adalah
menghitung nilai hash dari kunci atau nilai aslinya, kemudian
membandingkan kunci atuau nilai asli dengan isi pada memori yang beralamat
nomor hashnya. Dengan cara ini, pencarian suatu nilai dapat dilakukan dengan
cepat tanpa harus memeriksa seluruh isi tabel satu per satu.
Selain digunakan pada penyimpanan
data, fungsi hash juga digunakan pada algoritma enkripsi sidik jari
digital (fingerprint) untuk mengautentifikasi pengirim dan penerima
pesan. Sidik jari digital diperoleh dengan fungsi hash, kemudian nilai hash
dan tanda pesan yang asli dikirim kepada penerima pesan. Dengan menggunakan
fungsi hash yang sama dengan pengirim pesan, penerima pesan
mentransformasikan pesan yang diterima. Nilai hash yang diperoleh oleh
penerima pesan kemudian dibandingkan dengan nilai hash yang dikirim
pengirim pesan.
Kedua nilai hash harus
sama, jika tidak, pasti ada masalah. Hashing selalu merupakan fungsi
satu arah. Fungsi hash yang ideal tidak bisa diperoleh dengan melakukan reverse
engineering dengan menganalisa nilai hash. Fungsi hash yang
ideal juga seharusnya tidak menghasilkan nilai hash yang sama dari
beberapa nilai yang berbeda . Jika hal yang seperti ini terjadi, inilah yang
disebut dengan bentrokan (collision). Kemungkinan terjadinya bentrokan
tidak dapat dihindari seratus persen. Fungsi hash yang baik dapat
meminimalkan kemungkinan terjadinya bentrokan.
2.
Macam - Macam Fungsi Hash
Fungsi Hash (dilambangkan
dengan h(k)) bertugas untuk mengubah k (key) menjadi suatu nilai
dalam interval [0....X], dimana "X" adalah jumlah maksimum dari record-record
yang dapat ditampung dalam tabel. Jumlah maksimum ini bergantung pada ruang
memori yang tersedia. Fungsi Hash yang ideal adalah mudah dihitung dan
bersifat random, agar dapat menyebarkan semua key. Dengan key yang
tersebar, berarti data dapat terdistribusi secara seragam bentrokan dapat
dicegah. Sehingga kompleksitas waktu model Hash dapat mencapai O(1), di
mana kompleksitas tersebut tidak ditemukan pada struktur model lain. Ada
beberapa macam fungsi hash yang relatif sederhana yang dapat digunakan
dalam penyimpanan database:
a.
Metode Pembagian Bersisa (division-remainder method)
Jumlah lokasi memori yang tersedi
dihitung, kemudian jumlah tersebut digunakan sebagai pembagi untuk membagi
nilai yang asli dan menghasilkan sisa. Sisa tersebut adalah nilai hashnya.
Secara umum, rumusnya h(k)= k mod m. Dalam hal ini m adalah jumlah lokasi
memori yang tersedia pada array. Fungsi hash tersebut menempatkan record
dengan kunci K pada suatu lokasi memori yang beralamat h(k). Metode
ini sering menghasilkan nilai hash yang sama dari dua atau lebih nilai
aslinya atau disebut dengan bentrokan. Karena itu, dibutuhkan mekanisme khusus
untuk menangani bentrokan yang disebut kebijakan resolusi bentrokan.
b.
Melipat (folding)
Metode ini membagi nilai asli ke
dalam beberapa bagian, kemudian menambahkan nilai-nilai tersebut, dan mengambil
beberapa angka terakhir sebagai nilai hashnya.
c.
Transformasi Radiks (radix transformation)
Karena nilai dalam bentuk digital, basis angka atau radiks
dapat diganti sehingga menghasilkan urutan angka-angka yang berbeda. Contohnya
nilai desimal (basis 10) bisa ditransformasikan kedalam heksadesimal (basis
16). Digit atas hasilnya bisa dibuang agar panjang nilai hash dapat
seragam.
d.
Pengaturan ulang digit (digit rearrangement)
Metode ini mengubah urutan digit
dengan pola tertentu. Contohnya mengambil digit ke tiga sampai ke enam dari
nilai aslinya, kemudian membalikan urutannya dan menggunakan digit yang terurut
terbalik itu sebagai nilai hash. Fungsi hash yang bekerja dengan
baik untuk penyimpanan pada database belum tentu bekerja dengan baik untuk
keperluan kriptografi atau pengecekan kesalahan. Ada beberapa fungsi hash
terkenal yang digunakan untuk keperluan kriptografi. Diantaranya adalah fungsi
hash message-diggest, contohnya MD2, MD4, dan MD5, digunakan untuk
menghasilkan nilai hash dari tanda tangan digital yang disebut
messagediggest. Ada pula Secure Hash Algorithm (SHA), sebuah algoritma
standar yang menghasilkan message-diggest yang lebih besar (60-bit) dan serupa
dengan MD4.
3.
Bentrokan Pada Fungsi Hash
Fungsi hash bukan merupakan
fungsi satu-ke-satu, artinya beberapa record yangberbeda dapat
menghasilkan nilai hash yang sama / terjadi bentrokan. 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. Ada dua macam kebijakan resolusi bentrokan pada
tabel hash, yaitu kebijakan resolusi bentrokan di luar tabel dan
kebijakan resolusi bentrokan di dalam tabel. Harus diperhatikan juga
teknik-teknik penempatan record agar mudah dicari jika dibutuhkan.
a.
Kebijakan resolusi bentrokan di luar tabel
Artinya tabel hash bukan lagi menjadi array of
records, tetapi menjadi array of pointers. Setiap pointer menunjuk
ke senarai berkait yang berisi record tersebut. Metode seperti ini
dinamakan chaining. Dalam bentuk sederhananya berupa senarai berkait
dari recordrecord yang menghasilkan nilai hash yang sama.
Penambahan record dapat dilakukan dengan menambah senarai berisi record
tersebut. Untuk pencarian pada tabel, pertama-tama dicari nilai hash terlebih
dahulu, kemudian dilakukan pencarian dalam senarai berkait yang bersangkutan.
Untuk menghapus suatu record, hanya menghapus senarainya saja. Kelebihan
dari metode chaining ini chaining ini adalah proses penghapusan
yang relarif mudah dan penambahan ukuran tabel hash bisa ditunda untuk
waktu yang lebih lama karena penurunan kinerjanya berbanding lurus meskipun
seluruh lokasi pada tabel sudah penuh. Bahkan, penambahan ukuran tabel bisa
saja tidak perlu dilakukan sama sekali karena penurunan kinerjanya yang linier.
Misalnya, tabel yang berisi record sebanyak dua kali lipat kapasitas
yang direkomendasikan hanya akan lebih lambat dua kali lipat dibanding yang
berisi sebanyak kapasitas yang direkomendasikan. Kekurangan dari metode chaining
ini sama dengan kekurangan dari senarai berkait. Operasi traversal pada
senarai berkait memiliki performa cache yang buruk.
Struktur data lain dapat digunakan
sebagai pengganti senarai berkait. Misalnya dengan pohon seimbang, kompleksitas
waktu terburuk bisa diturunkan menjadi O(log n) dari yang sebelumnya
O(n). Namun demikian, karena setiap senarai diharapkan untuk tidak panjang,
struktur data pohon ini kurang efisien kecuali tabel 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.
b.
Kebijakan resolusi bentrokan di dalam tabel
Berbeda dengan kebijakan resolusi
bentrokan di luar tabel, pada kebijakan resolusi di dalam tabel data disimpan
di dalam hash tabel tersebut, bukan dalam senarai berkait yang
bertambah terus menerus. Dengan demikian data yang disimpan tidak mungkin bisa
lebih banyak daripada jumlah ruang pada tabel hash. Jika suatu record
akan dimasukkan ke dalam tabel hash pada lokasi sesuai nilai hash-nya
dan ternyata lokasi tersebut sudah diisi dengan record lain maka harus
dicari lokasi alternatif yang masih belum terisi dengan cara tertentu. Cara ini
disebut 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
Dengan menambahkan suatu interval
pada hasil yang diperoleh dari fungsi hash sampai ditemukan lokasi yang
belum terisi. Interval yang biasa digunakan adalah
2.
Quadratic probing / 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 metode double hashing, jika lokasi yang
diperoleh dengan fungsi hash sudah terisi, maka dilakukan proses hash
lagi sampai ditemukan lokasi yang belum terisi.
c.
Perbandingan antara metode chaining
dan open addressing
Keunggulan metode chaining dibanding
open addressing:
1.
Lebih mudah diimplementasikan dengan efektif dan hanya
membutuhkan struktur data dasar.
2.
Metode chaining tidak rawan terhadap data-data yang
berkumpul di daerah tertentu. Metode open addressing membutuhkan
algoritma hash yang lebih baik untuk menghindari pengumpulan data di
sekitar lokasi tertentu.
3.
Performa menurun secara linier. Meskipun semakin banyak record
yang dimasukkan maka semakin panjang senarai berantai, tabel hash tidak
akan penuh dan tidak akan menimbulkan peningkatan waktu pencarian record yang
tibatiba meningkat yang terjadi bila menggunakan metode open addressing.
4.
Jika record yang dimasukkan panjang, memori yang
digunakan akan lebih sedikit dibandingkan dengan metode open addressing.
Perbandingan waktu yang diperlukan untuk melakukan pencarian. Saat tabel mencapai
80% terisi, kinerja pada linear probing(open addressing)menurun drastis.
Untuk ukuran record yang kecil, keunggulan metode open addressing dibandingkan
dengan chaining diantaranya
ð Ruang yang digunakan lebih efisien
karena tidak perlu menyimpan pointer atau mengalokasi tempat tambahan di
luar tabel hash.
ð Tidak ada waktu tambahan untuk
pengalokasian memori karena metode open addressing tidak memerlukan
pengalokasian memori.
ð Tidak memerlukan pointer.
Sebenarnya, penggunaan algoritma apapun pada tabel hash biasanya cukup
cepat, dan persentase kalkulasi yang dilakukan pada tabel hash rendah.
Penggunaan memori juga jarang berlebihan. Oleh karena itu, pada kebanyakan
kasus, perbedaan antar algoritma ini tidak signifikan.
d.
Metode-metode lain
Selain metode-metode yang sudah
disebutkan di atas, ada juga beberapa metode lain diantaranya :
1.
Coalesced hashing
Gabungan dari chaining dan openaddressing.
Coalesced hashing menghubungkan ke tabel itu sendiri. Seperti open
addressing, metode ini memiliki keunggulan pada penggunaan tempat dan cache
dibanding metode chaining. Seperti chaining, metode ini
menghasilkan lokasi penyimpanan yang lebih menyebar, tetapi pada metode ini record
yang disimpan tidak mungkin lebih banyak daripada ruang yang
disediakan tabel.
2.
Perfect hashing
Jika record yang akan
digunakan sudah diketahui sebelumnya, dan jumlahnya tidak melebihi jumlah ruang
pada tabel hash, perfect hashing bisa digunakan untuk membuat
tabel hash yang sempurna, tanpa ada bentrokan.
3.
Probabilistic hashing
Kemungkinan solusi paling sederhana
untuk mengatasi bentrokan adalah dengan mengganti record yang sudah
disimpan dengan record yang baru, atau membuang record yang baru
akan dimasukkan. Hal ini bisa berdampak tidak ditemukannya record pada
saat pencarian. Metode ini digunakan untuk keperluan tertentu saja.
4.
Robin Hood hashing
Salah satu variasi dari resolusi
bentrokan double hashing. Ide dasarnya adalah sebuahrecord yang
sudah dimasukkan bisa digantikan dengan record yang baru jika nilai
pencariannya (probe count – bertambah setiap menemukan termpat yang
sudah terisi) lebih besar daripada nilai pencarian dari record yang
sudah dimasukkan. Efeknya adalah mengurangi kasus terburuk waktu yang
diperlukan untuk pencarian.
http://syazdiayhodian.blogspot.co.id/2011/06/hashing.html
BERIKUT PROSES PERHITUNGANNYA MENURUT YANG DITENTUKAN
PADA SOAL :
Soal
|
#
|
Kode
|
Nama
|
Status
|
SKS
|
Smt
|
|
1
|
IPBU
11101
|
Pancasila
|
W
|
2
|
1
|
|
2
|
IPBU
11102
|
Agama
|
W
|
2
|
1
|
|
3
|
TIFS
11103
|
Database
|
W
|
2
|
1
|
|
4
|
TIFS
21202
|
Delphi
|
W
|
2
|
2
|
|
5
|
TIFS
21201
|
Foxpro
|
W
|
2
|
2
|
|
6
|
TIFS
22105
|
Pascal
|
W
|
2
|
2
|
Pertanyaan
:
Selesaikan soal diatas dengan menggunakan FUNGSI HASH
sebagai berikut :
1. K MOD N
2. K MOD P
3. Midsquaring
4. Penjumlahan Digit
5. Multiplication
6. Trunction
7. Folding
8.
Konversi Radix
Penyelesaian
:
- 1 Asumsi yang digunakan pada soal kali ini adalah penempatan kode mata kuliah yang dijadikan kunci dalam penyimpanan dalam memori.
- 2 Kode mata kuliah tersebut memiliki asumsi sebagai berikut :
Terdiri dari 10 karakter, yaitu 4 huruf 1 spasi dan 5 angka.
- 3 Kita misalkan 4 huruf kode matakuliah tersebut merupakan patokan dalam penempatan penyimpanan dalam memori. Misal IPBU = 1 dan TIFS = 2 dan spasi kita anggap tidak ada.
- 4 Sehingga kode mata kuliah menjadi 6 karakter angka, dimana angka pertama merupakan hasil permisalan konversi diatas.
Disimpan:
1. K
MOD N
2. K
MOD P
3.
Midsquaring
4.
Penjumlahan Digit
5.
Multiplication
6.
Trunction
7.
Folding
8.
Konversi Radix
1 K MOD N
Ditanyakan:
Penempatan Nilai-2 kunci
Rata-rata akses
Dik: Nilai-2 kunci
:
11101, 11102, 11103,
21202, 21201, 22105
Dit: Penempatan
nila-2 kunci dan Rata-rata akses
Jawab:
Kunci: 11101, 11102, 11103, 21202, 21201, 22105
N=6
P=7 LISCH (Late Insertion Standard Coalesced Hashing)
|
Record
|
Kunci
|
Link
|
|
0
|
||
|
1
|
11101
|
6
|
|
2
|
11102
|
|
|
3
|
11103
|
5
|
|
4
|
21202
|
|
|
5
|
22105
|
|
|
6
|
21201
|
Alamat indeks=0-6
H(11101)=11101 MOD 6=1
H(11102)=11102 MOD 6=2
H(11103)=11103 MOD 6=3
H(21202)=21202 MOD 6=4
H(21201)=21201 MOD 6=3 (collicon)->6
H(22105)=22105 MOD 6=1 (collicon)->5
Rata-rata akses nilai kunci: (6+2)/6=1.33
Ket:
6->lkh penempatan kunci pd home address
2->lkh penempatan kunci 11101, 11103
(collision)
1 K MOD P
Alamat indeks 2 digit
Kunci: 11101, 11102, 11103, 21202, 21201, 22105
a)
H(K)=K MOD M
M=97
Alamat
indeks=0-96
H(11101)=
11101 MOD 97=43
H(11102)=
11102 MOD 97=44
H(11103)=
11103 MOD 97=45
H(21202)=
21202 MOD 97=56
H(21201)=
21201 MOD 97=55
H(22105)=
22105 MOD 97=86
Penempatan
nilai-nilai kunci
|
Record
|
Kunci
|
|
0
|
|
|
…
|
|
|
43
|
11101
|
|
44
|
11102
|
|
45
|
11103
|
|
…
|
|
|
55
|
21201
|
|
56
|
21202
|
|
…
|
|
|
86
|
22105
|
|
…
|
|
|
96
|
Rata-rata
akses =6/97=0,0618= 0,062
b)
H(K) = K MOD M + 1
M = 97
Alamat indeks = 1 – 97
H(11101)=
11101 MOD 97+1=44
H(11102)=
11102 MOD 97+1=45
H(11103)=
11103 MOD 97+1=46
H(21202)=
21202 MOD 97+1=57
H(21201)=
21201 MOD 97+1=56
H(22105)=
22105 MOD 97+1=87
Penempatan
nilai-nilai kunci
|
Record
|
Kunci
|
|
1
|
|
|
…
|
|
|
44
|
11101
|
|
45
|
11102
|
|
46
|
11103
|
|
…
|
|
|
56
|
21201
|
|
57
|
21202
|
|
…
|
|
|
87
|
22105
|
|
…
|
|
|
97
|
Rata-rata
akses =6/97=0,0618= 0,062
2
Midsquaring
Alamat
indeks 2 digit
Kunci: 11101, 11102, 11103, 21202, 21201, 22105
Alamat
indeks=0-99
|
K
|
11101
|
11102
|
11103
|
21202
|
21201
|
22105
|
|
K²
|
0123232201
|
0123254404
|
0123276609
|
0449524804
|
0449482401
|
0488631025
|
|
H(K)
|
23
|
25
|
27
|
52
|
48
|
63
|
Penempatan
nilai kunci
|
Record
|
Kunci
|
|
0
|
|
|
…
|
|
|
23
|
11101
|
|
…
|
|
|
25
|
11102
|
|
..
|
|
|
27
|
11103
|
|
…
|
|
|
48
|
21201
|
|
…
|
|
|
52
|
21202
|
|
…
|
|
|
63
|
22105
|
|
…
|
|
|
99
|
Rata-rata akses= 6 / 100 = 0,06
3
Penjumlahan Digit
Alamat
indeks 2 digit
Kunci: 11101, 11102, 11103, 21202,
21201, 22105
Alamat
indeks=0-99
H(11101)= 1+11+01=13
H(11102)= 1+11+02=14
H(11103)= 1+11+03=15
H(21202)= 2+12+02=16
H(21201)= 2+12+01=15 (Collicon)->99
H(22105)= 2+21+05=28
Penempatan nilai kunci
|
Record
|
Kunci
|
Link
|
|
0
|
||
|
…
|
||
|
13
|
11101
|
|
|
14
|
11102
|
|
|
15
|
11103
|
99
|
|
16
|
21202
|
|
|
…
|
||
|
28
|
22105
|
|
|
…
|
||
|
99
|
21201
|
Rata-rata
akses= 6 / 100 = 0,06
4
Multiplication
Alamat
indeks 2 digit
Kunci: 11101, 11102, 11103, 21202, 21201, 22105
Alamat
indeks=0-99
H(11101)= 1 | 11 | 01 1*01=1
H(11102)= 1 | 10 | 02 1*02=2
H(11103)= 1 | 10 | 03 1*03=3
H(21202)= 2 | 12 | 02 2*02=4
H(21201)= 2 | 12 | 01 2*01=2
(Collicon)->99
H(22105)= 2 | 21 | 05 2*05=10
Penempatan nilai-nilai kunci
|
Record
|
Kunci
|
Link
|
|
0
|
||
|
…
|
||
|
1
|
11101
|
|
|
2
|
11102
|
99
|
|
3
|
11103
|
|
|
4
|
21202
|
|
|
…
|
||
|
10
|
22105
|
|
|
…
|
||
|
99
|
21201
|
Rata-rata
akses= 6 / 100 = 0,06
5
Trunction
Pemotongan
dilakukan pada 3 digit terakhir
Kunci: 11101, 11102, 11103, 21202, 21201, 22105
Alamat
indeks=0-99
|
K
|
11101
|
11102
|
11103
|
21202
|
21201
|
22105
|
|
H(K)
|
101
|
102
|
103
|
202
|
201
|
105
|
Penempatan nilai-nilai kunci
|
Record
|
Kunci
|
|
0
|
|
|
…
|
|
|
101
|
11101
|
|
102
|
11102
|
|
103
|
11103
|
|
105
|
22105
|
|
…
|
|
|
201
|
21201
|
|
202
|
21202
|
|
999
|
Rata-rata
akses= 6 / 100 = 0,06
6
Folding
a)
Folding by boundary (non carry)
Alamat
indeks 2 digit
Kunci: 11101, 11102, 11103, 21202, 21201, 22105
Alamat
indeks=0-99
H(11101)= 1 | 11 | 01=10+11+10=31
H(11102)= 1 | 11 | 02=20+11+10=41
H(11103)= 1 | 11 | 03=30+11+10=51
H(21202)= 2 | 12 | 02=20+12+20=52
H(21201)= 2 | 12 | 01=10+12+20=42
H(22105)= 2 | 21 | 05=50+21+20=91
Penempatan
nilai kunci
|
Record
|
Kunci
|
|
0
|
|
|
…
|
|
|
31
|
11101
|
|
…
|
|
|
41
|
11102
|
|
42
|
21201
|
|
…
|
|
|
51
|
11103
|
|
52
|
21202
|
|
…
|
|
|
91
|
22105
|
|
…
|
|
|
99
|
Rata-rata
akses= 6 / 100 = 0,06
b)
Folding by boundary ( carry)
Alamat
indeks 2 digit
Kunci: 11101, 11102, 11103, 21202, 21201, 22105
Alamat
indeks=0-99
H(11101)= 1 | 11 | 01=10+11+10=31
H(11102)= 1 | 11 | 02=20+11+10=41
H(11103)= 1 | 11 | 03=30+11+10=51
H(21202)= 2 | 12 | 02=20+12+20=52
H(21201)= 2 | 12 | 01=10+12+20=42
H(22105)= 2 | 21 | 05=50+21+20=91
Penempatan
nilai kunci
|
Record
|
Kunci
|
|
0
|
|
|
…
|
|
|
31
|
11101
|
|
…
|
|
|
41
|
11102
|
|
42
|
21201
|
|
…
|
|
|
51
|
11103
|
|
52
|
21202
|
|
…
|
|
|
91
|
22105
|
|
…
|
|
|
99
|
Rata-rata
akses= 6 / 100 = 0,06
c)
Folding by shifting (non carry)
Alamat indeks 2 digit
Kunci: 11101, 11102, 11103, 21202, 21201, 22105
Alamat
indeks=0-99
H(11101)= 1 | 11 | 01=13
H(11102)= 1 | 11 | 02=14
H(11103)= 1 | 11 | 03=15
H(21202)= 2 | 12 | 02=16
H(21201)= 2 | 12 | 01=15 (Collicon)->99
H(22105)= 2 | 21 | 05=28
Penempatan
nilai kunci
|
Record
|
Kunci
|
Link
|
|
0
|
||
|
…
|
||
|
13
|
11101
|
|
|
14
|
11102
|
|
|
15
|
11103
|
99
|
|
16
|
21202
|
|
|
…
|
||
|
28
|
22105
|
|
|
…
|
||
|
99
|
21201
|
Rata-rata
akses= 6 / 100 = 0,06
d)
Folding by shifting (carry)
Alamat indeks 2 digit
Kunci: 11101, 11102, 11103, 21202, 21201, 22105
Alamat
indeks=0-99
H(11101)= 1 | 11 | 01=13
H(11102)= 1 | 11 | 02=14
H(11103)= 1 | 11 | 03=15
H(21202)= 2 | 12 | 02=16
H(21201)= 2 | 12 | 01=15 (Collicon)->99
H(22105)= 2 | 21 | 05=28
Penempatan
nilai kunci
|
Record
|
Kunci
|
Link
|
|
0
|
||
|
…
|
||
|
13
|
11101
|
|
|
14
|
11102
|
|
|
15
|
11103
|
99
|
|
16
|
21202
|
|
|
…
|
||
|
28
|
22105
|
|
|
…
|
||
|
99
|
21201
|
Rata-rata
akses= (6 +1)/ 100 = 0,07
7
Konversi Radix
Alamat indeks 7 digit
Kunci: 11101, 11102, 11103, 21202, 21201, 22105
Alamat
indeks=0-9999999
H(11101)= 1
* 154 + 1 * 15³ + 1 * 15² + 0* 15¹ + 1* 15º
=54225
H(11102)= 1 * 154 + 1 * 153
+ 1 * 152 + 0* 151 + 2* 150
=54225
H(11103)= 1 * 154 + 1 * 153
+ 1 * 152 +0* 151 + 3* 150
=54225
H(21202)= 2 * 154 + 1 * 153
+ 2 * 152 + 0* 151 + 2* 150
=105075
H(21201)= 2 * 154 + 1 * 153
+ 2 * 152 + 0* 151 + 1* 150
=105075
H(22105)= 2 * 154 + 2 * 153
+ 1 * 152 + 0* 151 + 5* 150
=108225
Kunci: 11101, 11102, 11103, 21202, 21201, 22105
N=6
P=15
Alamat indeks=0-6
H(11101)11101 MOD 15=1
H(11102)=11102 MOD 15=2
H(11103)=11103 MOD 15=3
H(21201)=21201 MOD 15=6
H(21202)=21202 MOD 15=7
H(22105)=22105 MOD 15=10
EISCH (Early Insertion Coalesced Hashing)
Penempatan
nilai kunci
|
Record
|
Kunci
|
|
0
|
|
|
...
|
|
|
54225
|
11101
|
|
54225
|
11102
|
|
54225
|
11103
|
|
…
|
|
|
...
|
|
|
105075
|
21201
|
|
105075
|
21202
|
|
...
|
|
|
108225
|
22105
|
|
9999999
|
Rata-rata akses :
6 /
10000000 = 0,0000006
Komentar