HASHING (Java Programming)

Hash tables salah satu fasilitas dari method  yang sudah disediakan oleh java untuk memudahkan pelabelan suatu array.

Analogi yang tepat dari hash tables sendiri seperti pembacaan kamus.

Ketika memanggil kata tertentu akan keluar hasil balik dari kata kunci tersebut.

Contoh : kamus inggris Indonesia berikut . kita butuh memasukkan key nya untuk memanggil kata yang dimaksud.

Book maka secara otomatis key tersebut akan memanggil nilainya yakni buku.

Jadi seperti halnya array, hash tables hanya mempermudah penamaan array tertentu yang ingin dipanggil dengan kata kunci (key) tertentu.

Pada kata tertentu memiliki hashcode, atau nilai tertentu pada setiap String yang dimiliki nya. Disini tidak dijelaskan bagaimana computer menerjemahkan String kedalam Hash codes tersebut. Namun yang akan dipelajari ialah bagaimana mengkonversi key dalam String tertentu menjadi HashTables. Hash Tables adalah table dari key (kata kunci) yang sudah dibuat dengan index tertentu. Index tertentu tersebut terbentuk dari key. Nah untuk merubah String tersebut kedalam index agar dapat dimengerti didalam hashtables, ialah dengan langkah-langkah sebagai berikut.

  1. Awalnya kita menterjemahkan String tersebut kedalam bentuk nilai yakni Hash codesnya.

Dengan method >>>> object.hashCode()

Maka kita akan mendapatkan hashcodes dari String tersebut,

Contoh : String s = “rasyid”;
Printf(s.hashCode());
Output : -938116944
  1. Setelah itu diperlukan cara untuk mengkonversinya, yakni dengan melakukan modulus. Kenapa harus dengan modulus. Karena dengan modulus terhadap nilai kapasitas (kapasitas dari table yang akan dibuat), maka nilai yang akan dihasilkan tentunya ialah nilai antara 2 hingga N-1 dari table tersebut. Contoh array dengan kapasitas 11. Tentu nya memiliki index antara 0 hingga 10. Maka dari itu, nilai dari suatu bilangan jika dimodulus dengan kapasitas tersebut akan menghasilkan nilai modulus antara 0 hingga 10. Contoh 20 % 11, maka keluarannya ialah 9.
  2. Nilai hashcodes pada suatu key (string) jelas berbeda-beda, sehingga mungkin saja nilai hashcodes nya bernilai negative. Suatu nilai negative jika dimodulus akan menghasilkan nilai negative. Maka dari itu kita juga butuh mengkonversi bilangan hashcodes nya menjadi bilangan bulat positif.

Misalkan “jack” menghasilkan angka biner 101111 (*ket : nilai 1 pada kiri merupakan penanda bahwa angka tersebut negative, jika 0 berarti postif).

Cara yang tepat ialah melakukan oprasi Boolean dan dengan angka biner 011111…

Nah angka 01111… (takhingga), jika dikonversi angka menghasilkan bilangan bulat yang begitu panjang, namun dalam bentuk hexadesimalnya ialah 0x7FFFFFFF.

Maka : 101111 & 0x7FFFFFFF maka hasilnya ialah 001111.

  1. Nah setelah itu kita sudah mendapatkan nilai dari indexnya.

Contoh :

Misalkan kita ingin membuat hash table dengan jumlah 11

int kapasitas = 11;
String s = “rasyid”;
int j = (s.hashCode() & 0x7FFFFFFF )% kapasitas ;
Printf(j);
Output nya : 77

Contoh Javanya :

import java.util.HashMap;
import java.util.Map;
public class TestHashTable {
private static final int MASK = 0x7FFFFFFF;
    private static final int CAPACITY = 101;
    public static void main(String[] args) {
        Map map1 = new HashMap();
        map1.put(“Tor”, “gate”);
        map1.put(“Rad”, “wheel”);
        map1.put(“Tag”, “day”);
        map1.put(“Uhr”, “clock”);
        map1.put(“Hut”, “hat”);
        map1.put(“Ohr”, “ear”);
        System.out.println(“map1=” + map1);
        printHashCode(“rasyid”);
        printHashCode(“Pin”);
        printHash(“rasyid”);
        printHash(“Hut”);
    }
    private static void printHash(String word) {
        System.out.println(“hash(” + word + “) = ” + hash(word));
    }
    private static int hash(Object object) {
        return (object.hashCode() & MASK) % CAPACITY;
    }
    private static void printHashCode(String word) {
        System.out.printf(“%s: %s%n”, word, word.hashCode());
    }
}

Ketika key tersebut digunakan pada index tertentu, pada kasus tertentu hash yang kita buat memiliki nilai yang sudah dimiliki hash lain. Sehingga pada hashtable tersebut program kesulitan untuk mencerna mana key yang memiliki index tersebut, misalkan kata “tug” dan kata “raw” memiliki nilai index yang sama. Maka kita perlu solusi untuk menyelsaikan ini.

Solusi :

  1. Linear probes.

