Dalam sebuah paper tahun 1985, ilmuwan komputer Andrew Yao, yang kemudian memenangkan Penghargaan A.M. Turing, menyatakan bahwa di antara tabel hash dengan serangkaian properti tertentu, cara terbaik untuk menemukan elemen individu atau tempat kosong adalah dengan hanya melalui tempat-tempat potensial secara acak—pendekatan yang dikenal sebagai uniform probing. Dia juga menyatakan bahwa, dalam skenario terburuk, di mana Anda mencari tempat kosong terakhir yang tersisa, Anda tidak akan pernah lebih baik daripada x. Selama 40 tahun, sebagian besar ilmuwan komputer menganggap bahwa dugaan Yao benar.
Krapivin tidak terhalang oleh kebijaksanaan konvensional karena dia tidak menyadarinya. “Saya melakukan ini tanpa mengetahui dugaan Yao,” katanya. Penjelajahannya dengan pointer kecil mengarah pada jenis tabel hash baru—salah satu yang tidak bergantung pada uniform probing. Dan untuk tabel hash baru ini, waktu yang dibutuhkan untuk kueri dan penyisipan dalam skenario terburuk proporsional dengan (log x)2—jauh lebih cepat daripada x. Hasil ini langsung menentang dugaan Yao. Farach-Colton dan Kuszmaul membantu Krapivin menunjukkan bahwa (log x)2 adalah batas optimal yang tak terkalahkan untuk kelas tabel hash yang populer yang ditulis Yao.
“Hasil ini indah karena mengatasi dan memecahkan masalah klasik tersebut,” kata Guy Blelloch dari Carnegie Mellon.
“Bukan hanya mereka membantah [dugaan Yao], mereka juga menemukan jawaban terbaik untuk pertanyaannya,” kata Sepehr Assadi dari Universitas Waterloo. “Kita bisa saja menunggu 40 tahun lagi sebelum kita tahu jawaban yang benar.”
Krapivin di Jembatan King’s College di Universitas Cambridge. Tabel hash barunya dapat menemukan dan menyimpan data lebih cepat daripada yang pernah dibayangkan peneliti.
Foto: Phillip Ammon untuk Majalah Quanta
Selain membantah dugaan Yao, paper baru ini juga berisi apa yang banyak dianggap sebagai hasil yang lebih menakjubkan. Ia berkaitan dengan situasi yang terkait, meskipun sedikit berbeda: Pada tahun 1985, Yao tidak hanya melihat waktu terburuk untuk kueri, tetapi juga waktu rata-rata yang diambil di seluruh kueri yang mungkin. Dia membuktikan bahwa tabel hash dengan properti tertentu—termasuk yang dilabeli “serakah,” yang berarti elemen-elemen baru harus ditempatkan di tempat yang tersedia pertama kali—tidak akan pernah mencapai waktu rata-rata yang lebih baik daripada log x.
Farach-Colton, Krapivin, dan Kuszmaul ingin melihat apakah batas yang sama juga berlaku untuk tabel hash non-serakah. Mereka menunjukkan bahwa tidak dengan memberikan contoh, tabel hash non-serakah dengan waktu kueri rata-rata yang jauh lebih baik daripada log x. Bahkan, itu tidak tergantung pada x sama sekali. “Anda mendapatkan sebuah angka,” kata Farach-Colton, “sesuatu yang hanya berupa konstan dan tidak tergantung pada seberapa penuh tabel hash itu.” Fakta bahwa Anda dapat mencapai waktu kueri rata-rata konstan, terlepas dari kepenuhan tabel hash, benar-benar tidak terduga—bahkan bagi para penulis sendiri.
Hasil tim mungkin tidak mengarah pada aplikasi langsung apa pun, tetapi bukan itu satu-satunya hal yang penting, kata Conway. “Penting untuk lebih memahami struktur data seperti ini. Anda tidak pernah tahu kapan hasil seperti ini akan membuka sesuatu yang memungkinkan Anda melakukan yang lebih baik dalam praktik.”
Cerita asli dicetak ulang dengan izin dari Majalah Quanta, sebuah publikasi independen editorial dari Simons Foundation yang misinya adalah untuk meningkatkan pemahaman masyarakat tentang ilmu pengetahuan dengan meliput perkembangan penelitian dan tren dalam matematika serta ilmu pengetahuan fisika dan kehidupan.