HASHING TABLE & BINARY TREE

HASHING TABLE & BINARY TREE


Hashing adalah salah satu topik yang akan ditanyakan pewawancara kepada Anda dalam setiap wawancara karena dengan bantuan hashing, Anda dapat melakukan operasi penyisipan, penghapusan, dan pencarian dalam waktu O (1).

 Dasar-dasar Hashing


Hashing adalah cara untuk menyimpan data ke dalam beberapa struktur data (umumnya Tabel Hash digunakan) sedemikian rupa sehingga operasi dasar pada data tersebut yaitu penyisipan, penghapusan, dan pencarian dapat dilakukan dalam waktu O (1). Di sini, data disimpan dalam bentuk pasangan nilai kunci, yaitu untuk setiap data, Anda akan penghapusan, dan pencarian data Anda akan dilakukan. menetapkan beberapa kunci dan berdasarkan pada kunci itu penyisipan,
HASHING TABLE


Dalam Tabel Hash, untuk menyimpan data kami menggunakan fungsi Hash yang mengambil data sebagai input dan berdasarkan data itu menghasilkan beberapa kunci dan kami menyimpan data berdasarkan kunci itu.


Data kami dapat berupa apa pun, misalnya dalam bentuk bilangan bulat atau string atau tipe data lainnya. Tetapi tujuan utama kami adalah untuk mengubah data itu menjadi bilangan bulat dengan melakukan beberapa preprocessing dan kemudian menerapkan beberapa fungsi hash untuk itu dan memetakan hasilnya dalam tabel hash.
Mari kita lihat bagaimana kita bisa melakukan Penyisipan, Penghapusan, dan Pencarian di O v(1) menggunakan Tabel Hash:

Penyisipan  : Di sini, kami menggunakan fungsi hash, jadi fungsi hash akan menghasilkan kunci dalam waktu O (1) karena kami menggunakan perhitungan matematika dalam fungsi hash dan kami dapat langsung pergi ke alamat itu tanpa traversal apa pun. Jadi, kompleksitas waktu keseluruhan dari penyisipan data dalam tabel hash adalah O (1).
Penghapusan : Untuk menghapus elemen dari tabel hash, kita dapat menggunakan fungsi hash untuk menemukan posisi elemen di tabel hash dan langsung menuju ke tempat itu dan langsung menghapus item itu. Jadi, operasi penghapusan keseluruhan dapat dilakukan di O (1).

Pencarian : Fungsi hash dapat digunakan untuk mencari indeks data tertentu. Yang perlu Anda lakukan hanyalah meneruskan nilai data dalam fungsi hash dan fungsi hash akan mengembalikan indeks tempat data disimpan. Jadi, operasi pencarian dapat dilakukan dalam O (1) waktu.

Berikut perbedaan HASH TABLE dengan BINARY SEARCH TREE

SOURCE : afteracademy.com

Comments

Post a Comment

Popular posts from this blog

Heaps

Image
Heaps adalah salah satu bentuk tree yang memenuhi syarat heap. jika anak node lebih besar atau sama dengan node tersebut maka disebut min-heap. lalu jika  sebuah node nilainya lebih besar atau sama dengan anak node tersebut disebut max-heap, adapun gabungan dari kedua heap disebut  min-max heap dimana dalam baris node atas lebih kecil dari node bawahnya lalu node bawahnya lagi lebih besar dan seterusnya. Min Heap & Max Heap Min Max Heap
Read more

LINKED LIST

Image
   Linked list adalah  Koleksi linear dari data, yang disebut sebagai  nodes ,  dimana setiap   node akan menunjuk pada  node  lain melalui sebuah  pointer, linked list juga merupakan k umpulan   nodes  yang merepresentasikan sebuah  sequence.   Dalam linked list terbagi menjadi 2 yaitu single linked list dan doubly linked list. Single linked list adalah sebuah linked list yang menggunakan sebuah variabel pointer saja untuk menyimpan banyak data dengan suatu daftar isi yang saling berhubungan, sedangkan, double linked list adalah mengatasi kelemahan-kelemahan dalam single linked list contohnya dengan dua buah pointer yaitu prev dan next. 1. Single Linked List     Single Linked List merupakan suatu linked list yang hanya memiliki satu varuabel pointer saja. Dimana pointer tersebut menunjuk ke node selanjutnya.Biasanya field pada tail menunjuk ke NULL Single Linked List merupakan suatu linked lis...
Read more