Wawancara Coding: Bagaimana Cara Mengimplementasikan Robin Hood Hashing?

Petunjuk dan ruang lingkup

Implementasikan tabel hash open-addressing berkapasitas tetap dengan larik sebanyak m slot, di mana setiap slot menampung paling banyak satu pasangan kunci-nilai. Dukung insert(key,value), contains(key), dan remove(key). Selesaikan tabrakan dengan Robin Hood hashing; jangan gunakan chaining atau tombstone. Untuk berfokus pada algoritma inti, tabel yang penuh dapat mengembalikan kegagalan alih-alih mengubah ukuran (resizing).

Ini adalah masalah wawancara coding umum tentang struktur data, invarian, edge case, dan kompleksitas. Tugas publik CS106B Stanford meminta mahasiswa untuk mengimplementasikan tabel Robin Hood dan secara eksplisit menyertakan pertukaran jarak probe, penghentian pencarian dini, dan penghapusan pergeseran mundur. Panduan wawancara rekayasa perangkat lunak saat ini mencantumkan pertimbangan struktur data, kebenaran, kompleksitas, dan penanganan edge case sebagai sinyal penilaian coding.

Apa yang diuji oleh pewawancara

• Dapatkah Anda menyimpan home bucket dan PSL (probe sequence length) dari setiap elemen?
• Dapatkah Anda menjelaskan prinsip “kunci yang lebih miskin mendapat prioritas”: ketika PSL yang masuk lebih besar, lakukan pertukaran dengan kunci penghuni yang lebih dekat ke home bucket-nya?
• Dapatkah Anda menggunakan monotonisitas PSL untuk menghentikan pencarian yang gagal lebih awal alih-alih memindai seluruh larik?
• Dapatkah Anda menghapus tanpa tombstone sambil menjaga setiap kunci dalam klaster probe tetap dapat dijangkau?
• Dapatkah Anda menyatakan biaya rata-rata dan kasus terburuk serta memilih kebijakan untuk beban tinggi?

Jawaban rutin biasanya menuliskan linear probing tetapi melewatkan fakta bahwa celah penghapusan akan memotong jalur pencarian berikutnya. Jawaban yang kuat mengubah “slot kosong” dan “PSL penghuni di bawah PSL target” menjadi kondisi berhenti yang terbukti.

Klarifikasi sebelum menjawab

1. Apakah kapasitasnya tetap? Dengan kapasitas tetap, kegagalan penyisipan adalah hasil eksplisit; dengan pengubahan ukuran, ambang batas load factor memicu pembangunan ulang (rebuild).
2. Apakah kunci duplikat diperbolehkan? Asumsikan duplikat memperbarui nilainya alih-alih menambahkan slot kedua; sebuah multimap akan membutuhkan API dan kontrak penghapusan yang berbeda.
3. Apakah fungsi hash stabil dan kunci dapat disalin? Hash harus stabil selama satu operasi. Menyimpan cache home bucket dapat menghindari kalkulasi berulang tetapi menghabiskan memori slot.
4. Haruskah iterator atau referensi tetap stabil? Pertukaran dan pergeseran mundur memindahkan elemen, sehingga alamat yang stabil tidak dijamin. Gunakan indireksi jika pemanggil memerlukan handle yang stabil.
5. Apakah konkurensi termasuk dalam cakupan? Ini bersifat single-threaded. Versi konkuren membutuhkan penguncian (locking), striping, atau protokol lock-free; implementasi biasa tidak thread-safe.

Kerangka jawaban 30 detik

“Saya menyimpan kunci, nilai, home bucket, dan PSL di setiap slot yang terisi. Penyisipan melakukan probe linier dari home; ketika PSL yang masuk melebihi PSL penghuni, saya menukarnya agar elemen yang menempuh jarak lebih jauh mendapat prioritas, kemudian melanjutkan penempatan item yang tergeser. Pencarian dapat gagal pada slot kosong atau ketika PSL penghuni berada di bawah PSL target, karena entri setelahnya tidak mungkin kembali ke jarak yang lebih pendek. Penghapusan menggeser entri berikutnya ke belakang hingga menemukan slot kosong atau entri dengan PSL nol, mengurangi PSL untuk setiap pergeseran sehingga tidak ada jalur pencarian yang terputus. Operasi yang diharapkan mendekati O(1), kasus terburuk adalah O(m), dan ruang adalah O(m).”

Jawaban mendalam langkah demi langkah

1. Model slot dan invarian

Setiap slot yang terisi menyimpan (key, value, home, psl). Dalam cincin berisi m slot, psl = (index - home + m) % m. Pertahankan tiga invarian:

• home adalah titik asal hash tetap untuk kunci.
• Melangkah sebanyak psl langkah ke depan dari home akan mencapai indeks saat ini.
• Dalam satu klaster probe yang berdekatan, nilai PSL yang terisi tidak pernah menurun; slot kosong mengakhiri klaster.

