PENGALAMATAN TERBUKA (OPEN ADDRESSING)

17:39 Pemrograman Web 4 Comments



PENGALAMATAN TERBUKA (OPEN ADDRESSING)

Kali ini saya akan menjelaskan tentang Pengalamatan Terbuka (Open Addressing)
Pengalamatan terbuka atau open addressing merupakan salah satu cara yang digunakan untuk mengatasi tabrakan pada hash.
Ada beberapa metode untuk menemukan alamat baru yang masih kosong. Untuk menemukan alamat yang baru atau lokasi kosong ini harus menggunakan pola tertentu agar rekaman yang disimpan pada alamat kosong tersebut tetap bisa didapatkan dengan mudah saat dibutuhkan kembali. Ada 3 Metode yang sering digunakan yaitu:

1. Linear probing
2. Quadratic probing / squared probing
3. Double hashing

Contohnya pada sebuah rekaman dengan kunci k akan disisipkan ke dalam tabel alamat hash. Berdasarkan fungsi hash yang dipakai, alamat untuk kunci k tersebut dihitung, misalnya pada alamat h. dan apabila pada alamat h sudah terisi maka alamat h tersebut akan disipan pada alamat yang kosong. Cara ini merupakan cara Linier Probing.

Liniear Probing yaitu Dengan menambahkan suatu jaraka/space pada hasil yang diperoleh dari fungsi hash sampai didapatkan alamat yang belum terisi, maka data tersebut disimpan atau diletakkan pada alamat yang kosong tersebut.
Untuk lebih jelaskan berikut adalah contohnya:

Rekaman
A
B
C
K
P
Q
R
Y
Z
H(k)
5
6
7
5
0
1
2
9
0

Dari contoh diatas maka dihasilkan data seperti data dibawah ini:
Rekaman
P
Q
R
Z
-
A
B
C
K
Y
H(k)
0
1
2
3
4
5
6
7
8
9

Dapat dilihat dari data diatas rekam A,B,C,P,Q dan R menempati rekaman atau susunan yang sesuai pada table yang pertama sedangkan K dan Z ditempatkan di rekaman yang kosong. Karena rekaman sebelumnya pada table pertama sudah dipake yang lain. Jadi ditempatkan pada data yang kosong.
Pada terbuka menangani, setiap posisi dalam array adalah di salah satu dari tiga kondisi, Empty, Delete, atau Occupied. Jika posisi ditempati, mengandung nilai yang sah (kunci dan data); jika tidak, tidak mengandung nilai. Posisi yang awalnya kosong. Jika nilai dalam posisi dihapus, posisi ditandai sebagai Delete, bukan Empty: kebutuhan untuk perbedaan ini dijelaskan di bawah.

Algoritma untuk memasukkan nilai V ke dalam tabel adalah ini:
menghitung posisi di mana V harus disimpan, P = H (key (V)).
Jika posisi P tidak OCCUPIED, toko V ada.
Jika posisi P OCCUPIED, menghitung posisi lain di meja; set P untuk nilai ini dan ulangi (2) - (3).

BERIKUT ADALAH SOURCE CODE DARI PROGRAM DIATAS.
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define MAX 10

void main()
{

                        int a[MAX],num,key,i;
                        char ans;
                        int create(int);
                        void linear_prob(int [],int,int),display(int []);
//clrscr();
                        printf("\n Collision Handling By Linaer Probling");
                        for(i=0;i<MAX;i++)
                        a[i]=-1;
            do
            {
                        printf("\n Masukkan Angka ");
                        scanf("%d",&num);
                        key=create(num);
                        linear_prob(a,key,num);
                        printf("\n Apakah anda mau lanjut(Y/N");
                        ans=getch();
            }
            while(ans=='y');
                        display(a);
                        getch();
}

int create(int num)
            {          
                        int key;
                        key=num%10;
                        return key;
            }

void linear_prob(int a[MAX],int key,int num)
{
                        int flag,i,count=0;
                        void display(int a[]);
                        flag=0;
                        if(a[key]==-1)
                        a[key]=num;
            else
            {          
                        i=0;
            while(i<MAX)
            {
                        if(a[i]!=-1)
                        count++;
                        i++;
            }          
                                    if(count==MAX)
            {
                        printf("\n\n Hash Table adalah Fu;;");
                        display(a);
                        getch();
                        exit(1);
            }

                        for(i=key+1;i<MAX;i++)
                        if(a[i]==-1)

                                    {
                        a[i]=num;
                        flag=1;
                        break;
            }
                        for(i=0;i<key&&flag==0;i++)
                                    if(a[i]==-1)
            {
                                    a[i]=num;
                                    flag=1;
                                    break;

                        }
            }
}

void display(int a[MAX])
{
                        int i;

                        printf("\n\n The HAsh Table adalah....\n");
                        for(i=0;i<MAX;i++)
                        printf("\n %d %d",i,a[i]);
}


Sekian penjelasan tentang pengalamat terbuka dari saya, kurang lebihnya mohon di maafkan.
Assalamualaikum wr wb.





NAMA: AYU ANGGARA
NPM: 1144014

PLAGIARISM:



4 komentar: