Materi Hashing - Struktur Data

Materi Hashing


A. Pengertian
     Hashing adalah proses pengindeksan dan pengambilan elemen (data) dalam struktur data untuk menyediakan cara yang lebih cepat untuk menemukan elemen menggunakan kunci hash.



Hash Value=Key mod (n+1)

B. Collision
     Collision terjadi ketika dua item hash ke slot yang sama, kita harus memiliki metode sistematis untuk menempatkan item kedua dalam tabel hash.
Memecahkan:
- Open Addressing : dalam hal itu mencoba untuk menemukan slot atau alamat terbuka berikutnya di tabel hash.
  1. Linear Probbing : Kita melihat secara berurutan, slot demi slot, sampai kita menemukan posisi terbuka.
  2. Quadratic Probbing : Ini berarti bahwa jika nilai hash pertama adalah h, nilai berturut-turut adalah h + 1, h + 4, h + 9, h + 16. seterusnya
- Closed Address (Separate Chaining)

     Pada dasarnya separate chaining membuat tabel yang digunakan untuk proses hashing menjadi sebuah array of pointer yang masing-masing pointernya diikuti oleh sebuah linked list, dengan chain (mata rantai) 1 terletak pada array of pointer, sedangkan chain 2 dan seterusnya berhubungan dengan chain 1 secara memanjang.

     Kelemahan dari open hashing adalah bila data menumpuk pada satu/sedikit indeks sehingga terjadi linked list yang panjang.

Source Code Dasar :

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
            print(ind)
        ind=ind+1

Contoh Program Hashing dengan gabungan beberapa penyelesaian :

import random
import time

def random_angka(banyak_angka):
 list_Angka = []
 for i in range(banyak_angka):
     num = random.randint(1,banyak_angka)
     list_Angka.append(num)
 return list_Angka

blist = random_angka(100)
print('blist\n',blist)

lineStart = time.clock()
print('\nLinier Probbing')

def lineHashx(x):
    return x%100
    
def linierHash(table,keys, value):
    index = lineHashx(keys)
    if table[index] == None and (value not in table):
        table[index] = value
    elif table[index] == value:
        table[index] = None
#        table[index] = value
    else:
        collusion = index
        found = False
        posisi = collusion+1
        if posisi >= len(table)-1:
            posisi = 0
        while posisi < len(table)-1 and not found:
            if table[posisi] == value:
                found = True
                table[posisi] = None
            elif table[posisi] == None and (value not in table):
                found = True
                table[posisi] = value
            posisi += 1

def autoCreateHash(table, alist):
    for value in alist:
        linierHash(table, value, value)

#Main to AutoCreate Hashing table from List
table = [None]*100
autoCreateHash(table, blist)
print('\n',table)

#Insert or Remove data from hashing table
#search = int(input('Masukkan data yang mau dicari = '))
#linierHash(table, search, search)
#print(table)

lineEnd = time.clock()


quadStart = time.clock()
print('\nQuadratic Probbing')

def quadHashx(x):
    return x%100
    
def quadraticHash(table, keys, value):
    index = quadHashx(keys)
    if table[index] == None and (value not in table):
        table[index] = value
    elif table[index] == value:
        table[index] = None
#        table[index] = value
    else:
        found = False
        i = 0
        while not found:
            collusion = index
            i += 1
            collusion += i**2
            pIndex = quadHashx(collusion)
            if table[pIndex] == value:
                found = True
                table[pIndex] = None
            elif table[pIndex] == None and (value not in table):
                found = True
                table[pIndex] = value

def autoCreateHash(table, alist):
    for value in alist:
        quadraticHash(table, value, value)

#Main to AutoCreate Hashing table from List
table = [None]*100
#blist = [54,26,93,17,77,31,44,55,20]
autoCreateHash(table, blist)
print(table)

#Insert or Remove data from hashing table
#search = int(input('Masukkan data yang mau dicari = '))
#quadraticHash(table, search, search)
#print(table)

quadEnd = time.clock()


chainStart = time.clock()
print('\nChaining Address')

def chainHashx(x):
    return x%11
    
def chainingHash(table, keys, value):
    if value in table[chainHashx(keys)]:
        table[chainHashx(keys)].remove(value)
    else:
        table[chainHashx(keys)].append(value)
#        table[hashx(value)].insert(0, value)   
    
def autoCreateHash(table, alist):
    for value in alist:
        chainingHash(table, value, value)

#Main to AutoCreate Hashing table from List
table = [[] for _ in range(11)]
#blist = [54,26,93,17,77,31,44,55,20]
autoCreateHash(table, blist)
print(table)


#Insert or Remove data from hashing table
#search = int(input('Masukkan data yang mau dicari = '))
#chainingHash(table, search, search)
#print(table)

chainEnd = time.clock()

print('\nPerbandingan Waktu Eksekusi')
print('Linier    = ',lineEnd-lineStart)
print('Quadratic = ',quadEnd-quadStart)
print('Chaining  = ',chainEnd-chainStart)

Hasil Run : 

