Dalam sebuah makalah tahun 1985, ilmuwan komputer Andrew Yao, yang akan memenangkan penghargaan AM Turing, menegaskan bahwa di antara tabel hash dengan serangkaian properti tertentu, cara terbaik untuk menemukan elemen individu atau tempat kosong adalah dengan hanya melalui bintik -bintik potensial – pendekatan yang dikenal sebagai penyelidikan seragam. Dia juga menyatakan bahwa, dalam skenario terburuk, di mana Anda mencari tempat terbuka terakhir yang tersisa, Anda tidak akan pernah bisa melakukan yang lebih baik dari X. Selama 40 tahun, sebagian besar ilmuwan komputer berasumsi bahwa dugaan Yao benar.
Krapivin tidak ditahan oleh kebijaksanaan konvensional karena alasan sederhana bahwa ia tidak menyadarinya. “Saya melakukan ini tanpa mengetahui tentang dugaan Yao,” katanya. Eksplorasi dengan pointer kecil menyebabkan jenis tabel hash baru – yang tidak bergantung pada penyelidikan yang seragam. Dan untuk tabel hash baru ini, waktu yang diperlukan untuk kueri dan insersi terburuk sebanding dengan (log X)2—Far lebih cepat dari X. Hasil ini secara langsung bertentangan dengan dugaan Yao. Farach-Colton dan Kuszmaul membantu Krapivin menunjukkan itu (log X)2 adalah batas optimal, tak terkalahkan untuk kelas populer dari tabel hash yang telah ditulis Yao.
“Hasil ini indah karena membahas dan memecahkan masalah klasik,” kata Guy Blelloch dari Carnegie Mellon.
“Bukan hanya karena mereka membantah [Yao’s conjecture]mereka juga menemukan jawaban terbaik untuk pertanyaannya, ”kata Sepehr Assadi dari University of Waterloo. “Kita bisa pergi 40 tahun lagi sebelum kita tahu jawaban yang benar.”
Selain menyangkal dugaan Yao, makalah baru ini juga berisi apa yang banyak dianggap sebagai hasil yang lebih mencengangkan. Ini berkaitan dengan situasi yang terkait, meskipun sedikit berbeda, pada tahun 1985, Yao tidak hanya melihat waktu terburuk untuk pertanyaan, tetapi juga pada rata-rata waktu yang diambil di semua kueri yang mungkin. Dia membuktikan bahwa tabel hash dengan properti tertentu – termasuk yang diberi label “serakah,” yang berarti bahwa elemen baru harus ditempatkan di tempat pertama yang tersedia – tidak akan pernah mencapai waktu rata -rata lebih baik daripada log X.
Farach-Colton, Krapivin, dan Kuszmaul ingin melihat apakah batas yang sama juga diterapkan pada tabel hash non-greedy. Mereka menunjukkan bahwa itu tidak dengan memberikan contoh tandingan, tabel hash non-greedy dengan waktu kueri rata-rata yang jauh lebih baik daripada log X. Faktanya, itu tidak bergantung pada X sama sekali. “Anda mendapatkan nomor,” kata Farach-Colton, “sesuatu yang hanya konstan dan tidak bergantung pada seberapa penuh tabel hash.” Fakta bahwa Anda dapat mencapai waktu kueri rata -rata yang konstan, terlepas dari kepenuhan meja hash, sepenuhnya tidak terduga – bahkan bagi penulis sendiri.
Hasil tim mungkin tidak mengarah pada aplikasi langsung apa pun, tetapi tidak terlalu penting, kata Conway. “Penting untuk memahami struktur data semacam ini dengan lebih baik. Anda tidak tahu kapan hasil seperti ini akan membuka kunci sesuatu yang memungkinkan Anda melakukan lebih baik dalam latihan. “
Cerita asli Dicetak ulang dengan izin dari Majalah Quanta, publikasi editorial independen dari Yayasan Simons yang misinya adalah untuk meningkatkan pemahaman publik tentang sains dengan meliput perkembangan penelitian dan tren matematika dan ilmu fisik dan kehidupan.
