Hash tables:
------------
bermula dari: BST Insert, Find, Delete -> O(log N)

mengambil keuntungan dari array primitive, random
access ke A[i] adalah O(1).
gunakan array sebagai Hash Table !

Sebuah usaha agar operasi Insert, Find, Delete 
On-Average O(1) !

Butuh fungsi yang memetakan sebuah elemen X 
ke indeks i, dimana 0 <= i < hashtable-size.
=> ini tugas Fungsi Hash

elemen dalam hash table unik...

Fungsi Hash:
------------
1. Komputasi harus murah/cepat/efisien
2. Mampu mendistribusikan keys secara merata
   pada hash table
3. Meminimalkan Collision
4. Bersifat satu arah (tidak invertible)

fungsi hash paling sederhana:
hash(x) = x % tablesize

fungsi hash yang biasa digunakan untuk String:
public static int hash(String key, int tableSize) {
    int hashVal = 0;
    for (int i=0; i < key.length(); i++) {
        hashVal = (hashVal * 37 
            + key.charAt(i));
    }
    hashVal %= tableSize;
    if (hashVal < 0) {
        hashVal += tableSize;
    }
    return hashVal;
}

Collision:
----------
2/lebih item dipetakan (oleh fungsi hash) ke lokasi/key yang sama.

resolution:
1. open addressing/closed hashing/probing

Hi(x) = (hash(x) + f(i)) % tablesize

i: collision yang ke-i

- Linear Probing ---> f(i) = i
  terjadi collision, +1, terjadi collision lagi, +1, dst...

  Bagus ketika load factor <= 0.5
  load_factor = banyaknya data / ukuran hash table  

  delete item ? lazy deletion --> tidak benar-benar dihapus
  hanya diberi tanda "deleted"

  Masalah: Primary Clustering  --> Blocks of occupied cells
    --> elemen2 yang menurut fungsi hash diletakkan di cell
        berbeda, diarahkan (probed) pada cell yang sama.
    --> penyebab: banyak elemen2 yang dipetakkan oleh fungsi hash 
        ke CLUSTER yang sama
  
  solusi Primary Clustering --> Quadratic Probing,
  agar tidak diarahkan ke cell yang sama

- Quadratic Probing ---> f(i) = i^2
  misal, indeks awal terjadi collision = H, maka
  kita coba probing ke H+1^2, H+2^2, H+3^2, ... dengan kunjungan 
  circular pada hashtable.

  ukuran hash table sangat penting:
  - biasanya digunakan ukuran yang merupakan bilangan Prima
    teorema: jika ukuran hash table adalah bilangan prima M,
             dijamin M/2 probing yang pertama (ketika collision) 
             pasti mengunjungi cell yang berbeda !

  dari teorema di atas, Quadratic Probing baik ketika
  load factor <= 0.5

  jika lebih dari itu load factornya, biasanya dilakukan REHASHING !

  Rehashing -> buat table baru yang ukurannya lebih besar
            -> elemen di table lama dihash kembali ke table baru

  Masalah: Secondary Clustering
    --> elemen2 yang menurut hash diletakkan di lokasi sel sama,
        diarahkan pada sel yang sama juga
    --> penyebab: ada banyak elemen yang dipetakkan ke lokasi sel
        yang sama !

  Solusi Secondary Clustering: untuk probing, gunakan Hash function
  kembali --> Double Hashing

- Double Hashing ---> f(i) = i * hash2(x)

  - probing sequence mengikuti fungsi hash ke-2 hash2(x)
    jika ada 2 elemen beda, kemungkinannya kecil nilai
    hash2(x) sama...

  - hash2(x) tidak boleh 0. mengapa ?

  - good common choice: hash2(x) = R - (x mod R)
    R adalah bilangan prima yang < tablesize

2. closed addressing/open hashing/chaining
- lihat slide ...