Hashing Table & Binary Tree

By Emanuel Lienardi - 8:05 AM

Hash Table

Hashing adalah teknik yang digunakan untuk secara unik mengidentifikasi objek tertentu dari sekelompok objek serupa. Beberapa contoh bagaimana hashing digunakan dalam kehidupan kita termasuk:

Di universitas, setiap siswa diberi nomor gulungan unik yang dapat digunakan untuk mengambil informasi tentang mereka.
Di perpustakaan, setiap buku diberi nomor unik yang dapat digunakan untuk menentukan informasi tentang buku, seperti posisinya yang tepat di perpustakaan atau pengguna yang telah dikeluarkannya, dll.

Dalam kedua contoh ini, siswa dan buku di hash ke nomor unik.

Asumsikan bahwa Anda memiliki objek dan Anda ingin menetapkan kunci untuk mempermudah pencarian. Untuk menyimpan pasangan kunci / nilai, Anda dapat menggunakan larik sederhana seperti struktur data tempat kunci (bilangan bulat) dapat digunakan secara langsung sebagai indeks untuk menyimpan nilai. Namun, dalam kasus di mana kunci besar dan tidak dapat digunakan secara langsung sebagai indeks, Anda harus menggunakan hashing .

Dalam hashing, kunci besar dikonversi menjadi kunci kecil dengan menggunakan fungsi hash . Nilai-nilai ini kemudian disimpan dalam struktur data yang disebut tabel hash . Gagasan hashing adalah untuk mendistribusikan entri (pasangan kunci / nilai) secara seragam di seluruh array. Setiap elemen diberi kunci (kunci yang dikonversi). Dengan menggunakan kunci itu Anda dapat mengakses elemen dalam O (1) waktu. Menggunakan kunci, algoritma (fungsi hash) menghitung indeks yang menunjukkan di mana entri dapat ditemukan atau dimasukkan.

Hashing diimplementasikan dalam dua langkah:

Elemen dikonversi menjadi integer dengan menggunakan fungsi hash. Elemen ini dapat digunakan sebagai indeks untuk menyimpan elemen asli, yang jatuh ke tabel hash.
Elemen disimpan di tabel hash di mana ia dapat dengan cepat diambil menggunakan kunci hash.
hash = hashfunc (key)
index = hash% array_size

Dalam metode ini, hash tidak tergantung pada ukuran array dan kemudian dikurangi menjadi indeks (angka antara 0 dan array_size - 1) dengan menggunakan operator modulo (%).

Fungsi hash adalah fungsi matematis yang mengubah nilai input numerik menjadi nilai numerik yang terkompresi. Maksudnya bertujuan mengkompresi nilai numerik yang diinputkan. Inputan fungsi hash mempunyai panjang yang beragam, namun outputan nilai hash akan selalu mempunyai panjang yang tetap. Nilai yang dikembalikan oleh fungsi hash disebut message digest atau hanya nilai hash.

Fungsi hash kriptografi memang dirancang untuk mencegah mengembalikan checksum yang sudah di hash kembali ke teks asli. Namun, meskipun hampir tidak mungkin dibalik, itu bukan berarti nilai hash 100% dijamin aman.

Seperti sekarang banyak software yang memungkinkan untuk menterjemahkan kembali fungsi hash, seperti Rainbow Table yang dapat digunakan untuk mengcrack plaintext checksum. Rainbow Table pada dasarnya adalah kamus yang mengeluarkan ribuan, jutaan, atau bahkan milyaran dari ini di samping nilai plainteks yang sesuai.

Di sini, dibutuhkan O (n) waktu (di mana n adalah jumlah string) untuk mengakses string tertentu. Ini menunjukkan bahwa fungsi hash bukan fungsi hash yang baik.

Mari kita coba fungsi hash yang berbeda. Indeks untuk string tertentu akan sama dengan jumlah nilai ASCII karakter dikalikan dengan urutan masing-masing dalam string setelah itu adalah modulo dengan 2069 (bilangan prima).

Fungsi String Hash Indeks

