Hash Middle Square_Muh Akbar Tamrin_1144012
#include <iostream>
#include <math.h>
#include <stdlib.h>
#include <conio.h>
using namespace std;
int a[] = { 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000 };
int middleSquareNumber(int numb, int dig)
{
int sqn = numb * numb, next_num = 0;
int trim = (dig / 2);
sqn = sqn / a[trim];
for (int i = 0; i < dig; i++)
{
next_num += (sqn % (a[trim])) * (a[i]);
sqn = sqn / 10;
}
return next_num;
}
int main(int argc, char **argv)
{
cout << "Enter the #-digit random numbers you want: ";
int n;
cin >> n;
int start = 1, end = 1;
start = a[n - 1];
end = a[n];
int number = ((rand()) % (end - start)) + start;
cout << "The random numbers are:\n" << number << ", ";
for (int i = 1; i < n; i++)
{
number = middleSquareNumber(number, n);
cout << number << ", ";
}
cout << "...";
getch();
return 0;
}
Outputnya :
HASH MIDDLE SQUARE
Sebelum membahas tentang Middle Square, kita bahas dulu Hashing. Hash merupakan suatu metode
yang secara langsung mengakses record-record dalam suatu tabel dengan melakukan
transformasi aritmatik pada key yang menjadi alamat dalam tabel tersebut. Key
merupakan suatu input dari pemakai di mana pada umumnya berupa nilai atau
string karakter.
Teknik Hashing meliputi suatu perhitungan
aritmetika pada nilai kunci untuk menghasilkan satu bilangan bulat /integer.
Bilangan bulat ini merupakan alamat relatif dimana nilai kunci disimpan di
direktori. Direktori disimpan sebagai satu array
File akses langsung (direct file) atau kadang
disebut juga random access menekankan faktanya permintaan record itu sendiri
tidak dalam ukuran khusus(data dalam keadaan acak).
Tujuan Hashing untuk menemukan fungsi yang
memudahkan perhitungan untuk memetakan setiap nilai kunci kedalam suatu nilai
kosong.
FUNGSI HASH
Fungsi Hash yang mendekati ideal sangat menentukan
kemerataan penyebaran kata pada tabel Hash, sehingga dapat meminimalkan jumlah
collision yang terjadi. Fungsi Hash yang ideal adalah mudah dikomputasikan dan
bersifat random untuk meminimalkan jumlah collision. Hasil random tersebut
dicapai dengan cara memanfaatkan seluruh unsur dalam key dan memperhatikan
semua urutan dalam key tersebut. Namun dalam pemanfaatan seluruh unsur dalam
key dapat berakibat pada sulitnya komputasi fungsi Hash. Fungsi Hash yang
kompleks akan menambah kompleksitas (bisa menyebabkan fungsi Hash tidak lagi
linier) yang mengakibatkan penambahan running time pada saat perhitungan
terhadap fungsi Hash. Dengan demikian, perlu dicari suatu algoritme Hash yang
bagus.
JENIS FUNGSI HASH
Fungsi Hash (dilambangkan dengan h(key)) bertugas
untuk mengubah key menjadi suatu nilai dalam interval [0....LEVELSIZE-1],
dimana "LEVELSIZE" 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 dan collision dapat dicegah. Sehingga
kompleksitas kinerja model Hash dapat mencapai O(1), di mana kompleksitas
tersebut tidak ditemukan pada struktur model lain.
Beberapa Fungsi Hash yang umum digunakan adalah :
a Division-Remainder(Pembagian sisa)
b Truncation(Pemenggalan)
c Folding(Lipatan)
d Multiplication(Perkalian)
e Mid-Square
a Division-Remainder(Pembagian sisa)
Tehnik Hashing menggunakan sisa pembagian adalah
dengan cara membagi satu nilai kunci dengan satu nomor yang cocok / disediakan
, kemudian menggunakan sisa dari pembagian , yang akan menghasilkan alamat
relatif untuk record. Hashing dengan sisa pembagian sangat mudah
diimplementasikan dalam bebrapa bahasa pemrograman yang memiliki fungsi
MOD.Alamat dihasilkan dari suatu nilai dengan perhitungan MOD.
b Truncation(Pemenggalan)
Satu fungsi Hashing Truncation (Pemenggalan)
melaukukan penghilangan digit k yang pertama atau yang terakhir dari sejumlah n
digit.suatu nomor dipenggal atau dihilangkan ketika beberapa digit awal atau
digit yang terakhir dipindahkan.
Keuntungan dari fungsi Hash Pemenggalan adalah :
- Cepat dan mudah dalam implementasikannya
Kerugiannya adalah :
- Terbatasnya ukuran ruang alamat (dalam hal ini
nomor ini lokasi penyimpanan berbeda) untuk kelipatan 10.
c Folding(Lipatan)
Teknik hashing folding (lipatan) teknik hashing
ini kunci dibagi menjadi beberapa bagian masing-masing (kecuali bagian awal
atau akhir ) memiliki jumlah digit yang sama. Bagian-bagian ini kemudian
dilipat antara satu bagian dengan bagian lain. Hasil penjumlahan setelah
dilipat dan digit dengan orde paling tinggi dipenggal menjadi alamat relatif.
d Multiplication(Perkalian)
Teknik ini dilakukan dengan cara baigan –
bagiannya seperti yang dilakukan di teknik folding, bagian dari salah satu
kunci bias dipilih untuk kemudian dikalikan. Hasilnya atau satu bagian yang
dipenggal merupakan alamat relatif dari record yang akan dialokasikan diman
akunci tersebut akan disimpan.
e Mid-Square
Mid Square teknik hashing ini nilai kunci
dikuadratkan, kemudian menentukan digit yang akan dikutip dari tengah, hasilnya
memberikan alamt relatif. Jiaka alamat relatif yang diinginkan sejumlah n
digit, maka digit dipenggal diantara kedua ujung hasil perpangkatan kunci,
menyisakan n digit dari tengah.
Penjelasan diatas adalah tentang metode pengurutan dengan menggunakan Metode Hash Middle Square. sekian yang bisa saya jelaskan. Mohon maaf atas kekurangannya Jika ada yang tidak dipahami atau ada diantara kalian yang ingin menambahkan atau cuman sekedar kritik dan saran tinggal comment dibawah ini.
Link Github :
0 komentar: