Hashing table & Binary Tree

Hashing Table

Apa itu Hashing?

Hashing adalah teknik yang digunakan untuk menyimpan dan mengambil kunci dengan cepat. Dalam hashing, string karakter ditransformasikan menjadi nilai panjang yang biasanya lebih pendek atau kunci yang mewakili string asli.

Hashing digunakan untuk mengindeks dan mengambil item dalam database karena lebih cepat menemukan item menggunakan kunci hash yang lebih pendek daripada menemukannya menggunakan nilai asli.

Hashing juga dapat didefinisikan sebagai konsep mendistribusikan kunci dalam array yang disebut tabel hash menggunakan fungsi yang telah ditentukan yang disebut fungsi hash.

Apa itu Hash Table?

Tabel hash adalah tabel (larik) tempat kami menyimpan string asli. Indeks tabel adalah kunci hash sementara nilainya adalah string asli.

Ukuran tabel hash biasanya beberapa urutan besarnya lebih rendah dari jumlah total string yang mungkin, sehingga beberapa string mungkin memiliki kunci hash yang sama.

Fungsi Hash

Ada banyak cara untuk mengaitkan string menjadi kunci. Berikut ini adalah beberapa metode penting untuk membangun fungsi hash.

a. Mid-square

b. Divisi (paling umum)

c. Fold

d. Ekstraksi Digit

e. Rotasi Hash

a) Apa itu Mid Square?

Kuadratkan string / identifier dan kemudian gunakan jumlah bit yang sesuai dari tengah kotak untuk mendapatkan hash-key.

Jika kuncinya adalah string, itu dikonversi ke angka.

Langkah:

 Kuadratkan nilai kunci. (k2)

 Ekstrak bit tengah hasil yang diperoleh pada Langkah 1

Fungsi: h (k) = s

k = kunci

s = kunci hash diperoleh dengan memilih r bit dari k2

b) Divisi/Division (paling umum)

Bagilah string / identifier dengan menggunakan operator modulus.

Ini adalah metode hashing integer yang paling sederhana x.

Fungsi: h (z) = z mod M

z = kunci

M = nilai yang digunakan untuk membagi kunci, biasanya menggunakan bilangan prima, ukuran tabel atau ukuran memori yang digunakan.

c) Fold

Partisi string / identifier menjadi beberapa bagian, lalu tambahkan bagian bersama-sama untuk mendapatkan kunci hash

Langkah:

-Bagilah nilai kunci menjadi beberapa bagian

-Tambahkan bagian individual (biasanya carry terakhir diabaikan)

d) Ekstrasi Digit

Digit yang ditentukan sebelumnya dari nomor yang diberikan dianggap sebagai alamat hash.

Contoh:

-Pertimbangkan x = 14.568

-Jika kita mengekstrak digit 1, 3, dan 5, kita akan mendapatkan kode hash: 158.

e) 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.

Contoh:

Alamat hash yang diberikan = 20021

Hasil rotasi: 12002 (lipat digit)

Apa itu Collision?

Keterbatasan tabel hash menyebabkan ada dua angka yang jika dimasukkan ke dalam fungsi hash maka menghasilkan nilai yang sama. Hal ini disebut dengan collision.

contoh: Kita ingin memasukkan angka 6 dan 29.

             Hash(6) = 6 % 23 = 6

             Hash(29)= 29 % 23 = 6

Pertama-tama anggap tabel masih kosong. Pada saat angka 6 masuk akan ditempatkan pada posisi indeks 6, angka kedua 29 seharusnya ditempatkan di indeks 6 juga, namun karena indeks ke-6 sudah ditempati maka 29 tidak bisa ditempatkan di situ, di sinilah terjadi collision. Cara penanganannya bermacam-macam :

 1. Linear Probing

Pada saat terjadi collision, maka akan mencari posisi yang kosong di bawah tempat terjadinya collision, jika masih penuh terus ke bawah, hingga ketemu tempat yang kosong. Jika tidak ada tempat yang kosong berarti HashTable sudah penuh

2. Chaining

Tambahkan key and entry di manapun dalam list (lebih mudah dari depan)

Kerugian:   Overhead pada memory tinggi jika jumlah entry sedikit

Keunggulan dibandingkan open addressing:

-          Proses insert dan remove lebih sederhana

-          Ukuran Array bukan batasan (tetapi harus tetap meminimalisir collision: buat ukuran tabel sesuai dengan jumlah key dan entry yang diharapkan)

Kegunaan Hashing table dalam dunia Blockchain

Dalam protokol bitcoin, fungsi hash adalah bagian dari algoritma hashing blok yang digunakan untuk menulis transaksi baru ke dalam blockchain melalui proses mining.

Dalam bitcoin mining, input untuk fungsi ini adalah semua transaksi terbaru, yang belum dikonfirmasi (bersama dengan beberapa input tambahan yang berkaitan dengan stempel waktu dan referensi ke blok sebelumnya).

Dalam contoh kode di atas, kami telah melihat bahwa mengubah sebagian kecil input untuk fungsi hash menghasilkan keluaran yang sama sekali berbeda. Properti ini sangat penting untuk algoritma 'bukti kerja' yang terlibat dalam mining: untuk berhasil 'menyelesaikan' blok, miner mencoba untuk menggabungkan semua input dengan sepotong data input mereka sendiri sedemikian rupa sehingga hash yang dihasilkan dimulai dengan sejumlah nol.

Sebagai demonstrasi dasar, kami dapat mencoba 'mining' dengan fungsi hash Python kami dengan secara manual menambahkan tanda seru setelah "CoinDesk rocks!" sampai kita menemukan hash yang dimulai dengan nol tunggal.

>>> hash ("CoinDesk rocks !!")

66925f1da83c54354da73d81e013974d

>>> hash ("CoinDesk rocks !!!")

c8de96b4cf781a6373766c668ceac0f0

>>> hash ("CoinDesk rocks !!!!")

9ea367cea6a2cc4a6f5a1d9a334d0d9e

>>> hash ("CoinDesk rocks !!!!!")

b8d43387d98f035e2f0ac49740a5af38

>>> hash ("CoinDesk rocks !!!!!!")

0fe46518541f4739613b9ce29ecea6b6 => ASK!

Tentu saja, menyelesaikan hash untuk blok bitcoin - yang pada saat penulisan harus dimulai dengan 18 nol - memerlukan jumlah perhitungan yang sangat besar (dan karenanya kekuatan pemrosesan gabungan semua komputer dalam jaringan masih membutuhkan waktu sekitar 10 menit untuk pecahkan blok).

Ini adalah kebutuhan akan kekuatan pemrosesan dalam jumlah besar ini yang berarti bitcoin baru di mining dalam jangka waktu yang lama, tidak sekaligus.

Untuk mendapatkan bitcoin melalui mining, Anda harus melakukan sejumlah besar pekerjaan yang diperlukan untuk menyelesaikan blok - dan dengan mendapatkan hadiah itu, Anda mengunci semua transaksi baru menjadi blok, yang ditambahkan ke permanen catatan semua transaksi sebelumnya: blockchain.

Sumber: https://www.coindesk.com/bitcoin-hash-functions-explained

Binary Tree

Pengertian pohon
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 pohon tidak perlu disimpan secara berdekatan dan dapat disimpan di mana saja dan dihubungkan oleh pointer. Pohon adalah koleksi dari 1 atau lebih node.

Konsep pohon:
- Node di atas disebut sebagai root.
- Garis yang menghubungkan induk ke anak adalah edge.
- Node yang tidak memiliki anak disebut leaf.
- Node yang memiliki orang tua yang sama disebut sibling.
- 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.

Konsep pohon binary
Binary tree adalah struktur data rooted tree di mana setiap node memiliki paling banyak dua anak.
Kedua anak itu biasanya dibedakan sebagai anak kiri dan anak kanan.

Node yang tidak memiliki anak disebut daun.

Jenis pohon binary
-PERFECT binary tree adalah pohon biner di mana setiap level berada pada kedalaman yang sama.
-COMPLETE binary tree adalah pohon biner di mana setiap level, kecuali mungkin yang terakhir, terisi penuh, dan semua node sejauh mungkin dibiarkan. Pohon biner sempurna adalah pohon biner lengkap.
-SKEWED binary tree adalah pohon biner di mana setiap node memiliki paling banyak satu anak.
-BALANCED binary tree adalah pohon biner di mana tidak ada daun yang lebih jauh dari akar daripada daun lainnya (skema penyeimbangan yang berbeda memungkinkan definisi yang berbeda tentang "lebih jauh").