Hash Middle Square_Muh Akbar Tamrin_1144012

22:09 Pemrograman Web 0 Comments



Contoh Hasil Dari Middle Square :

#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: