HASHING, TREE, BINARY TREE

HASHING

Teknik menyimpan dan mengambil kunci dengan cepat. Stringnya dibuat menjadi lebih pendek. Digunakan untuk mengindeks dan mengambil item dalam database, karena hash lebih pendek dan cepat. Tabel hash adalah pendistribusian kunci dalam array, tempat penyimpanan string asli. Fungsinya/function disebut hash function.

Metode hash string menjadi key:

- mid-square

- division (paling umum digunakan)

- folding

- digit extraction

- rotating hash

//MID - SQUARE

Nilai awal diambil kemudian dikuadratkan, lalu beberapa digit dari tengah diekstrak yang menjadi nilai baru, menghasilkan kunci dengan kecocokan tinggi bila nilai awal besar.

Contoh 3121 - kuadratnya=9740641 - tengahnya=406. Dengan binary 1001010-0101000010-1100001

//DIVISION

Memakai modulus. Nilai asli dibagi dengan jumlah lokasi/tabel yang tersedia.

Contoh nilai asli 12 dan 21, ukuran tabel=11

(12 mod 11)+1 = 1+1 = 2; simpan 12 di lokasi 2. Angka 2 menjadi nilai key.

(21 mod 11)+1 = 10+1 = 11; simpan 21 di lokasi 11.

//FOLDING

Nilai key dibagi menjadi beberapa bagian, tiap bagian punya jumlah digit yang sama dengan alamat relatif, kemudian dilipat (seperti kertas) lalu dijumlah.

Contoh nilai asli 123456, 234561, 321654.

123+654 = 777; simpan 123456 di 777.

234+153 = 387; simpan 234351 di 387.

321+456 = 777; simpan 321456 di 777. Terjadi kolisi dengan 123456.

//DIGIT EXTRACTION

Beberapa digit sebelumnya diekstrak.

Contoh 14568. Ambil digit ke 1 yaitu 1, 3 yaitu 5, dan 5 yaitu 8. Jadi disimpan di 158.

//ROTATING

Nilai asli dibalik lalu menjadi hash code.

Contoh 20021. Hash codenya adalah 12002.

COLLISION merupakan suatu peristiwa dimana 2 atau lebih nilai asli memiliki hash code yang sama. Penyelesainnya adalah dengan cara probing dan chaining.

Hubungan hash dengan blockchain adalah dalam sistem blockchain menggunakan hash pointer, yaitu pointer yang berisi hash data dari tempat/blok sebelumnya. Ilustrasinya adalah
seorang hacker menyerang blok 3 dan mencoba mengubah data. Karena sifat fungsi hash, sedikit perubahan dalam data akan mengubah hash secara drastis. Ini berarti bahwa setiap perubahan kecil yang dibuat di blok 3, akan mengubah hash yang disimpan di blok 2, sekarang pada gilirannya akan mengubah data dan hash blok 2 yang akan menghasilkan perubahan di blok 1 dan seterusnya dan seterusnya . Ini sepenuhnya akan mengubah rantai, yang tidak mungkin

TREE

tree adalah node tanpa looping. Node dapat disimpan dimana saja dan dihubungkan dengan pointer. Garis yang menghubungkan disebut edge. Total sub tree dari suatu node disebut degree.

BINARY TREE

Node yang lebih di atas disebut orangtua, yang di bawahnya disebut anak. Anak dari suatu node paling banyak adalah 2. Pada umumnya diterapkan dalam metode pencarian, untuk memudahkan pencarian. Jika ingin mencari anaknya, dapat dicari dari orangtuanya terlebih dahulu karena terkait. Dalam penyusunan yang rapat ini, jika sebuah simpul memiliki indeks i, anaknya dapat ditemukan pada indeks ke-2i+1 dan 2i+2.

Jenis - jenis pohon biner:

a. Pohon Biner Penuh

Semua simpul (kecuali daun) memiliki 2 anak dan tiap cabang memiliki panjang ruas yang sama.