Hashing and Hash Tables, Trees & Binary Tree

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.

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.

Misalnya, ada 267 (8.031.810.176) string dengan panjang 7 karakter hanya terdiri dari huruf kecil saja.

Hash Function

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

• Mid-square
• Division (paling umum)
• Folding
• Digit Extraction
• Rotating Hash

Mid-square

Kode hash mid-square diproduksi dengan mengkuadratkan input dan mengekstraksi sejumlah digit atau bit tengah yang sesuai. Misalnya, jika inputnya 123.456.789 dan tabel hash ukuran 10.000, mengkuadratkan kunci menghasilkan 1.524157875019e16, sehingga kode hash diambil sebagai angka tengah 4 digit dari angka 17 digit (mengabaikan angka tinggi) 8750. Metode kuadrat menghasilkan kode hash yang masuk akal jika tidak ada banyak angka nol di depan atau di belakang. Ini adalah varian dari hashing multiplikasi, tetapi tidak sebagus kunci arbitrer bukan pengganda yang baik.

Division

Teknik standar adalah dengan menggunakan fungsi modulo pada kunci, dengan memilih pembagi M yang merupakan bilangan prima yang dekat dengan ukuran tabel, jadi h (K) = K  mod M. Ukuran tabel biasanya adalah kekuatan 2. Ini memberikan distribusi dari {0, M-1}. Ini memberikan hasil yang baik pada sejumlah besar set kunci. Kelemahan signifikan hashing divisi adalah bahwa divisi diprogram secara mikro pada sebagian besar arsitektur modern termasuk x86 dan bisa 10 kali lebih lambat daripada multiply. Kelemahan kedua adalah bahwa itu tidak akan memecah kunci berkerumun. Misalnya, tombol 123000, 456000, 789000, dll. Modulo 1000 semua peta ke alamat yang sama. Teknik ini bekerja dengan baik dalam praktik karena banyak set kunci sudah cukup acak, dan probabilitas bahwa set kunci akan berulang dengan bilangan prima yang besar kecil.

Folding

Kode hash lipat dihasilkan dengan membagi input menjadi n bagian m bit, di mana 2 ^ m adalah ukuran tabel, dan menggunakan operasi bitwise yang mempertahankan paritas seperti ADD atau XOR, untuk menggabungkan bagian. Operasi terakhir adalah mask atau shift untuk memotong bit berlebih pada ujung tinggi atau rendah. Misalnya, untuk ukuran tabel 15 bit dan nilai kunci 0x0123456789ABCDEF, ada 5 bagian 0x4DEF, 0x1357, 0x159E, 0x091A dan 0x8. Menambahkan, kami memperoleh 0x7AA4, nilai 15-bit.

Digit Extraction

Digit Extraction, digit yang dipilih diekstraksi dari kunci dan digunakan sebagai alamat. Misalnya, menggunakan enam digit nomor karyawan kami untuk hash ke alamat tiga digit (000 hingga 999), kami dapat memilih digit pertama, ketiga, dan keempat (dari kiri) dan menggunakannya sebagai alamat

Rotating 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)

Collision

Apa yang terjadi jika kita ingin menyimpan string ini menggunakan fungsi hash sebelumnya (gunakan karakter pertama dari setiap string)

mendefinisikan, mengapung, exp, char, atan, ceil, acos, floor.

Ada beberapa string yang memiliki hash-key yang sama, itu float dan floor (hash-key: 5), char dan ceil (hash-key: 2).

Ini disebut Collision. Bagaimana kita bisa menangani ini?

Ada dua cara umum untuk menangani tabrakan:

• Linear Probing

Cari slot kosong berikutnya dan letakkan talinya di sana.  Pemeriksaan linear memiliki yang buruk kompleksitas pencarian jika ada banyak tabrakan. Tabel "melangkah" di sebelah kanan jelaskan berapa banyak loop / langkah diperlukan untuk menemukan string.

• Chaining

Masukkan string ke dalam slot sebagai daftar rantai (daftar tertaut). Dalam rantai, kami menyimpan setiap string dalam rantai (daftar tertaut). Jadi jika ada Collision, kita hanya perlu beralih pada rantai itu.

Trees & Binary Tree

Tree

Tree adalah struktur data non-linier 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.

Konsep Tree

• Node di atas disebut sebagai root.
• Garis yang menghubungkan parent ke child adalah edge.
• Node yang tidak memiliki anak disebut leaf.
• Node yang memiliki parent yang sama disebut siblings.
• Tingkat node adalah total subtree dari node.
• 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 Binary Tree

Binary tree adalah struktur data rooted tree di mana setiap node memiliki paling banyak dua anak. Kedua child itu biasanya dibedakan sebagai child kiri dan child kanan. Node yang tidak memiliki child disebut leaf.

Contoh Binary tree dengan 9 node, yang di-root pada node yang bernilai 18. leaf adalah node yang berisi 9, 12, 10 dan 23.

Jenis-jenis Binary Tree

• 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 yang sempurna adalah pohon biner yang 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 jauh lebih jauh dari akar daripada daun lainnya (skema penyeimbangan yang berbeda memungkinkan definisi yang berbeda dari "jauh lebih jauh").