Python 3.5.2 (default, Nov 23 2017, 16:37:01) 
[GCC 5.4.0 20160609] on linux
Type "copyright", "credits" or "license()" for more information.
>>> 
================ RESTART: /home/rejeb/Downloads/2_hashing.py ================
blist
 [50, 28, 98, 70, 26, 91, 32, 38, 48, 74, 65, 91, 58, 47, 96, 1, 74, 33, 87, 71, 94, 12, 3, 27, 85, 92, 64, 35, 24, 23, 1, 82, 89, 98, 67, 61, 44, 13, 53, 88, 57, 70, 71, 51, 23, 55, 3, 39, 3, 70, 50, 44, 56, 8, 98, 1, 14, 31, 56, 66, 28, 84, 49, 24, 8, 24, 14, 69, 59, 100, 46, 92, 40, 31, 42, 26, 100, 50, 70, 25, 42, 24, 89, 46, 21, 38, 19, 33, 42, 30, 67, 45, 100, 8, 92, 45, 51, 61, 91, 26]

Linier Probbing

 [100, 1, None, 3, None, None, None, None, 8, None, None, None, 12, 13, None, None, None, None, None, 19, None, 21, None, None, None, 25, 26, 27, None, None, 30, None, 32, None, None, 35, None, None, None, 39, 40, None, 42, None, None, None, None, 47, 48, 49, 50, None, None, 53, None, 55, None, 57, 58, 59, None, None, None, None, 64, 65, 66, None, None, 69, None, None, None, None, None, None, None, None, None, None, None, None, 82, None, 84, 85, None, 87, 88, None, None, 91, 92, None, 94, None, 96, None, 98, None]

Quadratic Probbing
[100, 1, None, 3, None, None, None, None, 8, None, None, None, 12, 13, None, None, None, None, None, 19, None, 21, None, None, None, 25, 26, 27, None, None, 30, None, 32, None, None, 35, None, None, None, 39, 40, None, 42, None, None, None, None, 47, 48, 49, 50, None, None, 53, None, 55, None, 57, 58, 59, None, None, None, None, 64, 65, 66, None, None, 69, None, None, None, None, None, None, None, None, None, None, None, None, 82, None, 84, 85, None, 87, 88, None, None, 91, 92, None, 94, None, 96, None, 98, None]

Chaining Address
[[88, 55, 66], [12, 1, 100], [35, 13, 57], [58, 47, 3, 69, 25, 91], [48, 59, 92, 26], [27, 82, 49], [94, 39, 50], [84, 40], [96, 85, 19, 30, 8], [64, 53, 42], [32, 65, 87, 98, 21]]

Perbandingan Waktu Eksekusi
Linier    =  0.006620999999999988
Quadratic =  0.005447000000000091
Chaining  =  0.0038129999999999553
>>>

Comments

Post a Comment

Popular posts from this blog

Searching - Linier Search & Binary Search Python

Image
Kelompok: Sitti Suwaibah (170411100009) Wijanarko Putra Rajeb (170411100061)  Assalamualaikum Wr. Wb. Kali ini kita akan membagikan Materi dan beberapa script python tentang linier search dan binary search. Berikut scriptnya: ### Mencari Keberadaan Suatu Angka di Dalam List Data ### A. Metode Linier Search Linear search merupakan program search yang mudah dipahami, linear search memiliki kelebihan apabila data yang di cari letaknya pada data – data awal sehingga prosesnya berjalan cepat, namun apabila data yang di cari letaknya pada data terakhir maka pencarian lebih memakan waktu yang cukup lama pula. karena di linear search mengunjungi setiap elemen data yang ada.   1. Biasa ### myList = [1,5,10,15,20,25,30,2,6,8,9] # Example List cari = int(input("Masukkan Angka Yang Anda Cari : ")) # angka yang ingin dicari counter = 0 while counter != len(myList): if myList[counter] == cari: print("Found The Search Number.",counter) cou
Read more

Sorting Data 1 - Bubble Sort dan Selection Sort

Image
Sorting adalah pengurutan data dimana di dalam sorting ituada 2 macam proses sorting. Ada bubble sort sama selection sort. 1. Bubble Sort Adalah algoritma pengurutan sederhana yang berulang kali melewati daftar yang akan diurutkan, membandingkan setiap pasangan item yang berdekatan dan menukar mereka jika mereka berada di urutan yang salah. def BubbleSort(val): counter = 0 for passnum in range(len(val)-1,0,-1): for i in range(passnum): counter += 1 if val[i]>val[i+1]: val[i],val[i+1] = val[i+1],val[i] print(val) print('jumlah iterasinya',counter) DaftarAngka = [23,7,32,99,4,15,11,20] BubbleSort(DaftarAngka) Video Tutorial Bubble Sort https://goo.gl/r8EAA5 2. Selection Sort Menemukan nilai minimum dalam array dan memindahkannya ke posisi pertama. Langkah ini adalah pengulangan untuk nilai terendah kedua, lalu yang ketiga, dan seterusnya sampai array diurutkan. def SelectionSort(val):
Read more