Teknik" kalkulasi alamat

Teknik – Teknik Kalkulasi Alamat

Perhitungan (kalkulasi) terhadap nilai kunci atribut untuk mendapatkan nilai suatu alamat disebut dengan fungsi hash. Bisa juga fungsi hash digabungkan dengan teknik pencarian seperti tabel di atas, tetapi akan menjadi lebih lama pengerjaannya dibanding hanya dengan satu jenis saja (fungsi hash saja atau pencarian tabel saja).

Fungsi hash dikatakan baik bila memiliki kalkulasi yang sederhana dan memiliki kelas ekivalen (synonim) yang kecil, atau sederhananya, memiliki kalkulasi yang mudah tetapi memiliki benturan alamat yang sedikit.

Ada beberapa cara untuk mengatasi benturan (collision) penggunaan alamat seperti di atas, antara lain :

Scatter diagram techniques

Kualitas Perangkat lain yang dapat digunakan untuk menunjukkan hubungan antara “pasangan data”, dan dapat memberikan manfaat informasi lebih lanjut tentang proses produksi. Yang dimaksud dengan “data pasangan”? Istilah “sebab-akibat” hubungan antara dua jenis data juga bisa merujuk kepada hubungan antara satu sebab dan lain, atau antara satu penyebab dan beberapa orang lainnya. Misalnya, Anda dapat mempertimbangkan hubungan antara kekerasan bahan dan produk; antara kecepatan potong dari pisau dan variasi yang diamati pada panjang bagian, atau hubungan antara tingkat pencahayaan di lantai produksi dan kesalahan yang dibuat dalam inspeksi kualitas produk yang dihasilkan.

Randomizing techniques

Dalam teori, fungsi pengacakan diasumsikan benar-benar acak, dan hasil fungsi tak terduga algoritma berbeda setiap kali dijalankan. Teknik pengacakan tidak akan bekerja jika, pada setiap pelaksanaan algoritma pengacakan fungsi selalu melakukan pemetaan yang sama, atau pemetaan sepenuhnya ditentukan oleh beberapa parameter eksternal dapat diamati (seperti waktu startup program). Dengan sebuah pengacakan “-pseudo” fungsi, seseorang bisa secara prinsip membangun urutan fungsi telepon seperti yang selalu akan menghasilkan “buruk” kasus untuk algoritma deterministik yang mendasarinya. Untuk itu urutan dari panggilan, biaya rata-rata akan lebih dekat untuk biaya-kasus terburuk, daripada biaya rata-rata untuk input acak.

Key to address transformation methods

Teknik yang digunakan dalam teori mengoreksi kesalahan-kode ini diterapkan untuk menyelesaikan masalah menangani file besar. Pendekatan baru ini ke file menangani masalah digambarkan dengan desain khusus untuk menunjukkan kelayakan. fektivitas adalah lebih lanjut diilustrasikan dengan membandingkan hasil uji yang diperoleh dari simulasi perhitungan, yang menggunakan data khas, terhadap nilai-nilai dihitung dari model yang ideal.

Direct addressing techniques

Dalam menangani langsung, instruksi yang memberitahu dimana nilai tersebut dapat ditemukan, tetapi nilai itu sendiri dalam memori. Dalam sebuah bahasa tingkat tinggi, langsung menangani sering digunakan untuk hal-hal seperti variabel global.

Hash tables methods

Struktur data yang menggunakan fungsi hash untuk efisien peta pengidentifikasi tertentu atau Keys (misalnya, nama-nama orang) untuk dihubungkan sebuah nilai (misalnya, nomor telepon mereka). Fungsi hash digunakan untuk mengubah kunci ke indeks (hash) dari array elemen (dalam slot atau ember) dimana nilai yang sesuai yang akan dicari.

Idealnya fungsi hash harus memetakan setiap tombol untuk mengindeks slot yang berbeda, tapi ideal ini jarang dicapai dalam praktek (kecuali tombol hash tetap; entri baru yaitu tidak pernah ditambahkan ke tabel setelah dibuat). Kebanyakan desain tabel hash berasumsi bahwa hash collisions -pasang kunci yang berbeda dengan nilai hash yang sama-kejadian normal dan harus diakomodasi dalam beberapa cara.

Contoh Program Kalkulasi “HASH TABLE METHODS”

#include <iostream>
#include <hash_map>
#include <string.h>
using namespace std;
using namespace __gnu_cxx;
struct eqstr{
bool operator()(const char* s1, const char* s2) const {
return strcmp(s1,s2)==0;
}
};
int main(){
hash_map, eqstr> months;
months[“january”] = 31;
months[“february”] = 28;
months[“march”] = 31;
months[“april”] = 30;
months[“may”] = 31;
months[“june”] = 30;
months[“july”] = 31;
months[“august”] = 31;
months[“september”] = 30;
months[“october”] = 31;
months[“november”] = 30;
months[“december”] = 31;
cout << “september -> ” << months[“september”] << endl;
cout << “april -> ” << months[“april”] << endl;
cout << “june -> ” << months[“june”] << endl;
cout << “november -> ” << months[“november”] << endl;
return 0;
}

