HASH TABLE & BINARY TREE

HASH TABLE & BINARY TREE

A. Hashing

adalah suatu teknik yang digunakan untuk menyimpan dan menggunakan kembali kunci kunci dengan cara yang cepat.

-Dalam hashing, suatu string karakter dapat diubah menjadi panjang nilai yang lebih pendek atau kunci yang mewakili string yang asli.

• Hashing dapat digunakan sebagai index dan mengembaliken barang dalam bentuk database karena lebih cepat untuk mencari barang menggunakan kunci hashed dari pada mencari nilai aslinya.
• Hashing dapat juga diartikan sebagai konsep mendistribusikan kunci-kunci dalam suatu array yang disebut hash table dengan menggunakan fungsi tertentu yang disebut hash function.

Hash Function

Sebuah hash function adalah sebuah fungsi yang bisa digunakan untuk memetakan sebuah data set dari ukuran yang berubah-ubah ke sebuah data set dari ukuran yang pasti, yang jatuh ke hash table. Nilai yang dikembalikan oleh sebuah hash function disebut hash values, hash codes, hash sums, atau hanya hashes.

Ciri-ciri hash function yang baik:

1. Mudah untuk memetakan data, harus mudah untuk dipetakan dan harus tidak menjadi algoritme sendiri.
2. Distribusi yang seragam, harus memberikan distribusi yang seragam terhadap hash table dan tidak menghasilkan pengelompokan.
3. Sedikit tabrakan, tabrakan terjadi ketika sepasang elemen dipetakan ke hash value yang sama

Hash Table

Hash Table adalah sebuah data structure yang digunakan untuk menyimpan informasi. Informasi tersebut memiliki dua komponen utama, yaitu Key dan Value. Hash table menggunakan hash function untuk mengcompute sebuah index ke dalam sebuah array di mana sebuah elemen akan dimasukkan atau dicarikan.

B. Binary Tree

Tidak seperti array, linked list, stack dan queues, yaitu data struktur linear, trees ini lebih seperti data struktur hierarki. Sebuah binary tree adalah sebua pohon data struktur yang setiap cabangnya memiliki setidaknya 2 anak, yang di referensi sebagai anak kiri dan anakakanan. Biasanya binary tree dipakai dengan menggunakan Links.

Representasi binary tree biasanya seperti suatu pointer dari cabang bagian paling atas sebuah pohon. Jika tree tersebut kosong, maka nilai dari akarnya adalah NULL, sebuah cabang binary tree daoat berisi data, pointer dari anak kiri dan pointer dari anak kanan.

Binary tree dapat dilalui dari kiri-akar-kanan(inorder), preorder(akar-kiri-kanan) dan postorder(kiri-kanan-akar).

Node yang terletak di paling atas tree disebut dengan root.

Stack dan Queue dalam linked list

Keduanya adalah struktur data yang berfungsi untuk menyimpan data secara berurutan. Perbedaannya terdapat pada sifatnya.

Sifat dari Stack adalah LIFO (Last In First Out). Analoginya adalah seperti buku yang ditumpuk, buku yang terakhir kali diletakkan (paling atas)  adalah yang pertama kali diambil.

Sedangkan sifat dari Queue adalah FIFO (First In First Out). Analoginya seperti mengantri di kasir pada umumnya. Orang yang pertama kali masuk adalah yang pertama kali dilayani.

Stack adalah linear data structure yang elemennya hanya dapat di insert dan di delete dari satu sisi, yang disebut top. 

Stack sendiri memiliki konsep yang mirip dengan tumpukan piring, dimana jika kita ingin meletakkan piring, maka kita akan meletakan piring di paling atas (insert), serta ketika ingin mencuci piring tersebut, maka piring yang kita ambil adalah piring paling atas juga (delete).

Prinsip yang dipakai dalam stack adalah LIFO (Last In First Out), artinya elemen yang dimasukkan terakhir adalah yang dikeluarkan pertama.

Fungsi insert dalam stack dinamakan push operation, sedangkan fungsi delete dalam stack dinamakan pop operation.

Stack Operations

Push()   : memasukkan elemen ke dalam stack

Pop()     : menghapus/menghilangkan elemen dari stack

Top()     : menunjukkan elemen paling atas dari sebuah stack

Queue Operations

Push()   : memasukkan elemen di index paling belakang

Pop()     : menghapus/menghilangkan elemen dari index paling depan

Front()  : menunjukkan elemen dari index paling depan

linked list 

linked list dalam bahasa baku Indonesia diartikan sebagai "Seranai berantai". 

Dalam dunia komputer linked list merupakan sebuah struktur data untuk menyimpan beberapa objek secara terhubung, sehingga mempermudah penambahan, pengurangan, dan pencarian terhadap kumpulan data.

linked list adalah suatu struktur data linier. Linked List sendiri  dibentuk secara dinamik. Pada awal program dijalankan elemen linked list belum data. Elemen linked list (disebut node) dibentuk sambil jalan sesuai instruksi. Node yang ada pada Linked List diakses dengan cara menggunakan pointer yang mengacu (menunjuk) ke node tersebut.

Macam-macam linked list adalah sebagai berikut:

1. Single linked list
ciri ciri:
- Hanya memiliki 1 arah ( tidak berbalas ) ke penghubung ke node lain
- Tail akan selalu menunjuk NULL

    contoh gambar single linked list

2. Doubly linked list / double linked list
ciri ciri:
-  Setiap node memiliki 2 arah yang menunjuk node sebelum nya dan node selanjut nya.
- Head dan tail akan selalu menunjuk NULL


    contoh gambar doubly linked list

3. Circular linked list
ciri ciri:
- Tidak memiliki pointer yang menunjuk NULL

- Tail selalu menunjuk ke head dan head akan selalu menunjuk tail apabila
   juga bersifat double linked list

    Ada 2 jenis Circular Linked List, yaitu

-Circular Single Linked List

-Circular Double Linked List