🌎Praktikum 1

Implementasi Hash Table Sederhana

Deskripsi

Pada praktikum ini, Anda akan membuat struktur data hash table secara sederhana dengan mengimplementasikan fungsi-fungsi utama dari Hash Table.

Langkah Percobaan

• Buatlah kelas HashTable.

• Tambahkan atribut size dan dataMap.

private int size = 7;
private Node[] dataMap;

• Didalam kelas HashTable, tambahkan kelas internal Node. Perhatikan kelas internal Node. Kelas tersebut merupakan representasi node untuk menyimpan data dalam linked list.

class Node {
    String key;
    int value;
    Node next;
    
    Node(String key, int value) {
        this.key = key;
        this.value = value;
    }
}

• Buat konstruktor untuk kelas HashMap untuk mendeklarasikan ukuran dari array linked list.

public HashTable() {
    this.dataMap = new Node[this.size];
}

• Buat method printTable() yang akan digunakan untuk mengetahui isi setiap slot pada hash table.

public void printTable() {
    for (int i = 0; i < this.dataMap.length; i++) {
        System.out.println(i + ":");
        Node current = this.dataMap[i];
        while (current != null) {
            System.out.println("Key: " + current.key + ", Value: " + current.value);
            current = current.next;
            
        }
    }
}

• Implementasikan fungsi hashing ASCII dengan method hash().

public int hash(String key) {
    int hash = 0;
    for (int i = 0; i < key.length(); i++) {
        hash = (hash + key.charAt(i) * i) % this.dataMap.length;
    }
    return hash;
}

• Buatlah kelas HashTableMain. Kemudian buatlah beberapa nilai "key" untuk menguji hasil dari proses hashing.

public class HashTableMain {
    public static void main(String[] args) {
        HashTable table = new HashTable();

        System.out.println( table.hash("apple") );
        System.out.println( table.hash("banana") );
        System.out.println( table.hash("cherry") );
        System.out.println( table.hash("date") );
        System.out.println( table.hash("eggplant") );
    }
}

• Jalankan program dan amati hasilnya.

Hasil Hashing

• Tambahkan method set() yang digunakan untuk menambakan data pada hash table.

public void set(String key, int value) {
    int hash = this.hash(key);
    Node newNode = new Node(key, value);
    if (this.dataMap[hash] == null) {
        this.dataMap[hash] = newNode;
    } else {
        Node current = this.dataMap[hash];
        if(current.key == key) {
            current.value += value;
            return;
        }
        while (current.next != null) {
            current = current.next;
            if(current.key == key) {
                current.value += value;
                return;
            }
        }
        current.next = newNode;
    }
}

• Tambahkan data berikut pada kelas HashTableMain.

table.set("apple", 100);
table.set("banana", 50);
table.set("cherry", 300);
table.set("date", 500);
table.set("eggplant", 10);

• Cetak hasil penambahakn data dengan method printTable().

• Amati hasilnya.

Hasil Penambahan Data

• Tambahkan method get() untuk mendapatkan data berdasarkan key pada hash table.

public int get(String key) {
    int hash = this.hash(key);
    Node current = this.dataMap[hash];
    while (current != null) {
        if (current.key == key) return current.value;
        current = current.next;
    }
    return 0;
}

• Tambakan kode berikut pada main class untuk memastikan apakah methode get() berjalan dengan baik.

System.out.println("Apple:");
System.out.println( table.get("apple") );

System.out.println("\nDate:");
System.out.println( table.get("date") );

• Jalankan program dan amati hasilnya.

Hasil Pencarian Data

• Tambahkan method keys() pada hash table untuk mendapatkan semua key pada struktur data hash table. Method ini akan menggunakan ArrayList untuk menyimpan key. Pastikan Anda telah mengimport package ArrayList pada kelas HashTable.

public ArrayList keys() {
    ArrayList<String> keys = new ArrayList<>();
    for (int i = 0; i < this.dataMap.length; i++) {
        Node current = this.dataMap[i];
        while (current != null) {
            keys.add(current.key);
            current = current.next;
        }
    }
    return keys;
}

• Tambakan kode berikut pada main class untuk mengetahui apakah method keys() dapat berkeja dengan baik.

System.out.println( table.keys() );

• Jalankan program dan amati hasilnya.

Hasil Method keys()

Pertanyaan

• Apa keunggulan penanganan collision menggunakan metode separate chaining dibandingkan dengan motode linear probing?

• Apa maksud dari potongan kode berikut pada method hash()?

int hash = 0;
for (int i = 0; i < key.length(); i++) {
    hash = (hash + key.charAt(i) * i) % this.dataMap.length;
}

• Apa maksud dari potongan kode berikut pada method set()?

else {
    Node current = this.dataMap[hash];
    if(current.key == key) {
        current.value += value;
        return;
    }
    while (current.next != null) {
        current = current.next;
        if(current.key == key) {
            current.value += value;
            return;
        }
    }
    current.next = newNode;
}

• Buatlah method remove() untuk menghapus data berdasarkan key.