Hashing

Definisi

Hashing adalah transformasi aritmatik sebuah string dari karakter menjadi nilai yang merepresentasikan string aslinya. Hashing digunakan sebagai metode untuk menyimpan data dalam sebuah array agar penyimpanan data, pencarian data, penambahan data, dan penghapusan data dapat dilakukan dengan cepat. Fungsi yang mengembalikan nilai atau kunci disebut fungsi hash (hash function) dan array yang digunakan disebut tabel hash (hash table). Fungsi hash menyimpan nilai asli atau kunci pada alamat yang sama dengan nilai hashnya. Pada pencarian suatu nilai pada tabel hash, yang pertama dilakukan adalah menghitung nilai hash dari kunci atau nilai aslinya, kemudian membandingkan kunci atuau nilai asli dengan isi pada memori yang beralamat nomor hashnya. Metode-metode yang sering digunakan adalah:
1. Linear probing
        Dengan menambahkan suatu interval pada hasil yang diperoleh dari fungsihash sampai ditemukan lokasi yang belum terisi. Interval yang biasa digunakan adalah 
 2. Quadratic probing / squared probing
        Hampir sama dengan linear probing, hanya saja pada quadratic probing, hasil yang diperoleh dari fungsi hash ditambahkan dengan kuadrat dari interval yang digunakan. 

3. Chaining 

        Tabel hash bukan lagi menjadi array of records, tetapi menjadi array of pointers. Setiap pointer menunjuk ke senarai berkait yang berisi record tersebut. Kelebihan dari metode chaining ini chaining ini adalah proses penghapusan yang relarif mudah dan penambahan ukuran tabel hash bisa ditunda untuk waktu yang lebih lama karena penurunan kinerjanya berbanding lurus meskipun seluruh lokasi pada tabel sudah penuh.

Sr. No.	Key	Hash	Array Index	After Linear Probing, Array Index
1	1	1 % 20 = 1	1	1
2	2	2 % 20 = 2	2	2
3	42	42 % 20 = 2	2	3
4	4	4 % 20 = 4	4	4
5	12	12 % 20 = 12	12	12
6	14	14 % 20 = 14	14	14
7	17	17 % 20 = 17	17	17
8	13	13 % 20 = 13	13	13
9	37	37 % 20 = 17	17	18

Algoritma

table = [  [] for _ in range(10)]

print(table)

def hash(x):

    return x % 10

def insert(table,key,value):

    table[hash(key)].append(value)

Kode Program

table= [None]*10

def hash(x):

    return x%10

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 cari(table,key):

    index = hash(key)

    value = key

    if table[index]== value:

        print('Ada angka ', value,'di index',table[index])

    else :

        collusion=index

        found = False

        ind = collusion+1

        j=0

        if ind>len(table)-1:

            ind = 0

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

            if table[ind]==value:

                found=True

                print('Ada angka ', value,'di index',ind)

            ind=ind+1

            if ind>len(table)-1:

                print('Angka tidak ditemukan')

                found=True

insert(table,4,4)

insert(table,3,3)

insert(table,4,14)

insert(table,3,13)

insert(table,3,23)

insert(table,9,9)

insert(table,9,29)

print (table)

cari(table,29)