Invarian ketiga berasal dari pemberian prioritas kepada PSL yang lebih besar pada saat penyisipan. Hal ini memungkinkan pencarian membandingkan PSL target dengan PSL penghuni alih-alih memeriksa setiap slot setelahnya.

2. Hambatan pada linear probing

Linear probing biasa melangkah maju dari home hingga menemukan slot kosong. Pada beban tinggi, kunci awal dapat menempati slot yang dekat dengan home sementara kunci berikutnya yang telah melakukan probe jauh terus melangkah; varians panjang probe kemudian meningkatkan tail latency. Robin Hood hashing mempertahankan tata letak larik yang kompak tetapi memberikan prioritas kepada kunci yang telah menempuh perjalanan lebih jauh saat terjadi tabrakan.

3. Penyisipan Robin Hood

Pseudocode:

insert(key, value):
    item = (key, value, home=hash(key), psl=0)
    for step in 0 .. m-1:
        i = (item.home + item.psl) mod m
        if table[i] is empty:
            table[i] = item
            return success
        if table[i].key == key:
            table[i].value = value
            return updated
        if table[i].psl < item.psl:
            swap(table[i], item)
        item.psl += 1
    return full

Setelah pertukaran, item adalah entri yang tergeser. PSL-nya sudah mendeskripsikan posisi probe saat ini, sehingga iterasi berikutnya menambahkannya satu kali. Bedakan slot kosong dari entri sebenarnya yang memiliki PSL nol; jika tidak, batas penyisipan dan penghapusan menjadi ambigu.

4. Pencarian dan penghentian dini

Pencarian dimulai pada home target dan melacak PSL target:

contains(key):
    home = hash(key)
    for psl in 0 .. m-1:
        i = (home + psl) mod m
        if table[i] is empty:
            return false
        if table[i].psl < psl:
            return false
        if table[i].key == key:
            return true
    return false

Slot kosong mengakhiri klaster. PSL penghuni di bawah target berarti slot berikutnya tidak mungkin berisi target, karena PSL klaster tidak pernah menurun. Tugas Stanford memperlakukan penghentian dini ini sebagai perbedaan inti dari linear probing biasa.

5. Penghapusan pergeseran mundur (backward-shift deletion)

Jangan langsung mengosongkan slot: kunci berikutnya mungkin telah melintasinya selama resolusi tabrakan, dan pencarian akan berhenti secara keliru pada celah tersebut. Tombstone juga dilarang dan akan memperpanjang probe dari waktu ke waktu.

remove(key):
    i = find_index_or_not_found(key)
    if i is not found:
        return false
    j = (i + 1) mod m
    while table[j] is not empty and table[j].psl > 0:
        table[i] = table[j]
        table[i].psl -= 1
        i = j
        j = (j + 1) mod m
    table[i] = empty
    return true

Berhenti pada slot kosong atau entri dengan PSL nol. Yang pertama mengakhiri klaster; yang terakhir berada di home-nya sendiri, sehingga mengosongkan slot sebelumnya tidak akan memutus jalur pencariannya. Setiap pemindahan mengurangi PSL dan memulihkan invarian jarak.

6. Kompleksitas dan kebijakan beban tinggi

Dengan uniform hashing dan load factor α yang berada cukup jauh di bawah satu, probe yang diharapkan untuk insert, lookup, dan delete berskala konstan. Operasi tunggal masih dapat memindai semua m slot, sehingga waktu kasus terburuk adalah O(m) dan ruang adalah O(m). Robin Hood hashing terutama meningkatkan distribusi dan varians panjang probe; ini tidak menghilangkan kasus terburuk dari open-addressing. Analisis yang dikutip mempelajari varians terbatas dalam model beban tinggi, tetapi kode produksi tetap memerlukan ambang batas beban.

Ketika α mendekati ambang batas tersebut, bangun ulang (rebuild) pada kapasitas yang lebih besar alih-alih mengandalkan ekspektasi O(1). Jika kapasitas harus tetap, perlakukan full sebagai hasil bisnis normal dan pantau failure rate, mean PSL, P99 probes, dan panjang pergeseran penghapusan.

7. Contoh kasus uji dan pembuktian

• Penyisipan dan pencarian pada tabel kosong: slot home langsung terisi, dan kunci yang tidak ada akan berhenti pada slot kosong pertama.
• Kunci duplikat: memperbarui nilai tidak menambah jumlah elemen.
• Wraparound (perputaran indeks): pilih home di dekat akhir dan verifikasi (index - home + m) % m.
• Rantai pertukaran: buat kunci-kunci yang bertabrakan dan verifikasi bahwa satu penyisipan dapat menggeser dan menempatkan setiap item dengan benar.
• Hapus kepala, tengah, dan ekor klaster: semua kunci yang tersisa tetap dapat ditemukan.
• Hapus entri home: berhenti ketika entri penerus memiliki PSL nol, menghindari pergerakan lintas klaster.
• Tabel penuh: kunci unik ke-(m+1) mengembalikan kegagalan alih-alih melakukan perulangan tanpa henti.
• Hash berlawanan (adversarial hash): petakan banyak kunci ke satu home, verifikasi kebenaran, dan ekspos probe O(m) dalam metrik.

