Hashing Python

Hashing pada Python

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

Collision = Ketika dua item hash ke slot yang sama, kita harus memiliki metode sistematis untuk menempatkan item kedua dalam tabel hash.
Memecahkan:

A. Open Address: 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.

Source Code :

table = [None]*110
def Linear(x):
    return x % 11
def insert(table,keys,value):
    index = Linear(keys)
    if table[index]==None:
        table[index]=value
    else:
        tumbukan=index
        found = False
        ind = tumbukan + 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 +=1
    return table
keys = []
for i in range (0,100):
    keys.append(random.randint(11,111))
value = list(keys)
for j in range(0,100):
    linear = insert(table,keys[j],value[j])

print (linear)

2. Qudratic Probbing: Ini berarti bahwa jika nilai hash pertama adalah h, nilai berturut-turut adalah h + 1, h + 4, h + 9, h + 16. seterusnya

Source code :

table1 = [None]*100 def Quadrat(x): return x% 11 def insert1(table1,keys1,value1): index = Quadrat(keys1) if table1[index]==None: table1[index]=value1 else: tumbukan=index found = False ind = tumbukan + 1 if ind >= len(table1)-1: ind = 0 i = 1 while (ind<=len(table1)-1) and not(found): i+=1 if table1[ind]== None: found = True table1[ind]=value1 ind = (ind+(i**2)) return table1 keys1 = list(keys) value1 = list(keys) for j in range(0,100): quadratic=insert1(table1,keys1[j],value1[j]) print (quadratic)

B. Close Address

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

Source Code :

table2 = [[]]*20
def Chaining(x):
    return x % 11
def insert2(table2,keys2,value2):
    index = Chaining(keys2)
    if table2[index]==[]:
        table2[index]=[value2]
    else:
        table2[index].append(value2)
    return table2
keys2 = list(keys)
value2 = list(keys)
for j in range(0,100):
    chaining = insert2(table2,keys2[j],value2[j])
print (chaining)

Selamat Mencoba...