Hashing & Binary Tree

Hasing Table

• Hash Table adalah tabel (array) tempat kita simpan string aslinya. Indeks dari tabel adalah kunci hash saat nilainya string asli. 

Hash Function

1. Division

   Bagi String atau Identifier dengan menggunakan modulus.

2. Mid-square

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

3. Folding

   Partisi string / identifier menjadi beberapa bagian, lalu tambahkan bagian bersama-sama untuk mendapatkan hashkey.

   • Division 

     Metode ini membagi kunci dengan Modulus dan kemudian menggunakan sisa yang diperoleh sebagai indeks dalam tabel hash.

   • Mid-square

     Metode Mid Square bekerja dalam dua langkah:
     • Menguadratkan Value dari key
     •  Ekstrak digit tengah hasilnya diperoleh pada Langkah 1 

   • Folding

     Metode Folding bekerja dalam dua langkah:
     
     • Membagi nilai kunci menjadi beberapa bagian di mana setiap bagian memiliki yang sama jumlah digit kecuali bagian terakhir yang mungkin memiliki digit lebih rendah dari bagian lain.
     • Tambahkan bagian individual. Itu didapat jumlah dari part1 + part2 + ... + bagian n. Itu nilai hash yang dihasilkan dengan mengabaikan yang terakhir bawa, jika ada.