Contoh jawaban berkualitas tinggi

“Saya akan menggunakan tabel open-addressing Robin Hood berkapasitas tetap, menyimpan kunci, nilai, dan PSL di setiap slot yang terisi. Penyisipan melakukan probe secara linier dari home. Jika entri yang masuk telah berjalan lebih jauh daripada entri penghuni, saya menukarnya dan melanjutkan penempatan entri yang tergeser. Ini menjaga agar PSL tidak menurun dalam suatu klaster probe.

Pencarian memanfaatkan invarian tersebut: slot kosong menandakan kegagalan, dan PSL penghuni yang berada di bawah PSL target juga menandakan kegagalan karena entri setelahnya tidak mungkin kembali ke jarak yang lebih pendek. Penghapusan tidak boleh meninggalkan celah, jadi saya menggeser entri ke belakang selama PSL-nya positif dan mengurangi setiap PSL; slot kosong atau entri ber-PSL nol mengakhiri pergeseran. Waktu yang diharapkan mendekati O(1), kasus terburuk adalah O(m), sehingga load factor, P99 probes, dan panjang pergeseran menentukan apakah perlu mengubah ukuran atau menolak penyisipan. Karena pergeseran memindahkan elemen, saya tidak menjamin stabilitas iterator atau alamat memori.”

Kesalahan umum

• Kesalahan → selalu mempertahankan penghuni lama saat tabrakan → entri berikutnya mengumpulkan probe yang panjang → lakukan swap jika PSL yang masuk lebih besar.
• Kesalahan → menghentikan pencarian hanya pada slot kosong → kehilangan optimasi PSL → hentikan juga saat PSL penghuni berada di bawah target.
• Kesalahan → langsung mengosongkan slot yang dihapus → celah memotong jalur probe berikutnya → gunakan pergeseran mundur dan kurangi PSL.
• Kesalahan → menghentikan pergeseran pada sembarang entri yang terisi → meninggalkan kunci yang tidak terjangkau atau berpindah lintas klaster → geser hanya selama PSL klaster yang berdekatan bernilai positif.
• Kesalahan → menuliskan ekspektasi O(1) sebagai kasus terburuk O(1) → hash yang buruk dan beban tinggi membatalkannya → nyatakan kasus terburuk O(m) dan terapkan ambang batas beban.
• Kesalahan → menjanjikan referensi yang stabil → pertukaran dan penghapusan memindahkan entri → kembalikan handle, gunakan indireksi, atau hilangkan jaminan alamat.

Pertanyaan lanjutan dan tanggapan

Kapan tabel yang berkembang secara dinamis harus dibangun ulang?

Picu berdasarkan load factor dan tail probe latency, seperti α yang dikonfigurasi atau batas probe P99. Hitung ulang setiap home dan PSL selama pembangunan ulang; menyalin slot secara langsung adalah keliru karena modulus larik berubah. Write lock, migrasi tabel ganda, atau pembangunan ulang di latar belakang dapat memenuhi target ketersediaan yang berbeda, tetapi tentukan kebijakan konsistensi dan jeda terlebih dahulu.

Mengapa menghindari tombstone, dan bisakah pergeseran mundur memakan biaya terlalu tinggi?

Tombstone membuat penghapusan menjadi O(1) tetapi memperpanjang pencarian secara permanen hingga dilakukan pembangunan ulang. Pergeseran mundur memusatkan beban kerja pada operasi penghapusan dan menjaga klaster tetap kompak. Jika penghapusan mendominasi dan operasi baca jarang, tombstone ditambah pembangunan ulang berkala bisa lebih unggul; jika latensi baca sangat penting, lebih baik pilih pergeseran mundur dan pantau panjang pemindahannya.

Bagaimana Anda menangani pembaca dan penulis yang konkuren?

Implementasi ini bersifat single-threaded. Versi konkuren paling sederhana menggunakan read-write lock; pertukaran dan pergeseran harus berada dalam satu critical section penulisan sehingga pembaca tidak pernah melihat klaster yang baru berpindah sebagian. Throughput yang lebih tinggi dapat menggunakan striped lock atau snapshot immutable. Desain lock-free memerlukan version word, memory ordering, dan reklamasi memori; pointer slot atomik saja tidak cukup.

Apakah Robin Hood membuat pencarian rata-rata menjadi waktu konstan?

Di bawah model uniform-hash standar, biaya open-addressing yang diharapkan bergantung pada load factor. Robin Hood terutama mengurangi varians panjang probe dan sebaran tail. Biaya rata-rata tetap meningkat pada beban tinggi dan kasus terburuk dapat memindai seluruh tabel, sehingga perbaikan varians tidak menggantikan pengendalian beban dan benchmark.