Hashing, Hash Table, and Binary Tree

Christophorus Wilson
2301869273

Hashing

Hashing adalah semua method yang digunakan untuk menyimpan dan mengambil key dengan cepat. Di dalam hashing, string diubah menjadi bentuk string yang lebih pendek untuk mewakili string aslinya. Hashing digunakan untuk menjadi index dan mengambil elemen di database karena pencariannya lebih cepat menggunakan hashed key dibandingkan dengan value aslinya.

Distribusi hashing ke dalam sebuah array disebut dengan Hash Table dengan menggunakan fungsi yang disebut dengan Hash Function.

Hash Table

Hash Table adalah array tempat kita menyimpan value asli dari sebuah string. Index dari array tersebut adalah hashed key yang diambil dari value asli string tersebut.

Dari gambar diatas dapat dilihat bahwa apple diletakan di index 0 setelah  melewati proses Hash Function.

Hash Function

Ada beberapa cara untuk mengubah suatu string menjadi sebuah hashed key.

àMid-square

àDivision (paling sering digunakan)

àFolding

àDigit Extraction

àRotating Hash

Collision

Dalam metode penentuan hashed key, dapat terjadi situasi dimana beberapa data memuat hashed key yang sama. Hal ini disebut dengan Collision. Collision dapat diatasi dengan 2 cara.

èLinear Probing

*…%7 karena total elemen yang dapat disimpan adalah 7.

Proses 1 : Elemen 76. 76%7=6. Simpan di index 6.

Proses 2 : Elemen 93. 93%7=2. Simpan di index 2.

Proses 3 : Elemen 40. 40%7=5. Simpan di index 5.

Proses 4 : Elemen 47. 47%7=5. Seharusnya disimpan di index 5, namun karena index 5 telah terisi, maka cek index selanjutnya. Index 6 juga terisi, maka kembali ke index 0. Index 0 kosong, maka disimpan di index 0.

Dst.

Maka dapat disimpulkan bahwa metode linear probing adalah melintasi semua index (berawal dari index yang ditentukan dari hashed key) untuk mencari index yang kosong. Oleh karena itu, apabila terjadi banyak collision, linear probing akan memakan waktu yang lebih lama untuk menemukannya.

è Chaining

 

Asumsikan bahwa index 1, 3, 4, 5 telah terisi dengan elemen diatas. Kemudian elemen selanjutnya terjadi collision dengan elemen yang telah tersimpan.

Jacob memiliki hashed key yang sama dengan John, maka John menunjuk Jacob .

Martha memiliki hashed key yang  sama dengan Janet, maka Janet menunjuk Martha.

Claire memiliki hashed key yang sama dengan Janet dan Martha, maka Martha menunjuk Claire.

Maka dapat disimpulkan bahwa metode Chaining adalah metode yang menggunakan konsep Linked List, yaitu dengan menghubungkan sebuah data yang ada di dalam array dengan data yang mengalami collision.

Binary Tree

Sebuah tree adalah struktur data yang memperlihatkan hubungan antar objek data. Binary tree adalah sebuah tree yang setiap nodenya memiliki paling banyak 2 child nodes.

Struktur data binary tree :

struct tnode {

                char chr;

                struct tnode *left;

                struct tnode *right;
};