Hashing

Teknik mengindeks pada menajemen database dimana nilai kunci (yang mengindentifikasikan record) dimanipulasi secara numerik untuk menghitung langsung lokasi record yang berkaitan atau titik tolak untuk mencari record yang terkait. Yang betujuan utamanya adalah agar dua buah kunci yang berbeda tidak mempunyai nilai hash yang sama. Jika hal ini terjadi, akan menyebabkan terjadinya tabrakan.

Contoh Program Kalkulasi Alamat “HASING”

#pragma comment(lib, “crypt32.lib”)
#include <stdio.h>
#include <windows.h>
#include <Wincrypt.h>
#define MY_ENCODING_TYPE (PKCS_7_ASN_ENCODING | X509_ASN_ENCODING)
void MyHandleError(char *s);
void main(void)
{
HCRYPTPROV hProv;
BYTE *pbBuffer= (BYTE *)” Data yang harus hashed dan ditandatangani..”;
DWORD dwBufferLen = strlen((char *)pbBuffer)+1;
HCRYPTHASH hHash;
HCRYPTKEY hKey;
HCRYPTKEY hPubKey;
BYTE *pbKeyBlob;
BYTE *pbSignature;
DWORD dwSigLen;
DWORD dwBlobLen;

if(CryptAcquireContext(
&hProv,
NULL,
NULL,
PROV_RSA_FULL,
0))
{
printf(“CSP konteks yang diperoleh.\n”);
}
else
{
MyHandleError(“Kesalahan selama CryptAcquireContext”);
}

if(CryptGetUserKey(
hProv,
AT_SIGNATURE,
&hKey))
{
printf(“Kunci Signature telah diperoleh.\n”);
}
else
{
MyHandleError(“Kesalahan selama CryptGetUserKey untuk signkey”);
}

if(CryptExportKey(
hKey,
NULL,
PUBLICKEYBLOB,
0,
NULL,
&dwBlobLen))
{
printf(“Ukuran dari blob untuk kunci publik yang ditentukan. \n”);
}
else
{
MyHandleError(“Kesalahan perhitungan panjang BLOB.”);
}

if(pbKeyBlob = (BYTE*)malloc(dwBlobLen))
{
printf(“Memory telah dialokasikan ke BLOB. \n”);
}
else
{
MyHandleError(“Memori penuh. \n”);
}

if(CryptExportKey(
hKey,
NULL,
PUBLICKEYBLOB,
0,
pbKeyBlob,
&dwBlobLen))
{
printf(“Isi telah ditulis ke BLOB. \n”);
}
else
{
MyHandleError(“Kesalahan selama CryptExportKey.”);
}

if(CryptCreateHash(
hProv,
CALG_MD5,
0,
0,
&hHash))
{
printf(“Objek Hash telah dibuat. \n”);
}
else
{
MyHandleError(“Kesalahan selama CryptCreateHash.”);
}

if(CryptHashData(
hHash,
pbBuffer,
dwBufferLen,
0))
{
printf(“Buffer data telah di hash. \n”);
}
else
{
MyHandleError(“Kesalahan selama CryptHashData.”);
}

dwSigLen= 0;
if(CryptSignHash(
hHash,
AT_SIGNATURE,
NULL,
0,
NULL,
&dwSigLen))
{
printf(“Signature% panjang d ditemukan. \n”,dwSigLen);
}
else
{
MyHandleError(“Kesalahan selama CryptSignHash.”);
}

if(pbSignature = (BYTE *)malloc(dwSigLen))
{
printf(“Memori dialokasikan untuk signatur.\n”);
}
else
{
MyHandleError(“Memori penuh.”);
}

if(CryptSignHash(
hHash,
AT_SIGNATURE,
NULL,
0,
pbSignature,
&dwSigLen))
{
printf(“pbSignature adalah tanda hash. \n”);
}
else
{
MyHandleError(“Kesalahan selama CryptSignHash.”);
}

if(hHash)
CryptDestroyHash(hHash);

printf(“Objek Hash sudah dihapus.\n”);
printf(“Pada tahap penandatanganan program ini selesai.\n\n”);

if(CryptImportKey(
hProv,
pbKeyBlob,
dwBlobLen,
0,
0,
&hPubKey))
{
printf(“Key sudah diimport.\n”);
}
else
{
MyHandleError(“Public key import gagal.”);
}

if(CryptCreateHash(
hProv,
CALG_MD5,
0,
0,
&hHash))
{
printf(“Object hash telah dibuat ulang. \n”);
}
else
{
MyHandleError(“Kesalahan selama CryptCreateHash.”);
}

if(CryptHashData(
hHash,
pbBuffer,
dwBufferLen,
0))
{
printf(“Hash baru telah dibuat.\n”);
}
else
{
MyHandleError(“Kesalahan selama CryptHashData.”);
}

if(CryptVerifySignature(
hHash,
pbSignature,
dwSigLen,
hPubKey,
NULL,
0))
{
printf(“Signature ini telah diverifikasi.\n”);
}
else
{
printf(“Signature tidak divalidasi! \n”);
}

if(pbSignature)
free(pbSignature);

if(hHash)
CryptDestroyHash(hHash);

if(hProv)
CryptReleaseContext(hProv, 0);
}