Linear quadratic probes ialah solusi dengan cara mencari kan nilai index yang kosong metode linear. Metode linear yang dimaksud ialah mencari satu-satu index yang belum terisi dari index ke 0. Probes ialah banyak perulangan yang terjadi selama mencari index yang kosong tersebut. Sama halnya dengan metode pencarian Sequential Search. Metode ini juga memiliki notasi big O sebesar O(n). Kelebihannya metode ini selalu menemukan index yang kosong atau belum terisi. Kekurangannya metode ini jauh lebih lambat.

  1. Quadratic Probes.

Linear quadratic probes ialah solusi dengan cara mencari kan nilai index yang kosong metode kuadrat. Metode kuadrat yang dimaksud ialah mencari index yang belum terisi dari index ke 0, dengan menambahkan nilai index yang sama tersebut dengan angka kelipatan kuadrat dimulai dari 1. Metode ini juga memiliki notasi big O sebesar O(log n). Kelebihannya metode ini jauh lebih cepat.  Kekurangannya  metode ini mungkin saja tidak menemukan nilai dari index selanjutnya, sehingga perulangannya bisa mencapai tak hingga.

Berikut contohnya :

public class TestHash {
    private static final int MASK = 0x7FFFFFFF; // 2^32-1
    private static final int CAPACITY = 11;
    private static int size = 0;
    private static boolean[] used = new boolean[CAPACITY];
    private static final int MASK2 = 0x7FFFFFFF; // 2^32-1
    private static final int CAPACITY2 = 11;
    private static int size2 = 0;
    private static boolean[] used2 = new boolean[CAPACITY2];
    public static void main(String[] args) {
        System.out.println(“LINEAR”);
        printHash1(“Rad”);
        printHash1(“Uhr”);
        printHash1(“Ohr”);
        printHash1(“Tor”);
        printHash1(“Hut”);
        printHash1(“Tag”);
        printHash1(“Eis”);
        printHash1(“Ast”);
        printHash1(“Zug”);
        printHash1(“Hof”);
        printHash1(“Mal”);
           System.out.println(“QUADRATIC”);
           printHash2(“Rad”);
        printHash2(“Uhr”);
        printHash2(“Ohr”);
        printHash2(“Tor”);
        printHash2(“Hut”);
        printHash2(“Tag”);
        printHash2(“Eis”);
        printHash2(“Ast”);
        printHash2(“Zug”);
        printHash2(“Hof”);
        printHash2(“Mal”);
    }
    private static void printHash1(String word) {
        System.out.printf(“hash(%s) = %d, load = %d%%%n”,
                word, hash(word), 100 * size / CAPACITY);
    }
    private static int hash(Object object) {
        ++size;
        int h = (object.hashCode() & MASK) % CAPACITY;
        while (used[h]) {
            System.out.printf(“%d, “, h);
            h = (h + 1) % CAPACITY;
        }
        used[h] = true;
        return h;
    }
    private static void printHash2(String word) {
        System.out.printf(“hash(%s) = %d, load = %d%%%n”,
                word, hash2(word), 100 * size2 / CAPACITY2);
    }
    private static int hash2(Object object) {
        ++size2;
        int h = (object.hashCode() & MASK2) % CAPACITY2;
        if (used2[h]) {
            int h0 = h;
            int jump = 1;
            while (used2[h]) {
                System.out.printf(“%d, “, h);
                h = (h0 + jump * jump) % CAPACITY2; // squared increment
                ++jump;
            }
        }
        used2[h] = true;
        return h;
    }
}

Output :

run:
LINEAR
hash(Rad) = 3, load = 9%
hash(Uhr) = 4, load = 18%
hash(Ohr) = 2, load = 27%
hash(Tor) = 8, load = 36%
hash(Hut) = 5, load = 45%
3, 4, 5, hash(Tag) = 6, load = 54%
5, 6, hash(Eis) = 7, load = 63%
3, 4, 5, 6, 7, 8, hash(Ast) = 9, load = 72%
9, hash(Zug) = 10, load = 81%
3, 4, 5, 6, 7, 8, 9, 10, hash(Hof) = 0, load = 90%
2, 3, 4, 5, 6, 7, 8, 9, 10, 0, hash(Mal) = 1, load = 100%
QUADRATIC
hash(Rad) = 3, load = 9%
hash(Uhr) = 4, load = 18%
hash(Ohr) = 2, load = 27%
hash(Tor) = 8, load = 36%
hash(Hut) = 5, load = 45%
3, 4, hash(Tag) = 7, load = 54%
5, hash(Eis) = 6, load = 63%
3, 4, 7, hash(Ast) = 1, load = 72%
hash(Zug) = 9, load = 81%
Exception in thread “main” java.lang.ArrayIndexOutOfBoundsException: -8
3, 4, 7, 1, 8, 6, 6, 8, 1, 7, 4, 3, 4, 7, 1, 8, 6, 6, 8, 1, 7, 4, 3, 4, 7, 1, 7, 4, 3, 4, 7, 1, 8, 6, 6, 8, 1, …..
at TestHash.hash2(TestHash.java:73)
                at TestHash.printHash2(TestHash.java:63)
                at TestHash.main(TestHash.java:42)
Java Result: 1
BUILD SUCCESSFUL (total time: 0 seconds)

Ketarangan : Output asli dari kuadratic tersebut ialah tak dingga pada saat meng-input Hof, maka keluaranya bisa menjadi baris angka sepanjang 25 hal word.. hhehehe..

Komentarin aja

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s