- Hashing adalah mengubah suatu string menjadi suatu bilangan dengan suatu fungsi. Misalkan kita memiliki string "abca", dan fungsi f yang memetakan string ke bilangan bulat berikut:
f(S) = (
(banyaknya 'a')*1 +
(banyaknya 'b')*2 +
(banyaknya 'c')*3 +
... +
(banyaknya 'z')*26
) mod 1000000
Artinya:
f("abca") = (2*1 + 1*2 +
1*3 + 0*4 + 0*5 + ... + 0*26) mod 1000000
= 7
Kita berhasil mengubah string "abca" menjadi sebuah angka, yaitu 7. Hal ini juga akan dilakukan untuk setiap nama mahasiswa dalam setiap operasi; sebelumnya di-hash terlebih dahulu. Dengan demikian, direct addressing table dapat kembali digunakan! Kini kompleksitas untuk setiap operasi adalah O(K), dengan K adalah kompleksitas menghitung nilai hash melalui fungsi hashing. Untuk contoh di atas, K = panjang string. Jika panjang setiap string cukup kecil, setiap operasi bisa dianggap O(1).
- Hashing
Dapat diartikan sebagai aktivitas
untuk mengubah suatu objek menjadi serangkaian angka/karakter/sejenisnya. Seperti
contoh kita melakukan hash pada string menjadi bilangan.
T["stefanus"] = 3;
printf("%d\n",
T["stefanus"]);
- Pada ilmu komputer, tabel seperti ini disebut sebagai hash table. Struktur data ini erat kaitannya dengan konsep "key value". Key adalah hal yang menjadi indeks, dan value adalah nilai yang berasosiasi dengannya.
-
Operasi
minimal yang perlu didukung oleh hash table adalah:
- Diberikan key X
dan value Y, catat bahwa value dari X adalah Y. Operasi ini
dapat dianggap "T[X] = Y".
- . Diberikan key X,
cari value-nya. Operasi ini dapat dianggap seperti mengakses
"T[X]".
Ada
banyak cara untuk mengaitkan string menjadi kunci. Berikut ini adalah beberapa
metode penting untuk membangun fungsi hash.
- Mid-square
- Pembagian
(paling umum)
- Melipat
- Ekstraksi
Digit
- Rotasi Hash
2. Pembagian : Membagi
string / pengidentifikasi dengan menggunakan operator modulus.
Ini adalah metode hashing integer
yang paling sederhana x.
3. Melipat : Partisi string
/ identifier menjadi beberapa bagian, lalu tambahkan bagian bersama-sama untuk
mendapatkan kunci hash
4.Ekstrasi Digit : Digit
yang ditentukan sebelumnya dari nomor yang diberikan dianggap sebagai alamat
hash.
5.Rotasi Hash : Gunakan
metode hash (seperti metode pembagian atau mid-square). Setelah mendapatkan
kode / alamat hash dari metode hash, lakukan rotasi. Rotasi dilakukan dengan
menggeser digit untuk mendapatkan alamat hash baru.
Collision
dapat menggunakan teknik :
- Closed
hashing
Contoh teknik yang
digunakan adalah linear/quadratic probing. Saya tidak menjelaskan bagian
ini karena menurut saya kurang cocok digunakan saat kompetisi.
- Open
hashing
Idenya sederhana. Kita
dapat mengganti array pada direct addressing table menjadi
"array of linked list". Misalnya "array of linked list" ini
bernama T. Setiap elemen pada linked list T[i] menyimpan sejumlah
pasangan key dan value untuk memiliki nilai hash key berupa
i.
Ketika kita hendak menyimpan suatu nilai ke T[i] dan terjadi collision (sudah ada isinya), kita cukup tambahkan elemen baru pada T[i].
Ketika kita hendak menyimpan suatu nilai ke T[i] dan terjadi collision (sudah ada isinya), kita cukup tambahkan elemen baru pada T[i].
Pohon adalah struktur
data non-linear yang mewakili hubungan hierarkis di antara objek data
Beberapa hubungan pohon dapat
diamati dalam struktur direktori atau hierarki organisasi.
- Node
di atas disebut sebagai root.
- Garis
yang menghubungkan induk ke anak adalah edge.
- Node
yang tidak memiliki anak disebut daun.
- Node
yang memiliki orang tua yang sama disebut saudara.
- Derajat
simpul adalah total sub pohon simpul.
- Tinggi
/ Kedalaman adalah tingkat maksimum node dalam pohon.
- Jika
ada garis yang menghubungkan p ke q, maka p disebut leluhur q, dan q adalah
turunan dari p.
Perfect binary tree :
Complete binary tree :
Skewed binary tree :
Property Binary tree : Jumlah
maksimum node pada level k dari pohon biner adalah 2^k.
- Tree expression prefix :
char s[MAXN];
int T = 0;
void f(struct tnode *curr) {
if
( is_operator(s[T]) ) {
T++;
curr->left = newnode(s[T]);
f(curr->left);
T++;
curr->right = newnode(s[T]);
f(curr->right);
}
}
}
- Tree
expression postfix transversal :
void postfix(struct tnode *curr) {
if ( curr->left
!= 0 ) postfix(curr->left);
if (
curr->right != 0 ) postfix(curr->right);
printf( “%c“, curr->chr );
printf( “%c“, curr->chr );
}
- Tree
expresion infix transversal :
void infix(tnode *curr)
{
if ( is_operator(curr->chr) )
putchar( '(' );
if ( curr->left != 0 )
infix(curr->left);
printf( "%c",
curr->chr );
if ( curr->right != 0 )
infix(curr->right);
if ( is_operator(curr->chr) )
putchar( ')' );
}
Contoh Implementasi hashing dalam penambangan :
Contoh Implementasi hashing dalam penambangan :
Hashing in mining: The crypto puzzle.
Ketika kita mengatakan “menambang”, itu pada dasarnya berarti mencari blok baru untuk ditambahkan di blockchain. Penambang dari seluruh dunia terus bekerja untuk memastikan bahwa rantai itu terus tumbuh. Sebelumnya dulunya mudah bagi orang untuk menambang menggunakan hanya laptop mereka, tetapi seiring waktu, orang mulai membentuk kolam penambangan untuk menggabungkan kekuatan komputer mereka dan menambang lebih efisien.
Namun, ini bisa menjadi masalah. Ada batasan untuk setiap mata uang digital, misalnya. untuk bitcoin, hanya 21 juta. Hanya ada 21 juta bitcoin di luar sana. Jika para penambang diizinkan untuk melanjutkan, pada tingkat ini, mereka akan menangkap semua bitcoin yang ada. Selain itu, perlu ada batas waktu khusus di antara pembuatan setiap blok. Untuk bitcoin, batas waktu di antara pembuatan blok adalah 10 menit. Jika blok diizinkan dibuat lebih cepat, itu akan menghasilkan:
- Lebih banyak tabrakan: Lebih banyak fungsi hash akan dihasilkan yang pasti akan menyebabkan lebih banyak tabrakan.
- Lebih banyak blok yatim: Jika banyak penambang kelebihan penambangan, mereka akan menghasilkan blok baru secara bersamaan. Ini akan menghasilkan atau lebih banyak blok tidak menjadi bagian dari rantai utama dan menjadi blok yatim.
Jadi, untuk membatasi pembuatan blok, tingkat kesulitan tertentu diatur. Penambangan seperti permainan, Anda memecahkan teka-teki dan Anda mendapatkan hadiah. Kesulitan pengaturan membuat teka-teki itu jauh lebih sulit untuk dipecahkan dan karenanya lebih memakan waktu. Bitcoin WRT target kesulitan adalah string 64-karakter (yang sama dengan output SHA-256) yang dimulai dengan sekelompok nol. Sejumlah nol meningkat seiring meningkatnya tingkat kesulitan. Tingkat kesulitan berubah setelah setiap blok 2016.
Referensi :
binusmaya
https://selembardigital.com/apa-itu-hashing-di-bawah-tudung-blockchain/