Home
Uncategorized

hashing and symbol table

Hashing adalah metode memetakan sebuah data kesebuah tempat dimana data sebenarnya berubah dalam bentuk lain. pada python, cara metode hashing dengan membuat sebuah list yang akan di isi oleh data masukan. data masukan di beri dua buah nilai yaitu value sebagai data tersebut dan juga key sebagai alat untuk memasukan value ke list.

alagoritma hasing sebagai berkit.

  1.  membuat table hash yang berisikan none
  2.  memasukan data yang ingin dimasukan 
  3. data masuk terdiri value dan key nya
  4. lakukan pencarian modulus dari key yang di bagi panjang table hash 
  5. masukan value dari data tersebut kedalam table hash sesuai index nya
permasalahan yang terjadi pada hashing apabila pada index yang terjadi banyak value, inilah yang disebut collision. cara nya ada tiga yang saya sudah pelajari yaitu: linear hashing, quadratic hashing dan close address.
betikit ini penjelasan dari penyelesaian diatas :

  1. linear probling penyelesain dengan linear yaitu melakukan penambahan 1 tiap index yang terjadi collision misalnya, collision terjadi pada index 3, maka selanjutnya berindex 3 akan ditambahkan ke index 4, jika index 4 sudah terdapat value atau isi maka data tersebut ditaruh di index 5.
  2. quadratic probling, penyelesaian ini sama seperti linear akan tetapi penambahan tidak satu persatu melainkan penambahnya dikuadratkan lalu dimodulus dengan panjang table hash. misalnya yang terjadi collision dengan index 3 dan panjang table 10 maka jika ditambahkan data yang berindex 3 maka data tersebut ditaru di index ke 3 yang ditambahkan 1 kuadrat 2 jadi berindex 4 lalu dimodulus panjang table hash jadi index 4. jika index 4 sudah terisi maka index ditambah 2 kuadrat 2 jadi 3 + 4 yaitu 7 dan dimodulus panjang table hash yaitu 10 menjadi index 7, begitu seterusnya sehingga data dapat ditempatkan ditempat kosong pada table hash.
  3. close address, penyelesaian dengan cara ini yaitu membuat list pada table hash sehingga data yang berindex sama tidak terjadi collision karena data tersebut ditumpuk kedalam sebuah list yang dibuat.
berikut implementasi pada bahasa pemrograman python dari ketiga penyelesain metode hashing di atas:
  • linear probling
#Linier Probbing
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
while x < len(data):
    insert(table,data[x],data[x])
    x += 1
print('Linier Probbing')#Quadratic
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
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(table)
cari = 44
print('cari : ', cari)
search(cari,table)

  • quardatic probling
#Quadratic
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
while x < len(data):
    insert(table,data[x],data[x])
    x += 1
print('Quadratic')
print(table)
cari = 44
print('cari : ', cari)
search(cari,table)

  • close address
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)



Post a Comment