abcdef (97 1 + 98 2 + 99 3 + 100 4 + 101 5 + 102 6)% 2069 38
bcdefa (98 1 + 99 2 + 100 3 + 101 4 + 102 5 + 97 6)% 2069 23
cdefab (99 1 + 100 2 + 101 3 + 102 4 + 97 5 + 98 6)% 2069 14
defabc (100 1 + 101 2 + 102 3 + 97 4 + 98 5 + 99 6)% 2069 11

Tabel

Tabel hash adalah struktur data yang digunakan untuk menyimpan kunci / pasangan nilai. Tabel hash menggunakan fungsi hash untuk menghitung indeks ke dalam array di mana elemen akan dimasukkan atau dicari. Dengan menggunakan fungsi hash yang baik, hashing dapat bekerja dengan baik. Di bawah asumsi yang masuk akal, waktu rata-rata yang diperlukan untuk mencari elemen dalam tabel hash adalah O (1) .

Mari kita pertimbangkan string S. Anda harus menghitung frekuensi semua karakter dalam string ini.

string S = “ababcd”

Cara paling sederhana untuk melakukan ini adalah untuk mengulangi semua karakter yang mungkin dan menghitung frekuensi mereka satu per satu. Kompleksitas waktu dari pendekatan ini adalah O (26 * N) di mana N adalah ukuran string dan ada 26 karakter yang mungkin.

void countFre(string S)
    {
        for(char c = ‘a’;c <= ‘z’;++c)
        {
            int frequency = 0;
            for(int i = 0;i < S.length();++i)
                if(S[i] == c)
                    frequency++;
            cout << c << ‘ ‘ << frequency << endl;
        }
    }

Hasil outputnya akan seperti ini :

a 2
b 2
c 1
d 1
e 0
f 0
…
z 0

Sumber referensi :

https://www.hackerearth.com/practice/data-structures/hash-tables/basics-of-hash-tables/tutorial/

https://www.immersa-lab.com/fungsi-hash-dalam-kriptografi.htm

0 Comments

Double Linked List

By Emanuel Lienardi - 8:41 AM

Double Linked List

Adalah jenis linked list yang memiliki 2 pointer penunjuk yang juga bekerja sebagai pointer utama, yakni ke arah node sebelum (previous / prev) dan node (next).

Pointer pertama adalah pointer head, pointer ini menunjuk node pertama.

Pointer kedua adalah pointer tail, menunjuk node paling terakhir.

Dengan adanya 2 pointer itu, double linked list bisa lebih mudah digunakan dibanding single linked list. Juga lebih mudah untuk memasukkan data dan merapikannya.

Berikut gambar representasi dari double / doubly linked list

Kita bisa mengetahui kosong atau tidaknya sebuah linked list dengan melihat isi dari pointer head-nya. Jika isi pointer head NULL, maka linked list tersebut masih kosong. Selain itu, nilai pointer prev dari Head selalu NULL. Itu karena, Head merupakan data pertama. Itu juga berlaku di nilai pointer next-nya Tail, kosong. Karena Tail adalah node terakhir.

Berikut beberapa operasi yang biasa digunakan. Operasi ini sama dengan yang digunakan di single linked list.

1. Push

Push adalah operasi untuk memasukkan data ke linked list. Ada 2 macam operasi push, yaitu pushDepan dan pushBelakang.

a. pushDepan

Data yang paling baru dimasukkan akan berada di depan data lainnya.

Misal input 5, 3, 7, 9 : hasilnya jadi 9, 7, 3, 5

b. pushBelakang

Data yang paling baru akan berada di belakang data lainnya.

Misal input 5, 3, 7, 9 : hasilnya jadi 5, 3, 7, 9

2. Pop

Pop memiliki fungsi yang berkebalikan dari push. Pop digunakan untuk menghapus atau delete suatu data dari linked list tadi. Seperti Push, pop juga bisa dilakukan dari depan maupun belakang.

Berikut contoh code menggunakan bahasa Pemrograman C dengan library malloc.h

1. Linked List

2. pushDepan

3. pushBelakang

4. popDepan

5. popBelakang

6. viewAll ( untuk melihat semua data dari linked list diatas )

Referensi : https://socs.binus.ac.id/2017/03/15/doubly-linked-list/

0 Comments

Linked List

By Emanuel Lienardi - 8:32 AM