void MyHandleError(char *s)
{
fprintf(stderr,” Sebuah kesalahan terjadi dalam menjalankan program ini. \n”);
fprintf(stderr,”%s\n”,s);
fprintf(stderr, “Nomer kesalahan %x.\n”, GetLastError());
fprintf(stderr, “Program selesai. \n”);
exit(1);
}


*    Division Remainder

Pada division remainder, alamat relative dari suatu nilai key merupakan sisa dari hasil pembagian nilai key tersebut dengan suatu bilangan yang disebut sebagai bilangan pembagi.

Contoh :

Bila DIV adalah pembagi, KEY adalah nilai key dan ADDR adalah alamat relative, maka dalam bahasa Pascal, fungsi R(NILAI KEY)                  ADDRESS. Dapat diimplementasikan :

ADDR := KEY MOD DIV

Dalam bahasa COBOL :

DIVIDE KEY BY DIV GIVING TEMP REMAINDER ADDR

Sisa pembagian (sebagai hasil dari fungsi MOD pada Pascal), dapat dijabarkan sebagai berikut :

ADDR := KEY – DIV * TEMP


ADDR harus merupakan bilangan integer.

Banyak faktor yang harus dipertimbangkan dalam pemilihan pembagi :

–    Jangkauan dari nilai key yang dihasilkan dari operasi KEY MOD DIV adalah 0 sampai DIV-1.Nilai dari DIV menentukan ukuran “relatif address space”.Jika diketahui berkas relatif terdiri dari N record dan dianggap hanya satu record dapat disimpan dalam sebuah alamat relatif, maka akan didapat DIV > N

–     Pembagi harus diseleksi untuk mengurangi benturan. Penyelidikan menunjukkan bahwa pembagi yang berupa bilangan genap akan cenderung jelek, terutama dengan nilai key-nya yang dominan ganjil.

–     Menurut riset dari W.Buchholz, sebaiknya pembagi itu merupakan bilangan prima. Tetapi riset lain dari V.Y.Lum, menyatakan pembagi yang bukan bilangan prima akan memberikan hasil yang sama baik seperti bilangan prima.

–     Menurut pendapatnya, bukan bilangan prima yang mempunyai faktor prima kurang dari 20 akan dapat memberikan jaminan penampilan yang lebih baik

–     Walaupun kita telah menentukan pembagi dengan baik untuk mengatasi benturan, bila ruang alamat dari berkas relative mendekati penuh, maka peluang terjadinya benturan akan meningkat.

Untuk mengukur kepenuhan berkas relative digunakan Load Factor (Faktor Muat)

Banyak record dalam berkas

Laod Factor =

Max. banyak record dalam berkas

Biasanya load factor yang sering digunakan adalah 0.7 atau 0.8. Jika load factor lebih besar dari 0.7 atau 0.8 maka berkas tersebut harus diperbesar dan direorganisasi.

Jadi jika ingin menyimpan sebanyak n record pada suatu berkas dan load factor adalah 0.8, maka max banyak record pada berkas adalah 1.25 n

n

0.8 =

max

max = 1.25 n

Contoh :

Kita ingin membuat berkas yang terdiri dari 4000 record.

Load Factor (Faktor muat) = 0.8

Maka max. banyak record pada berkas :

(1.25) n = (1.25) . 4000

= 5000

Bilangan pembagi : 5003

123456789 = 24676 sisa 2761 + 1

5003

alamat relatif

987654321 =197412 sisa 2085 + 1

5003

alamat relative

Jadi alamat relatif didapat dari sisa pembagian + 1


*    Mid Square Hashing

Untuk mendapatkan alamat relatif, nilai key dikuadratkan, kemudian beberapa digit diambil dari tengah.

Dari nilai key yang dikuadratkan kita cari tengah-tengahnya.

Jumlah nilai key yang dikuadratkan, dari nilai key 1234567892 =  15241578750190521 (17 digit)

17            1

Untuk alamat relatif =      2     = 8   2

Kita mulai dari digit ke 8 dihitung dari kiri, maka alamat relative = 8750 (karena ditentukan 4 digit sebagai alamat relatif).

*    Hashing by folding

Untuk mendapatkan alamat relatif, nilai key dibagi menjadi beberapa bagian, setiap bagian (kecuali bagian terakhir) mempunyai jumlah digit yang sama dengan alamat relatif.

Bagian-bagian ini kemudian dilipat (seperti kertas) dan dijumlah. Hasilnya, digit yang tertinggi dibuang (bila diperlukan)

Contoh :

Nilai key 123456789 dan alamat relatif sebanyak 4 digit . Nilai key dibagi menjadi bagian-bagian yang terdiri dari 4 digit, mulai dari sebelah kanan.

1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
Menghasilkan :

1

2 3 4 5

9 8 7 6  +

1 3 2 2 1