Struktur data adalah suatu koleksi atau kelompok data yang dapat dikarakterisasikan oleh organisasi serta operasi yang didefinisikan terhadapnya. Pengertian struktur data adalah elemen data (mulai dari byte) yang ditentukan tipe datanya, diorganisasi (dibentuk, disusun, atau dikelompokkan) dan akan diproses sesuai dengan tipe datanya. Pada definisinya, data dapat dikategorikan menjadi :
Tipe data sederhana atau data sederhana, yang terdiri dari :
- Data sederhana tunggal, misalnya integer, real, Boolean, serta character.
- Data sederhana majemuk, misalnya string.
Tipe data ini dapat diorganisasikan menjadi berbagai struktur data dengan berbagai cara tertentu.
Struktur data, meliputi :
- Struktur data sederhana, misalnya array dan record.
- Struktur data majemuk, terdiri atas :
- Linear, misalnya stack, queue, dan linear linked list.
- Nonlinear, misalnya pohon binary (binary tree), pohon cari biner (binary search tree), pohon cari m-way (m-way search tree), general tree, serta graph.
Kedua kategori diatas terutama diperuntukkan untuk data pada storage utama. Data yang diperuntukan untuk storage tambahan, memiliki struktur data yang dikenal dengan organisasi file. Tipe organisasi file diantaranya adalah sebagai berikut :
1. Sequential
- Record disimpan dalam file secara beruntun berdasarkan waktu tiba dari pekerjaan yang diwakilinya, sehingga membentuk first-in-first-out (FIFO), struktur data seperti ini disebut antrean atau queue.
- Record yang masuk pertama akan memiliki indeks atau alamat yang lebih kecil daripada record yang masuk kemudian.
2. Indexed Sequential
- Record disimpan secara berurutan.
- Record yang masuk terlebih dahulu disimpan pada tempat yang lebih kecil.
- Untuk melakukan pencarian pada organisasi ini perlu menggunakan pencarian terlebih dahulu.
- Dengan organisasi file ini lebih fleksibel karena ukuran file disesuaikan dengan banyaknya data yang ada pada setiap file.
3. Relative
4. Multikey
Dua buah struktur data sederhana adalah array atau larik dan record. Array merupakan struktur data yang terurut dan homogen, terdiri dari data item yang membentuk satu kesatuan yang tipe datanya sama. Sedangkan record merupakan struktur data yang terdiri atas serangkaian data item dengan tipe data yang berbeda.
Pemakaian struktur data yang tepat di dalam proses pemrograman, akan mengasilkan algoritma yang lebih jelas dan tepat, sehingga menjadikan program secara keseluruhan lebih sederhana.
Suatu struktur data dicirikan dengan :
- Jenis atau satuan data pembentuknya
- Hubungan antara satuan tersebut.
Strukutur data terdiri dari satuan data sederhana yang cocok untuk program yang dipakainya. Hubungan antara satuan data tersebut membentuk salah satu cirri dari struktur yang bersangkutan. Jika sebuah struktur data sudah tersedia maka struktur data itu langsung dapat digunakan. Jika satuan data sederhana dapat membentuk sebuah struktur yang lebih efisien dalam penggunaan memori, maka struktur data tersebut dapat disatukan. Struktur tersebut tidak dapat langsung ditujukan kepada sebuah address, maka dari itu harus melalui proses pemrograman. Jika menggunakan penyajian secara sequential, maka komponen struktur data ditempatkan ke dalam relokasi memori secara berurutan.
Sumber: Dwizer's Blog.htm
Metode Hashing
• Untuk mengatasi kerugian korespondensi satu-satu, digunakan hashing
• Untuk mengurangi banyaknya ruang alamat yang digunakan untuk pemetaan dari key yang memiliki cakupan yang luas ke nilai alamat yang memiliki cakupan yang dipersempit
• Untuk itu dibutuhkan fungsi HASH
• Output fungsi HASH adalah home address dari record yang keynya diproses
• Fungsi : f(key) = address
Macam-Macam Fungsi Hashing
• Fungsi modulo
• Home address dicari dengan cara mencari sisa hasil bagi nilai key dengan suatu nilai tertentu.
• Fungsi: f(key) = key mod n
• Dengan n adalah:
• Banyaknya ruang alamat yang tersedia
• Atau bilangan prima terdekat yang berada di atas nilai banyak data, setelah itu banyaknya ruang alamat disesuaikan dengan n
• Fungsi Pemotongan
• Home address dicari dengan memotong nilai key ke jumlah digit tertentu yang lebih pendek.
• Contoh: NIM yang tadinya 8 digit, dipotong hanya menjadi 2 digit!
• Fungsi Pelipatan
• Dilakukan pelipatan terhadap record key dengan bagian yang sama panjang, lalu setiap bagian dijumlahkan
• NIM 8 digit dibagi dua digit, hingga menjadi 4 buah.
• Misal: 22002521, dibagi 22 00 25 21 kemudian dijumlahkan: 68
• Fungsi Pengkuadratan
• Home address dicari dengan mengkuadratkan setiap digit pembentuk key, lalu semua hasilnya dijumlahkan
• Contoh: 22002211, semua digit dikuadratkan dan dijumlah
• Fungsi Penambahan Kode ASCII
• Jika key bukan kode numerik, home address dicari dengan menjumlahkan kode ASCII setiap huruf pembentuk key
• ADE = 65 + 68 + 69 = 192
Collision (Tabrakan)
• Dengan menggunakan hashing, maka hubungan korespondensi satu-satu antara record key dengan alamat record akan hilang
• Selalu ada kemungkinan dimana terdapat dua buah record dengan key yang berbeda namun memiliki home address yang sama = tabrakan
Kriteria Fungsi Hash Yang Baik
• Dapat mendistribusikan setiap record secara merata, sehingga dapat meminimalkan terjadinya tabrakan
• Dapat dieksekusi secara efisien sehingga waktu tidak habis untuk menghitung home address nya saja
Collision Resolution
• Karena collision dapat dipastikan akan dapat terjadi, maka output dari suatu fungsi hash tidak selalu unik, namun hanya berupa kemungkinan suatu alamat yang dapat ditempati
• Jika suatu home address sudah ditempati oleh record lain, maka harus dicarikan alamat lain
• Proses pencarian alamat lain tersebut disebut collision resolution
Metode Collison Resolution
• Open Addressing
• Chaining
• Coalesced Hashing
• Chained Progressive Overflow
• Bucket
Metode Open Addressing
• Alamat alternatif dicari pada alamat-alamat selanjutnya yang masih kosong
• Cara:
• Linear Probing
Pencarian dilakukan dengan jarak pencarian tetap
• Quardratic Probing
Pencarian dilakukan dengan jarak pencarian berubah dengan perubahan tetap
• Double Hashing
Pencarian dilakukan menggunakan fungsi hash kedua. Pertama hash untuk mencari home address, kedua untuk pencarian jika terjadi collision. Fungsi hash kedua tidak boleh menghasilkan nilai 0
Tidak ada komentar:
Posting Komentar