Emanuel Lienardi

Cyber Security S1/SEM-2/2019-2020

2301865716

GSLC Struktur Data, Februari 2020

Linked List

1. Pengertian

· Berdasarkan pemahaman yang saya dapatkan dari beberapa sumber, linked list atau yang bisa juga disebut senarai berantai adalah salah satu bentuk struktur data yang terdiri dari urutan record data berbentuk linear yang disebut sebagai nodes. Nodes tersebut akan menunjuk nodes lain menggunakan pointer. Definisi linked list secara mudahnya adalah, kumpulan nodes yang mempresentasikan sebuah sequence .

· Berikut adalah macam macam linked list berdasarkan berntuknya :

1. Single linked list

Sekumpulan node yang saling terhubung dengan node lain melalui sebuah pointer. Rangkaian ini diawali dengan head untuk menyimpan alamat awal, dan diakhiri dengan node yang mengarahkan pointer ke null.

Single linked list ini hanya memiliki satu arah dan tidak bisa bolak – balik ( dua arah ).

Pada penggunaannya, single linked list memiliki 2 variasi, yaitu circular dan non – circular.

a. Single linked list circular

SLLC adalah single linked list yang pointer nextnya menunjuk pada diri sendiri. Jika single linked list itu memiliki beberapa node, maka pointer next pada node terakhir akan menunjuk ke node terdepannya.

Arti circular sendiri yaitu, pointer next-nya akan menunjuk diri sehingga pasti bentuknya melingkar ( circle ).

Deklarasi node :

typedef struct Xnode {

int data;

Xnode *next; };

Penjelasan :

- Pembuatan struct yang dinamai Xnode yang berisi 2 field, yaitu field data yang bertipe integer dan berguna untuk menyimpan angka nantinya, dan field next yang berguna sebagai pointer dari Xnode.

- Setelah pembuatan struct, buat variabel head yang bertipe pointer dari Xnode yang berguna sebagai kepala dari linked list tersebut.

b. Single linked list non circular

Ilustrasi Linked List :

- Setiap node pada linked list mempunyai field yang berisi pointer ke node berikutnya adan juga memiliki field yang berisi data.

- Pada akhir linked list, node terakhir akan menunjuk ke NULL yang akan digunakan sebagai kondisi berhenti pada saat pembacaan isi linked list.

Contoh program single linked list non circular

- #include <stdio.h>

- #include <stdlib.h>

- #include <iostream.h>

- #include <ctype.h>

- #include <string.h>

Berikut gambar ilustrasi rangkaian Linked List Non Circular

2. Double linked list
Tentang double linked list bisa dilihat di blog saya lainnya.
Klik link ini.
3. Circular linked list
Linked list ini memiliki arah memutar, membentuk lingkaran, sehingga dia memiliki 2 arah. Oleh karena itu, head dan tail nya otomatis saling terhubung dan tidak ada NULL di bagian akhir.

Berikut keuntungan menggunakan Circular Linked List :
- Setiap node bisa menjadi titik awal dari linked list itu. Bisa dimulai dari node manapun. Berhenti jika sudah melewati node yang sudah dilewati saja.
-   Berguna untuk implementasi antrian. Dengan menggunakan Circular Linked List ini, kita tidak perlu mempertahankan 2 pointer yang ada di depan dan
belakang.
-   Operasi remove dan insert bisa dilakukan dengan mengubah pointernya saja.
-   Daftar node yang dibuat melingkar ini mempermudah kerja aplikasi yang kerjanya berulang kali mengelilingi daftarnya. Contohnya sistem operasi pada PC.
4.   Circular Doubly Linked List

Sebenarnya tidak jauh berbeda dengan Double Linked List Non Circular, hanya saja Double Linked List Circular ini atau yang sering disingkat DLLC memiliki perbedaan yang terletak pada nodenya itu sendiri. Setiap head dan tail node pada DLLNC selalu bernilai NULL, lain halnya dengan DLLC, tail pada node harus merujuk kembali kepada headnya.

0 Comments

About Me

Hashing Table & Binary Tree

Hash Table

Double Linked List

Double Linked List

Linked List

recent posts

Blog Archive