STRUKTUR DATA - Hashing Python

STRUKTUR DATA - Hashing

 

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

•       Hash Value = Kunci mod (n + 1) 

   

 
 

➢    Colission

               Colission = Ketika dua item hash ke slot yang sama, kita harus memiliki metode sistematis untuk menempatkan item kedua di tabel hash

Menyelesaikannya :

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.

 

➢    Open Address

 

Quadratic : ['77', '44', '20', '55', 26, '93', '17', Tidak Ada, Tidak Ada, '31', 54]

 
 

Linear probbing: [77, 44, 55, 20, 26, 93, 17, 25, None, 31, 54]

➢  Close Address

Chaining = memungkinkan banyak item ada di lokasi yang sama dalam tabel hash. Ketika collisions terjadi, item masih ditempatkan di slot yang tepat dari tabel hash.

 

Source Code :

print("=== 160411100171 - Mas'ady Fawaizul Ihsan ===")

print("============ Hashing ============")

print("====== 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

        index = collusion + 1

        if index  >= len(table)-1:

            index = 0

        while(index <= len(table)-1) and not(found):

            if table[index] == None:

                found = True

                table[index] = value               

            index = index+1

           

masuk = "y"

while masuk == "y":

  data = int(input("Masukan berapa kali ingin memasukan data ke Tabel Hash: "))

  if data > len(table):

    print("Panjang data masukan lebih dari panjang Tabel Hash")

    print("Tolong masukan ulang")

  else:

    masuk = "n"

b = 1

while b <= data:

  masukan = int(input('Masukan angka yang ingin dimasukan ke Tabel Hash = '))

  insert(table,masukan,masukan)

  b+=1

print(table)

print("====== 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

        index = collusion + 1

        if index >= len(table)-1:

            index = 0