HASHING

-

1.     LINEAR PROBING
Dengan menambahkan suatu interval pada hasil yang diperoleh dari fungsi hash sampai ditemukan lokasi yang belum terisi. Berikut Sourcodenya:
table=[None]*11
def hash(x):
    return x%11
def insert(table,key,value):
    index = hash(key)
    if table[index] == None:
        table[index]=value
    else:
        collusion=index
        found = False
        ind = collusion+1
        if ind>=len(table)-1:
            ind = 0
        while (ind<=len(table)-1)and not(found):
            if table[ind]==None:
                found = True
                table[ind]=value
            ind = ind+1            
def search(cari,table):
    found = False
    keluar = False
    ind = hash(cari)
    if ind>=len(table)-1:
        ind = 0
    elif not found and ind:
        print('Data tidak ditemukan')
    while (ind<=len(table)-1)and not(found):
        if table[ind]==cari:
            print('Data ditemukan')
            found = True
        ind = ind+1
   
           
data = [54,26,93,17,77,31,44,55,20]
x = 0
import time
start = time.clock()
while x < len(data):
    insert(table,data[x],data[x])
    x += 1
print('Linier Probbing')
print(table)
cari = 44
print('cari : ', cari)
search(cari,table)
print('waktu yang dibutuhkan : ', round(time.clock()-start,5), ' detik')
2.      QUADRATIC PROBING
Hampir sama dengan linear probing, hanya saja pada quadratic probing, hasil yang diperoleh dari fungsi hash ditambahkan dengan kuadrat dari interval yang digunakan. Berikut Sourcodenya:
table=[None]*11
def hash(x):
    return x%11
def insert(table,key,value):
    index = hash(key)
    if table[index] == None:
        table[index]=value
    else:
        collusion=index
        found = False
        ind = collusion+1
        i = 1
        if ind>=len(table)-1:
            ind = 0
        while (ind<=len(table)-1)and not(found):
            if table[ind]==None:
                found = True
                table[ind]=value
            ind = (collusion+(i*i))%11
            i += 1

def search(cari,table):
    found = False
    keluar = False
    ind = hash(cari)
    if ind>=len(table)-1:
        ind = 0
    elif not found and ind:
        print('Data tidak ditemukan')
    while (ind<=len(table)-1)and not(found):
        if table[ind]==cari:
            print('Data ditemukan')
            found = True
        ind = ind+1
   
           
data = [54,26,93,17,77,31,44,55,20]
x = 0
import time
start = time.clock()
while x < len(data):
    insert(table,data[x],data[x])
    x += 1
print('Quadratic')
print(table)
cari = 44
print('cari : ', cari)
search(cari,table)
print('waktu yang dibutuhkan : ', round(time.clock()-start,5), ' detik')
3.     DOUBLE HASHING
Pada metode double hashing, jika lokasi yang diperoleh dengan fungsi hash sudah terisi, maka dilakukan proses hash lagi sampai ditemukan lokasi yang belum terisi.Keunggulan metode chaining dibanding open addressing:
1.     Lebih mudah diimplementasikan dengan efektif dan hanya membutuhkan struktur data dasar.
2.     Metode chaining tidak rawan terhadap data-data yang berkumpul di daerah tertentu. Metode open addressing membutuhkan algoritma hash yang lebih baik untuk menghindari pengumpulan data di sekitar lokasi tertentu.
3.     Performa menurun secara linier. Meskipun semakin banyak record yang dimasukkan maka semakin panjang senarai berantai, tabel hash tidak akan penuh dan tidak akan menimbulkan peningkatan waktu pencarian record yang tibatiba meningkat yang terjadi bila menggunakan metode open addressing.
4.     Jika record yang dimasukkan panjang, memori yang digunakan akan lebih sedikit dibandingkan dengan metode open addressing.
Berikut SourceCodenya:
table=[[]for _ in range(11)]
def hash(x):
    return x%11
def insert(table,key,value):
    table[hash(key)].append(value)
   
insert(table,54,54)
insert(table,26,26)
insert(table,93,93)
insert(table,17,17)
insert(table,77,77)
insert(table,31,31)
insert(table,44,44)
insert(table,55,55)
insert(table,20,20)
print(table)


Di post oleh :
1. FITRI ANISA (170411100014)
2. DHEA OKY SYAFITRI (170411100006)

Komentar

Posting Komentar

Postingan populer dari blog ini

Class and Object in Python

-
Class dan Objek Class Merupakan Struktur data yang bisa kita gunakan untuk mendefinisikan objek yang menyimpan data bersama-sama nilai-nilai dan perilaku (behavior). Kelas adalah suatu entitas yang merupakan bentuk program dari suatu abstraksi untuk permasalahan dunia nyata, dan instans dari class merupakan realisasi dari beberapa objek. contoh kelas : binatang, kendaraan, benda dsb. 2. objek merupakan Instance dari class. Jika class secara umum merepresentasikan (template) sebuah object, maka sebuah instance adalah representasi nyata dari class itu sendiri. 3. pada dasarnya ada 2 karakteristik yang utama pada sebuah objek : Objek memiliki attribut sebagai status yang disebut Stat Objek memiliki tingkahlaku yang kemudian disebut Method 4. keyword class diikuti dengan nama class yang kita inginkan. Lebih baik digunakan kata yang diawali huruf kapital. 5. Setiap method harus memiliki parameter self yang artinya method tersebut dim...
Baca selengkapnya

DOUBLE LINKED LIST

-
DOUBLE LINKED LIST 1.       PENGERTIAN DOUBLE LINKED LIST Double Linked List sama seperti  Single Linked List  merupakan sebuah tempat yang disediakan pada satu area memori tertentu untuk menyimpan data yang dikenal dengan sebutan node atau simpul. Akan tetapi, setiap node pada double linked list selain memiliki pointer yang menunjuk ke simpul berikutnya sehingga terbentuk satu untaian, juga memiliki pointer yang menunjuk ke simpul sebelumnya. Susunan berupa untaian model ini disebut Double Linked List.  2.       SOURCE CODE class Node:     def __init__(self,initdata):         self.data = initdata         self.next = None         self.previous = None     def getData(self):         return self.data  ...
Baca selengkapnya

GRAPH

-
GRAPH 1.      PENGERTIAN GRAPH Graph adalah kumpulan node (simpul) di dalam bidang dua dimensi yang dihubungkan dengan sekumpulan garis (sisi). Graph dapat digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut. Representasi visual dari graph adalah dengan menyatakan objek sebagai node, bulatan atau titik (Vertex), sedangkan hubungan antara objek dinyatakan dengan garis (Edge). 2.      ISTILAH PADA GRAPH Terdapat beberapa istilah yang berkaitan dengan graph yaitu : Ø   Vertex Vertex yaitu himpunan node / titik pada sebuah graph . Ø   Edge Edge yaitu himpunan garis yang menghubungkan tiap node / vertex . Ø   Adjacent Adjacent yaitu Adalah dua buah titik dikatakan berdekatan ( adjacent ) jika dua buah titik tersebut terhubung dengan sebuah sisi. Ø   Weight Disebut sebuah graph berbobot ( weight graph ), apabila terdapat sebuah fungsi bobot bernilai real. Ø ...
Baca selengkapnya